搜索装置、搜索方法、程序、搜索系统以及套利系统

技术领域

本发明的实施方式涉及搜索装置、搜索方法、程序、搜索系统以及套利系统。

背景技术

用于提高社会系统的生产率的大部分课题归结于组合最佳化问题。根据某些评价函数选择由节点(顶点)和连接节点与节点的有向边(edge)构成的图形中的、连接开始节点与终点节点之间的路径的问题被称为路径搜索问题。例如，探测汇兑等套利的机会的套利问题被公式化为有向图中的路径搜索问题。在该情况下，在有向图中，节点与货币对应，有向边与从与开始节点对应的货币向与结束节点对应的货币的交换对应，对有向边分配的权重值与货币的交换率对应。

另外，已知计算伊辛模型的基态的伊辛问题。伊辛问题是对用取±1这2值的变量(伊辛自旋)的2次函数提供的成本函数(伊辛能量)进行最小化的组合最佳化问题。

伊辛问题通过将伊辛自旋(s)变换为1次关系式(s＝2b-1)，能够利用使用比特(b)的式子来表示。b是0或者1这2值的变量。即，伊辛问题与对通过使用比特(b)的2次函数表示的成本函数进行最小化的问题相同。这样的问题还被称为QUBO(quadratic unconstrainedbinary optimization，二次无约束二元优化)问题。套利问题已知能够公式化为QUBO问题。

但是，要求高速地求解这样的最佳化问题的装置。例如，要求从对套利问题进行公式化的有向图中短时间内检测出因交换的结果而得到的收益(交换收益)成为最大的闭路(开始节点和结束节点是同一的路径)从而更快地探测套利的机会的装置。

发明内容

发明想要解决的课题在于高速地输出最佳化问题的解。

实施方式所涉及的搜索装置搜索对有向边分配有权重值的有向图中的最佳路径。所述搜索装置具备运算部，该运算部关于假想的多个粒子各自的位置以及运动量，从初始时刻至结束时刻按照每单位时间来更新位置以及运动量。所述多个粒子与对应于最佳路径搜索问题对应的0-1最佳化问题所包含的多个比特对应。所述多个比特与所述有向图所包含的多个有向边对应，所述多个比特分别表示对应的有向边是否被选择为所述最佳路径。所述运算部按照每所述单位时间，关于所述多个粒子的各个粒子，根据对应的粒子在比所述对象时刻提前1个单位时间的前一时刻下的运动量，计算对应的粒子在对象时刻下的位置。所述运算部按照每所述单位时间，关于所述有向图所包含的多个节点的各个节点，计算与出来的2个以上的有向边对应的、将2个以上的粒子在所述对象时刻下的位置累加的第1累计值。所述运算部按照每所述单位时间，关于所述有向图所包含的所述多个节点的各个节点，计算与进入的2个以上的有向边对应的、将2个以上的粒子在所述对象时刻下的位置累加的第2累计值。所述运算部按照每所述单位时间，关于所述多个粒子的各个粒子，根据结束节点的所述第1累计值及所述第2累计值、以及开始节点的所述第1累计值及所述第2累计值、以及对对应的有向边分配的权重值，计算对应的粒子在所述对象时刻下的运动量。在更新了位置以及运动量直至所述结束时刻为止之后，所述运算部根据对应的粒子在结束时刻下的位置，决定所述多个比特各自的值。根据所述搜索装置能够高速地输出最佳化问题的解。

附图说明

图1是示出有向图的图。

图2是用于说明储存与有向边对应的值以及变量的矩阵的图。

图3是示出对有向边分配了权重值的有向图的图。

图4是示出对有向边对应起来比特的有向图的图。

图5是示出第1实施方式所涉及的搜索装置的结构的图。

图6是示出第1实施方式所涉及的搜索装置的处理流程的流程图。

图7是示出第2实施方式所涉及的搜索装置的电路结构的图。

图8是示出存储器的结构的图。

图9是示出搜索装置的处理流程的流程图。

图10是示出对TE电路输入以及从TE电路输出的变量以及值的图。

图11是示出对GC电路输入以及从GC电路输出的变量的图。

图12是示出对CC电路输入以及从CC电路输出的变量以及值的图。

图13是示出对MX电路输入以及从MX电路输出的变量以及值的图。

图14是示出利用TE电路的变量以及值的读出顺序的图。

图15是示出利用MX电路的变量以及值的读出顺序的图。

图16是示出TE处理、MX处理以及GC处理的定时的图。

图17是示出TE电路的结构的图。

图18是示出GC电路的结构的图。

图19是示出利用GC电路的位置变量的取得顺序等的图。

图20是示出MX电路的结构的图。

图21是示出标准化电路的结构的图。

图22是示出CC电路的结构的图。

图23是示出第1主伪代码的图。

图24是示出第2主伪代码的图。

图25是示出TE伪代码的图。

图26是示出MX伪代码的图。

图27是示出并联化的TE电路的图。

图28是示出并联化的MX电路的图。

图29是示出并联化的GC电路的结构的图。

图30是示出利用并联化的GC电路的位置变量的取得顺序等的图。

图31是示出并联化前后的TE处理以及MX处理的定时的图。

图32是示出套利系统的结构的图。

图33是示出输入管理装置的结构的图。

(符号说明)

10：搜索装置；12：运算部；14：输入部；16：输出部；18：设定部；21：存储器；22：控制电路；23：第1电路；24：第2电路；25：二值化电路；26：标准化电路；31：TE电路；32：GC电路；33：CC电路；34：MX电路；41：X存储器电路；42：Y存储器电路；43：W存储器电路；44：Z存储器电路；45：XR存储器电路；46：XC存储器电路；47：XT存储器电路；48：最大值存储器电路；51：位置更新电路；52：限制电路；53：运动量更新电路；54：掩蔽电路；57：FY电路；58：第1加法器；60：第1多路复用器；61：第1比较器；62：第2多路复用器；63：第3多路复用器；64：第2比较器；65：FX电路；66：FW电路；67：第2加法器；68：第4多路复用器；69：第5多路复用器；71：行方向累加电路；72：第6多路复用器；73：第3比较器；74：列方向累加电路；77：FM电路；78：第3加法器；79：第1乘法器；80：第2乘法器；81：第3乘法器；82：第1减法器；83：第2减法器；84：第3减法器；85：第1内部加法器；86：第2内部加法器；87：第4乘法器；90：误差最小化部；91：最大值调整部；101：第7多路复用器；102：第4比较器；103：第8多路复用器；104：第1累加器；105：第9多路复用器；106：第5比较器；107：第10多路复用器；108：第6比较器；109：第2累加器；110：第11多路复用器；111：第7比较器；112：第3累加器；113：第12多路复用器；114：判定电路；115：幂乘电路；210：子TE电路；220：子X存储器电路；222：子Y存储器电路；224：子W存储器电路；226：子Z存储器电路；230：子MX电路；242：子XR存储器电路；244：子XC存储器电路；246：子XT存储器电路；262：行方向累加器；264：总加法器；266：解复用器；300：套利系统；312：接收装置；314：UDP处理部；316：输入管理装置；318：交易装置；320：TCP处理部；322：发送装置；332：传送电路；334：操纵电路；336：地址解码器；340：缓冲存储器；342：UT部；344：LT部；346：DI部。

具体实施方式

(第1实施方式)

说明第1实施方式所涉及的最佳路径问题及其解法。

(前提)

图1是示出有向图的图。

成为路径的搜索对象的有向图包括多个节点和多个有向边。对多个节点分别分配固有的索引。索引是1以上的整数。在有向图包括N个(N为3以上的整数)的节点的情况下，对多个节点分别分配从1至N的某一个固有的整数。此外，图1的例子示出N＝4的有向图。

多个有向边分别具有方向，分别表示从多个节点中的某一个节点(开始节点)出来朝向多个节点中的其他节点(结束节点)的路径。在本实施方式中，各有向边的开始节点和结束节点不同。即，在本实施方式中，有向边不包括开始节点和结束节点相同的边(自循环)。

此外，在实施方式中，将从第i个(i为1以上的整数并且N以下的整数)节点出来并进入第j个(j为1以上且N以下的整数、并且与i不同的值)节点的有向边表示为e

图2是用于说明储存与有向边对应的值以及变量的N×N矩阵的图。

在有向图所包含的节点的数量是N个的情况下，在实施方式中，这些值以及变量被储存到N行×N列的矩阵。在实施方式中，矩阵的行编号表示对应的有向边的开始节点的索引，列编号表示对应的有向边的结束节点的索引。但是，有向边不包括自循环，所以在矩阵中，作为对角分量(行编号和列编号相同的分量)的要素，储存不对路径搜索造成影响的值。图2的例子示出N＝4的情况的矩阵。

此外，也可以矩阵的行编号表示对应的有向边的结束节点的索引，列编号表示对应的有向边的开始节点的索引。

图3是示出对有向边分配权重值的有向图的图。

对有向图所包含的多个有向边分别分配权重值。在有向图包括N个节点的情况下，对从第i个节点出来并进入第j个节点的有向边分配的权重值被表示为w

作为最佳路径问题之一，有针对有向图检测最短路径的问题。检测最短路径的问题的解是对包含的2个以上的有向边分配的权重值之和成为最小的路径。

作为最佳路径问题之一，还有检测最长路径的问题、检测最小收益路径的问题、以及检测最大收益路径的问题。检测最长路径的问题的解是对包含的2个以上的有向边分配的权重值的倒数之和成为最小的路径。检测最小收益路径的问题的解是对包含的2个以上的有向边分配的权重值的对数值之和成为最小的路径。检测最大收益路径的问题的解是对包含的2个以上的有向边分配的权重值的倒数的对数值之和成为最小的路径。即，最长路径问题、最小收益路径问题以及最大收益路径问题能够作为最短路径问题来求解。

例如，考虑探测汇兑的套利的机会的套利问题。在该情况下，在有向图中，节点与货币对应，有向边与从开始节点的货币向结束节点的货币的交换对应。而且，对从第i个节点出来并进入第j个节点的有向边分配的权重值如下述的式(1)所示。

【数式1】

w

在式(1)中，r

在这样的有向图中，对包含的2个以上的有向边分配的权重值之和成为最小的闭路表示总体率(total rate)成为最大的闭路。因此，这样的有向图的最短路径问题的解与探测汇兑的套利机会的套利问题的解相当。

另外，例如，在检测最短距离的问题的情况下，有向图的节点与地点对应，对有向边分配的权重值表示从开始节点的地点至结束节点的地点的距离。在该情况下，权重值成为正的值。另外，在该情况下，对从第i个节点出来并进入第j个节点的有向边分配的权重值与对从第j个节点出来并进入第i个节点的有向边分配的权重值相同。即，这样的有向图可视为无向图。因此，检测无向图中的最短距离的问题能够作为有向图中的最短路径问题来求解。

(与闭路有关的问题)

在最佳路径问题中，有与闭路(环状的路径)有关的问题、和与连接不同的2个节点之间的路径有关的问题。首先，说明与闭路有关的问题，接下来说明与连接不同的2个节点之间的路径有关的问题。

图4是示出对有向边对应起来比特的有向图的图。有向图的最佳路径问题能够公式化为0-1最佳化问题。

在将有向图的最佳路径问题公式化为0-1最佳化问题的情况下，对多个有向边的分别对应起来比特。即，0-1最佳化问题所包含的多个比特与有向图所包含的多个有向边对应。此外，在本实施方式中，对从第i个节点出来并进入第j个节点的有向边分配的比特被表示为b

进而，0-1最佳化问题所包含的多个比特分别表示对应的有向边是否被选择为最佳路径。在本实施方式中，关于多个比特的各个比特，在是1的情况下，表示对应的有向边被选择为最佳路径，在是0的情况下，表示对应的有向边未被选择为最佳路径。例如，如果是套利问题，则多个比特的各个在是1的情况下，表示进行从开始节点的货币向结束节点的货币的交换，在0的情况下，表示不进行从开始节点的货币向结束节点的货币的交换。

而且，在将有向图的最佳路径问题公式化为0-1最佳化问题的情况下，最小化的式子通过下述的式(2)表示。

E＝M

C是使用多个比特来表示对包含于选择的路径的2个以上的有向边分配的权重值的合计值的成本函数。P是使用多个比特来表示满足最佳路径的制约条件的惩罚函数。M

在本实施方式中，成本函数C如下述的式(3)所示。

【数式2】

式(3)使用多个比特，表示对选择出的路径所包含的2个以上的有向边分配的权重值的合计值(累加值)。式(3)是对除了i＝j的情况以外的i和j的所有组合中的w

在与闭路有关的问题中，惩罚函数P使用多个比特来表示选择出的路径在有向图中形成闭路的条件。在有向图中形成闭路的条件如下所述。

第1是关于N个节点的各个节点被选择为最佳路径的、出来的有向边的数量为1以下这样的条件。

第2是关于N个节点的各个节点被选择为最佳路径的、进入的有向边的数量为1以下这样的条件。

第3是关于N个节点的各个节点被选择为最佳路径的、出来的有向边的数量和被选择为最佳路径的进入的有向边的数量相同这样的条件。

第4是从第i个节点出来并进入第j个节点的有向边、和从第j个节点出来并进入第i个节点的有向边不被同时选择为最佳路径这样的条件。

使用多个比特表示以上条件的惩罚函数P如下述的式(4)所示。

【数式3】

式(4)的右边的第1项是将关于任意的i针对j＝j′以外的所有j和j′的组合对b

式(4)的右边的第2项是将关于任意的j针对i＝i′以外的所有i和i′的组合对b

式(4)的右边的第3项的括号内是计算关于任意的i从关于所有j的b

式(4)的右边的第4项是关于所有i和j的组合对b

此外，关于惩罚函数P的所有项的1/2是用于使各项的相对于0的最小偏移量成为1的系数。另外，惩罚函数P只要是使用多个比特来表示满足与闭路有关的最佳路径的制约条件的式子，则也可以是其他式子。例如，惩罚函数P也可以包括使用b

(与闭路有关的问题的数值解析)

本实施方式所涉及的搜索方法通过非专利文献1所示的手法，在数值上求解如以上的包含于0-1最佳化问题的多个比特的值。

在使用非专利文献1所示的手法的情况下，包含于0-1最佳化问题的多个比特与假想的多个粒子对应起来。因此，多个粒子与包含于有向图的多个有向边对应。另外，多个粒子通过0-1最佳化问题表示整体的能量(哈密顿量)。而且，在本实施方式所涉及的搜索方法中，通过利用辛欧拉法在数值上求解多个粒子的运动方程式，计算多个比特的值。

例如，在本实施方式所涉及的搜索方法中，通过利用辛欧拉法在数值上求解下述的式(5)、式(6)、式(7)以及式(8)所示的古典力学的运动方程式，计算与闭路有关的问题的解。

【数式4】

在式(5)～(8)中，t表示时刻。i表示节点的索引，是1以上N以下的整数。j表示节点的索引，是i以外的1以上N以下的整数。w

在式(5)～式(8)中，XR

式(5)表示与从第i个节点出来并进入第j个节点的有向边对应的粒子的位置x

式(6)表示与从第i个节点出来并进入第j个节点的有向边对应的粒子的运动量y

式(7)表示关于第i个节点对与出来的2个以上的有向边对应的2个以上的粒子的位置进行累加的第1累计值。另外，式(8)表示关于第j个节点对与进入的2个以上的有向边对应的2个以上的粒子的位置进行累加的第2累计值。

在本实施方式所涉及的搜索方法中，使用这样的式(5)～式(8)，从初始时刻至结束时刻，按照每个单位时间，对假想的多个粒子各自的位置以及运动量进行时间积分。在该情况下，在本实施方式所涉及的搜索方法中，根据辛欧拉法，交替计算位置和运动量。即，在本实施方式所涉及的搜索方法中，按照每个单位时间，在计算位置之后，计算运动量，或者，在计算运动量之后，计算位置。

另外，粒子的位置被制约成表示对应的比特的第1值(例如0)与对应的比特的第2值(例如1)之间的值的连续值。此外，第2值大于第1值。

因此，在本实施方式所涉及的搜索方法中，按照每个单位时间，关于多个粒子的各个粒子，在位置小于第1值(例如0)的情况下，将位置修正为第1值，在大于第2值的情况下，将位置修正为第2值(例如1)。进而，在本实施方式所涉及的搜索方法中，也可以按照每个单位时间，关于多个粒子的各个粒子，在位置小于第1值或者大于第2值的情况下，将运动量修正为预先决定的值或者通过预先决定的运算决定的值。

而且，在本实施方式所涉及的搜索方法中，通过预先决定的阈值(例如0.5)，对最终时刻下的多个粒子各自的位置进行二值化，作为0-1最佳化问题所包含的多个比特各自的解来输出。此外，参照图5以后的图，说明执行依照这样的搜索方法的处理的具体的装置。

另外，在本实施方式所涉及的搜索方法中，也可以代替式(6)，而使用下述的式(9)，计算与闭路有关的问题的解。

【数式5】

h

p在初始时刻下为0，在最终时刻为1，是每个单位时刻单调增加的值。式(10)表示被编入到式(9)的h

此外，式(9)是对式(6)加上从0向1单调增加的p和依赖于此的式(10)的h

(与连接不同的2个节点之间的路径有关的问题)

与连接不同的2个节点之间的路径有关的问题相比于与闭路有关的问题，惩罚函数P不同。

在与连接不同的2个节点之间的路径有关的问题中，惩罚函数P使用多个比特表示选择出的路径在有向图中形成连接2个节点之间的路径的条件。在有向图中形成闭路的条件如下所述。

第1是关于开始节点被选择为最佳路径的出来的有向边的数量为1、以及关于结束节点被选择为最佳路径的进入的有向边的数量为1这样的条件。

第2是关于开始节点被选择为最佳路径的进入的有向边的数量为0、以及关于结束节点被选择为最佳路径的出来的有向边的数量为0这样的条件。

第3是关于N个节点的各个节点被选择为最佳路径的出来的有向边的数量为1以下这样的条件。

第4是关于N个节点的各个节点被选择为最佳路径的进入的有向边的数量为1以下这样的条件。

第5是关于开始节点以及结束节点以外的N-2个节点的各个节点被选择为最佳路径的出来的有向边的数量、和被选择为最佳路径的进入的有向边的数量相同这样的条件。

第6是从第i个节点出来并进入第j个节点的有向边、和从第j个节点出来并进入第i个节点的有向边没被同时选择为最佳路径这样的条件。

使用多个比特表示以上的条件的惩罚函数P例如编入有下述的式(21-1)、式(21-2)、式(21-3)、式(21-4)、式(21-5)以及式(21-6)。

【数式6】

b

此外，s表示1以上N以下的指定的1个整数。v表示1以上N以下的s以外的指定的1个整数。k表示1以上N以下的整数。

式(21-1)表示关于所有j对b

式(21-2)表示关于所有i对b

式(21-3)表示关于所有j对b

式(21-4)表示关于所有i对b

式(21-5)表示关于除了s以及v以外的所有i对b

式(21-6)表示对b

(与连接不同的2个节点之间的路径有关的问题的数值解析)

在本实施方式所涉及的搜索方法中，通过利用辛欧拉法，在数值上求解下述的式(22)、式(23)、式(24)、式(25)、式(26)以及式(27)所示的古典力学的运动方程式，计算与连接不同的2个节点之间的路径有关的问题的解。

【数式7】

在式(22)～式(27)中，t表示时刻。i表示节点的索引，是1以上N以下的整数。j表示节点的索引，是i以外的1以上N以下的整数。

在式(22)～式(27)中，s表示路径开始节点的索引，是1以上N以下的指定的整数。v表示路径结束节点的索引，是s以外的1以上N以下的指定的整数。k表示节点的索引，是s以及v以外的1以上N以下的整数。l表示节点的索引，是s、v以及k以外的1以上N以下的整数。w

在式(22)～式(27)中，x

在式(22)～式(27)中，XR

式(22)表示与从第i个节点出来并进入第j个节点的有向边对应的粒子的位置x

式(23)表示与从路径开始节点出来并进入第l个节点的有向边对应的粒子的运动量y

式(24)表示与从第k个节点出来并进入路径结束节点的有向边对应的粒子的运动量y

式(25)表示与从第k个节点出来并进入第l个节点的有向边对应的粒子的运动量y

式(26)表示关于第i个节点，对与出来的2个以上的有向边对应的2以上的粒子的位置进行累加的第1累计值。另外，式(27)表示关于第j个节点，对与进入的2个以上的有向边对应的2以上的粒子的位置进行累加的第2累计值。

而且，在本实施方式所涉及的搜索方法中，使用这样的式(22)～式(27)，与闭路的情况的最佳化问题同样地，求解与连接不同的2个节点之间的路径有关的问题。

但是，在本实施方式所涉及的搜索方法中，将x

此外，x

另外，在本实施方式所涉及的搜索方法中，也可以代替式(23)、式(24)以及式(25)，使用下述的式(28)、式(29)以及式(30)，计算与连接不同的2个节点之间的路径有关的问题的解。

【数式8】

p是在初始时刻下为0，在最终时刻为1，是按照每个单位时刻单调增加的值。

此外，下述的式(31)表示编入到式(28)的h

【数式9】

h

h

h

式(28)是对式(23)加上时间变化参数的式子。式(29)是对式(24)加上时间变化参数的式子。式(30)是对式(25)加上时间变化参数的式子。时间变化参数是以将初始时刻下的运动量的时间微分值设为0、在结束时刻在式(28)(29)(30)的右边使不依赖于粒子的位置x的项即h成为0的方式按照每个单位时间变化的值。

(搜索装置10)

图5是示出第1实施方式所涉及的搜索装置10的结构的图。第1实施方式所涉及的搜索装置10具备运算部12、输入部14、输出部16以及设定部18。

运算部12通过例如信息处理装置来实现。另外，运算部12也可以通过CPU(CentralProcessing Unit，中央处理单元)等1个或者多个处理电路执行程序来实现。另外，运算部12也可以通过FPGA(Field Programmable Gate Array)、门阵列或者面向特定用途的集成电路(ASIC)等实现。

运算部12使作为表示时刻的参数的t从开始时刻(例如0)逐次增加单位时间。运算部12通过从初始时刻至结束时刻按照每个单位时间进行时间积分，计算假想的多个粒子各自的位置以及运动量。然后，运算部12通过利用预先设定的阈值对结束时刻下的多个粒子各自的位置进行二值化，计算0-1最佳化问题所包含的多个比特各自的解。

输入部14在利用运算部12进行的运算处理以前，取得开始时刻下的多个粒子各自的位置以及运动量，提供给运算部12。输出部16在利用运算部12进行的运算处理结束以后，从运算部12取得0-1最佳化问题所包含的多个比特各自的解。然后，输出部16输出取得的解。设定部18在利用运算部12进行的运算处理以前，针对运算部12设定各参数。

图6是示出第1实施方式所涉及的搜索装置10的处理流程的流程图。搜索装置10的运算部12依照图6所示的流程图，执行处理。

首先，在S11中，运算部12对参数进行初始化。更具体而言，运算部12对t、p以及h

接下来，运算部12直至t大于T为止，反复S13至S18的处理(S12与S19之间的循环处理)。T表示结束时刻。由此，运算部12能够从初始时刻至结束时刻，按照每个单位时间反复S13至S18的处理。

在S13中，运算部12关于多个粒子的各个粒子，根据比对象时刻提前1个单位时间的前一时刻下的运动量(y

【数式10】

x

式(41)的右边的x

接下来，在S14中，运算部12关于多个粒子的各个粒子，在对象时刻下的位置(x

在比特中的、表示对应的有向边未被选择的值是0的情况下，第1值是0。在比特中的、表示对应的有向边被选择的值是1的情况下，第2值是1。例如，运算部12在对象时刻下的位置(x

另外，关于多个粒子的各个粒子，当对象时刻下的位置(x

接下来，在S15中，运算部12关于有向图所包含的多个节点的各个节点，计算与出来的2个以上的有向边对应的、对2个以上的粒子在对象时刻下的位置(x

【数式11】

式(42)表示关于除了i以外的所有j对x

接下来，在S16中，运算部12关于有向图所包含的多个节点的各个节点，计算与进入的2个以上的有向边对应的、对2个以上的粒子在对象时刻下的位置(x

【数式12】

式(43)表示关于除了j以外的所有i对x

接下来，在S17中，运算部12关于多个粒子的各个粒子，计算对象时刻下的运动量(y

更具体而言，运算部12通过下述的式(44)，计算对应的粒子在对象时刻下的运动量(y

【数式13】

此外，式(44)的右边的y

此外，在与闭路有关的问题的情况下，运动量的时间微分值(y

另外，在与闭路有关的问题的情况下，在S17中，运算部12也可以关于多个粒子的各个粒子，用下述的式(45)以及式(46)的2个阶段，计算对象时刻下的运动量(y

【数式14】

y

【数式15】

y

式(45)的h

【式16】

此外，在该情况下，运算部12也可以在仅接着式(45)的运算处理、S13的处理的之后执行。

接下来，在S18中，运算部12更新参数。更具体而言，运算部12对t、p以及h

例如，运算部12对t加上单位时间(dt)。在开始时刻是0、结束时刻是T并且反复N

接下来，在S19中，运算部12判断t是否超过结束时刻、即t是否大于T。运算部12在t未超过结束时刻的情况下，使处理返回到S13，执行S13至S18的处理。运算部12在t超过结束时刻的情况下，使处理进入到S20。

在S20中，运算部12通过预先设定的阈值，对结束时刻下的多个粒子各自的位置(x

如以上所述，搜索装置10能够高速地输出搜索有向图的最佳路径的最佳路径问题的解。例如，搜索装置10能够高速地输出与闭路有关的问题的解、以及与连接不同的2个节点之间的路径有关的问题的解。

(第2实施方式)

将第2实施方式所涉及的搜索装置10电路化而安装成FPGA、门阵列或者面向特定用途的集成电路等半导体装置。以下，说明第2实施方式所涉及的搜索装置10。

此外，第2实施方式所涉及的搜索装置10通过搜索包括N个节点的有向图，检测探测汇兑的套利的机会的套利问题的解。

图7是示出第2实施方式所涉及的搜索装置10的电路结构的图。第2实施方式所涉及的搜索装置10具备存储器21、控制电路22、第1电路23、第2电路24、二值化电路25以及标准化电路26。第1电路23包括TE电路31(自演进电路)、GC电路32(累计值计算电路)、以及CC电路33(成本计算电路)。另外，第2电路24包括MX电路34(多体相互作用电路)。

此外，搜索装置10也可以是不具备标准化电路26的结构。另外，第1电路23也可以是不包括CC电路33的结构。

存储器21存储多个位置变量、多个运动量变量、多个权重值、多个不可选择标志、多个第1累计值、多个第2累计值、多个反转位置变量、以及最大绝对值。

多个位置变量与有向标志所包含的多个有向边对应。多个位置变量分别表示与对应的有向边对应起来的粒子的位置。

多个运动量变量与多个有向边对应。多个运动量变量分别表示与对应的有向边对应起来的粒子的运动量。

多个权重值与多个有向边对应。多个权重值分别被分配给对应的有向边。多个权重值在利用第1电路23以及第2电路24进行的运算处理以前，从外部装置写入到存储器21。

多个不可选择标志与多个有向边对应。多个不可选择标志表示对应的有向边可选择或者不可选择为路径。多个不可选择标志例如在是0的情况下，表示对应的有向边可选择为路径，在1的情况下，表示对应的有向边不可选择为路径。通过有向图，预先决定有向边可选择或者不可选择为路径。多个不可选择标志在利用第1电路23以及第2电路24进行的运算处理以前，从外部装置写入到存储器21。

多个第1累计值与多个节点对应。多个第2累计值与多个节点对应。

多个反转位置变量与多个有向边对应。多个反转位置变量分别与多个位置变量相同，但开始节点和结束节点的对应关系被反转进行储存。

最大绝对值是标准化前的多个权重值的绝对值中的最大值。

控制电路22与存储器21、第1电路23、第2电路24、二值化电路25以及标准化电路26连接。控制电路22控制从初始时刻至结束时刻按照每个单位时间对与多个有向边的各个对应的位置变量以及运动量变量进行时间积分的运算。例如，控制电路22进行单位时间的管理、反复处理的管理以及参数的更新等。TE电路31以及MX电路34根据控制电路22的控制，关于多个有向边的各个，执行按照每个单位时间对位置变量以及运动量变量进行时间积分的运算。另外，控制电路22在运算处理以前，对存储于存储器21的多个位置变量以及多个运动量变量进行初始化。

TE电路31与存储器21连接。TE电路31按照每个单位时间访问存储器21，执行TE处理。

更详细而言，TE电路31按照每个单位时间，关于多个有向边的各个有向边，根据对应的有向边在比对象时刻提前1个单位时间的前一时刻下的位置变量以及运动量变量，更新对应的有向边在对象时刻下的位置变量。由此，TE电路31能够关于多个有向边的各个有向边，按照每个单位时间，对位置变量进行时间积分。

另外，TE电路31关于多个有向边的各个有向边，按照每个单位时间，根据前一时刻下的运动量变量、对应的有向边在对象时刻下的位置变量以及对对应的有向边分配的权重值，更新对应的有向边在对象时刻下的运动量变量。由此，TE电路31能够关于多个有向边的各个有向边，按照每个单位时间，将运动量变量的时间积分的运算执行至中途阶段。

进而，TE电路31按照每个单位时间，关于多个有向边的各个有向边，当对应的有向边在对象时刻下的位置变量小于预先决定的第1值的情况下，将对象时刻下的位置变量修正为第1值，在大于预先决定的第2值的情况下，将对象时刻下的位置变量修正为第2值。此外，第2值大于第1值。例如，TE电路31按照每个单位时间，关于多个有向边的各个有向边，当对应的有向边在对象时刻下的位置变量小于0的情况下，将对象时刻下的位置变量修正为0，在大于1的情况下，将对象时刻下的位置变量修正为1。

进而，TE电路31按照每个单位时间，关于多个有向边的各个有向边，当对象时刻下的位置变量小于第1值(例如0)或者大于第2值(例如1)的情况下，将前一时刻下的运动量变量修正为预先决定的值或者通过预先决定的运算决定的值。预先决定的值是例如是0或者0至1的任意值。通过预先决定的运算决定的值也可以是例如0至1的范围的通过随机数决定的值。

进而，TE电路31关于多个有向边的各个有向边，在对应的有向边的不可选择标志表示不可选择的情况下，将对象时刻下的位置变量、以及直至中途阶段更新后的对象时刻下的运动量变量置换为预先决定的值(例如0)。

GC电路32与存储器21连接。GC电路32按照每个单位时间访问存储器21，执行GC处理。

更详细而言，GC电路32按照每个单位时间，关于有向图所包含的多个节点分别计算与出来的2个以上的有向边对应的、对2个以上的对象时刻下的位置变量进行累加的第1累计值。进而，GC电路32按照每个单位时间，关于多个节点分别计算与进入的2个以上的有向边对应的、对2个以上的对象时刻下的位置变量进行累加的第2累计值。此外，GC电路32也可以不经由存储器21而从TE电路31取得对象时刻下的位置变量。

CC电路33与存储器21连接。CC电路33按照每个单位时间访问存储器21，执行CC处理。

更详细而言，CC电路33通过按照每个单位时间，利用预先设定的阈值对与多个有向边分别对应的位置变量进行二值化，从而关于多个有向边分别判定是否在对象时刻的阶段中被选择为最佳路径。接下来，CC电路33按照每个单位时间判定在对象时刻的阶段中被选择为最佳路径的2个以上的有向边是否满足最佳路径的制约条件。然后，CC电路33在满足制约条件的情况下，计算将对选择的2个以上的有向边分配的权重值合成而得的权重的合计值。例如，CC电路33在满足制约条件的情况下，计算针对对选择的2个以上的有向边分配的权重值进行加法的加法值。

进而，CC电路33根据对选择的2个以上的有向边分配的权重值的合计值，计算在进行与2个以上的有向边对应的交换的情况下得到的总体率(sol)。CC电路33将计算出的总体率(sol)输出给外部装置。

MX电路34与存储器21连接。MX电路34按照每个单位时间，访问存储器21，执行MX处理。

更详细而言，MX电路34关于多个有向边的各个有向边，按照每个单位时间根据对应的有向边在对象时刻下的位置变量、以及对应的有向边以外的有向边在对象时刻下的位置变量，还更新对应的有向边在对象时刻下的运动量变量。更详细而言，MX电路34按照每个单位时间，关于多个有向边的各个有向边，根据结束节点的第1累计值以及第2累计值、开始节点的第1累计值以及第2累计值、对应的有向边在对象时刻下的位置变量、以及与和对应的有向边相反朝向的有向边对应的对象时刻下的位置变量，还更新由TE电路31更新后的对应的有向边在对象时刻下的运动量变量。由此，MX电路34关于多个有向边的各个有向边，能够将由TE电路31时间积分至中途阶段的运动量变量时间积分至最后的阶段。

二值化电路25与存储器21连接。二值化电路25从存储器21读出与结束时刻下的多个有向边的各个有向边对应的位置变量。二值化电路25通过利用预先设定的阈值对与结束时刻下的多个有向边分别对应的位置变量进行二值化，计算0-1最佳化问题所包含的多个比特各自的解。然后，二值化电路25输出0-1最佳化问题所包含的多个比特各自的解。

标准化电路26与存储器21连接。标准化电路26在从外部装置向存储器21写入多个权重值的情况下，在利用第1电路23以及第2电路24进行的运算处理以前，针对多个权重值分别执行标准化处理。更具体而言，标准化电路26根据多个权重值中的最大绝对值，对多个权重值的各个权重值进行标准化，将标准化后的多个权重值写入到存储器21。另外，标准化电路26将最大绝对值写入到存储器21。

另外，标准化电路26在作为最佳路径搜索闭路的情况下，在标准化处理以前，执行校正处理。标准化电路26在权重的合计值是对选择出的路径所包含的2个以上的有向边分配的2个以上的权重值的加法值的情况下，作为校正处理，关于多个有向边的各个有向边，对对应的权重值加上对结束节点设定的系数，然后减去对开始节点设定的系数。此外，对多个节点的各个节点预先设定系数。以使校正后的权重值相对于0的误差的总和成为最小的方式，决定与多个节点的各个节点对应地设定的系数。

图8是示出存储器21的结构的图。存储器21包括X存储器电路41、Y存储器电路42、W存储器电路43、Z存储器电路44、XR存储器电路45、XC存储器电路46、XT存储器电路47以及最大值存储器电路48。X存储器电路41、Y存储器电路42、W存储器电路43、Z存储器电路44、XR存储器电路45、XC存储器电路46、XT存储器电路47以及最大值存储器电路48分别具有读出端口以及写入端口，相互独立地进行数据的读出以及写入。

X存储器电路41存储位置矩阵(X

此外，有向图不包括自循环的有向边(从第i个节点出来并进入第i个节点的有向边)。因此，在位置矩阵中，作为行编号和列编号相同的对角分量的要素，储存有对路径搜索不造成影响的值即0。

Y存储器电路42存储运动量矩阵(Y

W存储器电路43存储权重值矩阵(W

Z存储器电路44存储标志矩阵(Z

XR存储器电路45存储第1累计值数组(XR

XC存储器电路46存储第2累计值数组(XC

XT存储器电路47存储反转位置矩阵(XT

最大值存储器电路48存储标准化前的多个权重值的最大绝对值(absmax)。

图9是示出搜索装置10的处理流程的流程图。第2实施方式所涉及的搜索装置10根据图9所示的流程，执行处理。

首先，在S31中，标准化电路26执行标准化处理以及校正处理。此外，在针对存储于存储器21的多个权重值已经执行标准化处理以及校正处理的情况下，标准化电路26不执行S31的处理。

接下来，在S32中，控制电路22对参数(p)进行初始化。p在初始时刻是0。进而，控制电路22将存储于存储器21具备的X存储器电路41的多个位置变量初始化为任意的值。另外，进而，控制电路22将存储于存储器21具备的Y存储器电路42的多个运动量变量初始化为任意的值。

接下来，在S33中，TE电路31执行TE处理。接下来，在S34中，GC电路32执行GC处理。接下来，在S35中，CC电路33执行CC处理。TE电路31、GC电路32以及CC电路33针对N×N个有向边的每一个，反复执行S33、S34以及S35的处理。S33、S34以及S35的循环处理(第1循环)在第1电路23内完成执行。在S36中，控制电路22在S33以及S34的处理被执行N×N次的情况下(S36为“是”)，使处理进入到S37。此外，控制电路22也可以即使S35的处理未全部结束，也使处理进入到S37。在该情况下，S35的处理和S37的处理并行地执行。

在S37中，MX电路34执行MX处理。MX电路34针对N×N个有向边的每一个，反复执行S37的处理。S37的循环处理(第2循环)在第2电路24内完成执行。在S38中，控制电路22在S37的处理被执行N×N次的情况下(S37为“是”)，使处理进入到S39。

在S39中，控制电路22更新参数(p)。控制电路22、第1电路23以及第2电路24将S33至S39的处理(第3循环)反复执行预定步骤次数。

第1电路23在将S33至S39的处理(第3循环)执行1次的情况下，能够以单位时间对位置变量进行时间积分。另外，第1电路23以及第2电路24在将S33至S39的处理(第3循环)执行1次的情况下，能够以单位时间对运动量变量进行时间积分。然后，第1电路23在将S33至S39的处理(第3循环)执行预定步骤次数的情况下，能够从初始时刻至结束时刻，对位置变量以及运动量变量进行时间积分。

在S40中，控制电路22在S33至S39的处理被反复预先决定的步骤次数的情况下(S40的“是”)，使处理进入到S41。

在S41中，二值化电路25计算0-1最佳化问题所包含的多个比特各自的解。然后，二值化电路25输出0-1最佳化问题所包含的多个比特各自的解。搜索装置10例如按照每一定期间，反复执行S31至S41的处理。

图10是示出对TE电路31输入以及从TE电路31输出的变量以及值的图。TE电路31针对N×N个有向边的每一个，从存储器21读出对应的有向边的位置变量(X

图11是示出对GC电路32输入输出的变量的图。在由TE电路31进行TE处理之后，GC电路32按照N×N个有向边的每一个，从存储器21，读出对应的有向边的位置变量(X

GC电路32每当针对1行的位置变量执行TE处理时，生成对应的节点的第1累计值(XR

图12是示出对CC电路33输入以及从CC电路33输出的变量以及值的图。在由TE电路31进行TE处理之后，CC电路33针对N×N个有向边的每一个，从存储器21读出对应的有向边的位置变量(X

CC电路33通过针对N×N个所有有向边执行CC处理，计算权重值的合计值。然后，CC电路33根据对选择的2个以上的有向边分配的权重值的合计值，计算在进行与2个以上的有向边对应的交换的情况下得到的总体率(sol)，输出到外部。

图13是示出对MX电路34输入以及从MX电路34输出的变量以及值的图。MX电路34针对N×N个有向边的每一个，从存储器21读出对应的有向边的位置变量(X

图14是示出利用TE电路31的变量以及值的读出顺序的图。

TE电路31按照行方向的光栅扫描顺序，从存储于X存储器电路41的位置矩阵(X

另外，TE电路31按照每个时钟循环，从存储于Y存储器电路42的运动量矩阵(Y

然后，TE电路31通过流水线处理，生成同一行编号以及列编号的更新后的位置变量(x

图15是示出利用MX电路34的变量以及值的读出顺序的图。

MX电路34按照行方向的光栅扫描顺序，从存储于X存储器电路41的位置矩阵(X

另外，MX电路34按照每个时钟循环，从存储于Y存储器电路42的运动量矩阵(Y

另外，MX电路34按照每个时钟循环，从存储于XR存储器电路45的第1累计值数组(XR

然后，MX电路34通过流水线处理，生成更新后的运动量变量(y

图16是示出TE处理、MX处理以及GC处理的定时的图。搜索装置10将TE处理、MX处理以及GC处理反复执行预定步骤次数。

TE电路31针对每个有向边，依次从存储器21读出前一时刻下的位置变量以及运动量变量等，针对每个有向边依次计算对象时刻下的位置变量以及更新途中的对象时刻下的运动量变量，写入到存储器21。因此，从TE电路31读出开头的位置变量(1行1列的位置变量(X

MX电路34针对每个有向边，依次从存储器21读出对象时刻下的位置变量以及更新途中的对象时刻下的运动量变量等，针对每个有向边依次计算更新后的对象时刻下的运动量变量，写入到存储器21。因此，从MX电路34读出开头的位置变量(1行1列的位置变量(X

GC电路32从TE电路31或者存储器21，针对每个有向边依次取得对象时刻下的位置变量，针对每个节点依次计算第1累计值以及第2累计值，写入到存储器21。GC电路32也同样地执行流水线处理。GC电路32中的流水线延迟是λ

在此，GC电路32能够与TE处理并行地执行GC处理。但是，GC电路32在TE电路31输出开头的位置变量(1行1列的位置变量(X

MX电路34在TE处理以及GC处理完成之后，执行MX处理。即，MX电路34以与TE电路31执行TE处理的期间不重复的方式，执行MX处理。换言之，TE电路31以与MX电路34执行MX处理的期间不重复的方式，执行TE处理。同样地，MX电路34以与GC电路32执行GC处理的期间不重复的方式，执行MX处理。换言之，GC电路32以与MX电路34执行MX处理的期间不重复的方式，执行GC处理。因此，MX电路34在GC电路32执行GC处理之后、即在从TE处理结束起经过λ

CC电路33也执行流水线处理。CC电路33中的流水线延迟是λ

CC电路33能够与TE处理并行地执行CC处理。另外，MX电路34即使CC处理未完成也能够执行MX处理。因此，CC电路33只要能够在至少MX处理完成以前完成CC处理，则也可以与MX处理并行地执行CC处理。

以上，利用搜索装置10的1次的步骤的处理时间成为{2(N×N)+λ

图17是示出TE电路31的结构的图。

TE电路31按照每个时钟循环，取得在前一步骤中计算出的前一时刻下的位置变量(x

另外，TE电路31按照每个时钟循环，输出TE处理后的对象时刻下的位置变量(x

TE电路31包括位置更新电路51、限制电路52、运动量更新电路53以及掩蔽电路54。

位置更新电路51包括FY电路57和第1加法器58。

FY电路57按照每个时钟循环，取得前一时刻下的运动量变量(y

dx＝FY(y

第1加法器58按照每个时钟循环，取得前一时刻下的位置变量(x

nx1＝x

位置更新电路51按照每个时钟循环，输出对象时刻下的位置变量(nx1)。另外，位置更新电路51按照每个时钟循环，将前一时刻下的运动量变量(y

这样的位置更新电路51关于多个有向边的各个有向边，能够根据前一时刻下的位置变量以及运动量变量，计算对应的有向边在对象时刻下的位置变量。因此，位置更新电路51关于多个有向边的各个有向边能够以单位时间对位置变量进行积分。

限制电路52包括第1多路复用器60、第1比较器61、第2多路复用器62、第3多路复用器63以及第2比较器64。

第1多路复用器60根据第1比较器61的控制，选择+1或者0作为对象时刻下的位置变量(nx2)来输出。第1比较器61按照每个时钟循环，判断从位置更新电路51输出的对象时刻下的位置变量(nx1)是否大于0.5。第1比较器61在nx1大于0.5的情况下，从第1多路复用器60输出+1，在nx1是0.5以下的情况下，从第1多路复用器60输出0。

第2多路复用器62根据第2比较器64的控制，选择从位置更新电路51输出的对象时刻下的位置变量(nx1)或者从第1多路复用器60输出的对象时刻下的位置变量(nx2)，作为对象时刻下的位置变量(nx3)输出。

第3多路复用器63根据第2比较器64的控制，选择从位置更新电路51输出的前一时刻下的运动量变量(ny1)或者0，作为前一时刻下的运动量变量(ny2)输出。

第2比较器64按照每个时钟循环，判断从位置更新电路51输出的对象时刻下的位置变量(nx1)是否大于1或者小于0、或者、从位置更新电路51输出的对象时刻下的位置变量(nx1)是0以上1以下。

第2比较器64在nx1是0以上1以下的情况下，使第2多路复用器62选择从位置更新电路51输出的对象时刻下的位置变量(nx1)，作为对象时刻下的位置变量(nx3)输出。进而，第2比较器64在nx1是0以上1以下的情况下，使第3多路复用器63选择从位置更新电路51输出的前一时刻下的运动量变量(ny1)，作为前一时刻下的运动量变量(ny2)输出。

第2比较器64在nx1大于1或者小于0的情况下，使第2多路复用器62选择从第1多路复用器60输出的对象时刻下的位置变量(nx2)，作为对象时刻下的位置变量(nx3)输出。进而，第2比较器64在nx1大于1或者小于0的情况下，使第3多路复用器63选择0，作为前一时刻下的运动量变量(ny2)输出。

这样的限制电路52按照每个单位时间，关于多个有向边的各个有向边，当对应的有向边在对象时刻下的位置变量小于0的情况下，能够将对象时刻下的位置变量修正为0，当大于1的情况下，能够将对象时刻下的位置变量修正为1。进而，限制电路52关于多个有向边的各个有向边，当对象时刻下的位置变量小于0或者大于1的情况下，能够将前一时刻下的运动量变量修正为0。

运动量更新电路53包括FX电路65、FW电路66以及第2加法器67。

FX电路65按照每个时钟循环，取得从限制电路52输出的对象时刻下的位置变量(nx3)。FX电路65按照每个时钟循环，针对对象时刻下的位置变量(nx3)执行式(63)的运算，从而计算第1运动量更新量(dy1)。

dy1＝FX(nx3)＝-dt×(1-p)×(nx3-x

此外，p是按照每个单位时间而单调增加的参数，在初始时刻为0，在结束时刻为1。x

FW电路66按照每个时钟循环，取得权重值(w

dy2＝FW(w

此外，w

w

M

第2加法器67按照每个时钟循环，取得从限制电路52输出的前一时刻下的运动量变量(ny2)、FX电路65输出的第1运动量更新量(dy1)以及FW电路66输出的第2运动量更新量(dy2)。第2加法器67按照每个时钟循环，如式(66)所示，对前一时刻下的位置变量(ny2)、第1运动量更新量(dy1)以及第2运动量更新量(dy2)进行加法，从而输出对象时刻下的运动量变量(ny3)。

ny3＝ny2+dy1+dy2…(66)

运动量更新电路53按照每个时钟循环，输出对象时刻下的运动量变量(ny3)。

这样的运动量更新电路53关于多个有向边的各个有向边，能够根据前一时刻下的运动量变量、对应的有向边在对象时刻下的位置变量以及对对应的有向边分配的权重值，计算对应的有向边在对象时刻下的运动量变量。由此，运动量更新电路53关于多个有向边的各个有向边，能够将运动量变量的单位时间的积分运算执行至中途阶段。

掩蔽电路54包括第4多路复用器68和第5多路复用器69。

第4多路复用器68按照每个时钟循环，取得不可选择标志(z

第5多路复用器69按照每个时钟循环，取得不可选择标志(z

这样的掩蔽电路54关于多个有向边的各个有向边，在对应的有向边的不可选择标志表示不可选择的情况下，能够将对象时刻下的位置变量以及对象时刻下的运动量变量置换为作为预先决定的值的0。

图18是将GC电路32的结构与XR存储器电路45以及XC存储器电路46一起示出的图。图19是示出利用GC电路32的位置变量的取得顺序以及第1累计值以及第2累计值的计算顺序的图。

GC电路32按照每个时钟循环，取得对象时刻下的位置变量(x

GC电路32包括行方向累加电路71(ACC(r))、N个第6多路复用器72、N个第3比较器73、以及N个列方向累加电路74(ACC(c))。

行方向累加电路71按照每个时钟循环，取得TE处理后的位置变量(x

行方向累加电路71将计算出的累加值针对每行(针对每N时钟循环)作为第1累计值(xr

N个第6多路复用器72与N个列对应起来。N个第6多路复用器72的各个第6多路复用器72按照每个时钟循环，取得位置变量(x

N个第3比较器73与N个列对应起来。N个第3比较器73的各个第3比较器73按照每个时钟循环，判断取得的位置变量(x

N个列方向累加电路74与N个列对应起来。N个列方向累加电路74的各个列方向累加电路74对从对应的第6多路复用器72输出的所有位置变量(N×N时钟循环量的位置变量(x

N个列方向累加电路74的各个列方向累加电路74将计算出的累加值作为对应的列的第2累计值(xc

图20是示出MX电路34的结构的图。

MX电路34按照每个时钟循环，取得TE处理后的位置变量(x

然后，MX电路34按照每个时钟循环，输出MX处理后的对象时刻下的运动量变量(y

MX电路34包括FM电路77和第3加法器78。

FM电路77包括第1乘法器79、第2乘法器80、第3乘法器81、第1减法器82、第2减法器83、第3减法器84、第1内部加法器85、第2内部加法器86以及第4乘法器87。

第1乘法器79对第1累计值(xri

第1减法器82从第1乘法器79的输出值(2×(xri

第1内部加法器85对第1减法器82的输出值和第2减法器83的输出值进行加法运算。第2内部加法器86对第1内部加法器85的输出值和第3减法器84的输出值进行加法运算。第4乘法器87对第2内部加法器86的输出值乘以dt×M

这样的FM电路77按照每个时钟循环，执行式(67)的运算，从而计算第3运动量更新量(dy3)。

dy3＝dt×M

第3加法器78按照每个时钟循环，取得TE次处理后的运动量变量(y

y

这样的MX电路34关于多个有向边的各个有向边，能够根据结束节点的第1累计值以及第2累计值、开始节点的第1累计值以及第2累计值、对应的有向边在对象时刻下的位置变量、以及与和对应的有向边相反朝向的有向边对应的对象时刻下的位置变量进一步更新由TE电路31更新后的对应的有向边在对象时刻下的运动量变量。由此，MX电路34关于多个有向边的各个有向边，能够针对由TE电路31时间积分至中途阶段的运动量变量，将单位时间量的积分进行至最后的阶段。

图21是示出标准化电路26的结构的图。标准化电路26在从外部装置对存储器21写入多个权重值(w

标准化电路26包括误差最小化部90和最大值调整部91。

误差最小化部90在将从第i个节点出来并进入第j个节点的交换率设为r

在计算套利问题的解的情况下，搜索装置10搜索闭路作为最佳路径。因此，在针对对闭路所包含的有向边分配的所有交换率进行乘法运算的情况下，a被取消，所以即使进行这样的校正，最佳路径的权重的合计值也不变化。

另外，在r

w′

【数式17】

α

式(71)成为最小的α

【数式18】

误差最小化部90关于预先计算的多个节点的各个节点，预先设定系数(a

最大值调整部91取得由误差最小化部90校正后的多个权重值。最大值调整部91根据多个权重值的最大绝对值(absmax)，对多个权重值分别进行标准化。

更详细而言，最大值调整部91从校正后的多个权重值检测最大绝对值(absmax)。然后，最大值调整部91将校正后的多个权重值除以最大绝对值(absmax)。由此，最大值调整部91能够以使最大绝对值成为1的方式，对多个权重值进行标准化。

标准化电路26将由最大值调整部91标准化后的多个权重值(w

这样的标准化电路26通过对多个权重值进行标准化，能够高精度地计算权重的合计值。

图22是示出CC电路33的结构的图。

CC电路33按照每个时钟循环，取得对象时刻下的位置变量(x

CC电路33按照每个时钟循环，取得与位置变量(x

CC电路33包括第7多路复用器101、第4比较器102、第8多路复用器103、第1累加器104、第9多路复用器105、第5比较器106、N个第10多路复用器107、N个第6比较器108、N个第2累加器109、N个第11多路复用器110、N个第7比较器111、N个第3累加器112、第12多路复用器113、判定电路114、以及幂乘电路115。

第7多路复用器101按照每个时钟循环，根据第4比较器102的控制，输出0或者1。

第4比较器102按照每个时钟循环，取得位置变量(x

第8多路复用器103按照每个时钟循环，根据从第7多路复用器101输出的比特(b)，输出权重值(w

第1累加器104按照每个时钟循环，对从第8多路复用器103输出的权重值进行累加。更详细而言，第1累加器104对权重值进行与从1行1列至N行N列的N×N时钟循环量相应的累加。此外，第8多路复用器103将不包含于最佳路径的有向边的权重值作为0输出。因此，第1累加器104能够对与被选择为最佳路径的所有有向边对应的权重值进行累加。即，第1累加器104能够生成被选择为最佳路径的所有有向边的权重的合计值。第1累加器104在1行1列至N行N列的N×N时钟循环的处理完成之后，将权重值的累加值作为权重的合计值(cost)输出。

第9多路复用器105按照每个时钟循环，取得从第7多路复用器101输出的比特(b)。第9多路复用器105根据第5比较器106的控制，输出比特(b)或者0。

第5比较器106按照每个时钟循环，取得位置变量(x

N个第10多路复用器107与N个行对应起来。N个第10多路复用器107的各个第10多路复用器107按照每个时钟循环，取得从第9多路复用器105输出的比特(b)。N个第10多路复用器107的各个第10多路复用器107根据对应的第6比较器108的控制，输出取得的比特(b)或者0。

N个第6比较器108与N个行对应起来。N个第6比较器108的各个第6比较器108按照每个时钟循环，判断取得的比特(b)的行编号是否为对应的行。N个第6比较器108的各个第6比较器108在取得的比特(b)的行编号是对应的行的情况下，使对应的第10多路复用器107输出比特(b)。N个第6比较器108的各个第6比较器108在取得的比特(b)的行编号并非对应的行的情况下，使对应的第10多路复用器107输出0。

N个第2累加器109与N个行对应起来。N个第2累加器109的各个第2累加器109对从对应的第10多路复用器107输出的所有比特(N×N时钟循环量的比特(b))进行累加。N个第10多路复用器107的各个第10多路复用器107将对应的行以外的位置变量作为0输出。因此，N个第2累加器109的各个第2累加器109在取得包含于对应的行的比特(b)的时钟循环中，对比特(b)进行累加。由此，N个第2累加器109的各个第2累加器109能够输出对包含于对应的行的N个比特(b)进行累加而得到的行方向累加值(xr_b[k])。此外，k是1至N的任意的整数。

N个第11多路复用器110与N个列对应起来。N个第11多路复用器110的各个第11多路复用器110按照每个时钟循环，取得从第9多路复用器105输出的比特(b)。N个第11多路复用器110的各个第11多路复用器110根据对应的第7比较器111的控制，输出取得的比特(b)或者0。

N个第7比较器111与N个列对应起来。N个第7比较器111的各个第7比较器111按照每个时钟循环，判断取得的比特(b)的列编号是否为对应的列。N个第7比较器111的各个第7比较器111在取得的比特(b)的列编号是对应的列的情况下，使对应的第11多路复用器110输出比特(b)。N个第7比较器111的各个在取得的比特(b)的列编号并非对应的列的情况下，使对应的第11多路复用器110输出0。

N个第3累加器112与N个列对应起来。N个第3累加器112的各个第3累加器112对从对应的第11多路复用器110输出的所有比特(N×N时钟循环量的比特(b))进行累加。N个第11多路复用器110的各个第11多路复用器110将对应的列以外的位置变量作为0输出。因此，N个第3累加器112的各个第3累加器112在取得包含于对应的列的比特(b)的时钟循环中，对比特(b)进行累加。由此，N个第3累加器112的各个第3累加器112能够输出对包含于对应的列的N个比特(b)进行累加而得到的列方向累加值(xc_b[k])。

第12多路复用器113在1行1列至N行N列的N×N时钟循环的处理完成之后，根据由判定电路114实施的控制，输出从第1累加器104输出的权重的合计值(cost)或者0。

判定电路114在1行1列至N行N列的N×N时钟循环的处理完成之后，根据N个行方向累加值(xr_b[k])以及N个列方向累加值(xc_b[k])，判定最佳路径是否为闭路。

判定电路114例如在满足式(81)的情况下，判定为未形成闭路，在不满足式(81)的情况下，判定为形成闭路。

【数式19】

if((xr_b

(xr_b[k]>1)在N个行方向累加值(xr_b[k])中的至少1个大于1的情况(即是2以上的情况)下，意味着未形成闭路。

(xc_b[k]>1)在N个列方向累加值(xc_b[k])中的至少1个大于1的情况(即是2以上的情况)下，意味着未形成闭路。

(xr_b[k]！＝xc_b[k])在行编号以及列编号相同的行方向累加值(xr_b[k])和列方向累加值(xc_b[k])不同的情况下，意味着未形成闭路。

判定电路114在判定为最佳路径是闭路的情况下，使得从第12多路复用器113输出权重的合计值(cost)。判定电路114在判定为最佳路径并非闭路的情况下，使得从第12多路复用器113输出0。

幂乘电路115在1行1列至N行N列的N×N时钟循环的处理完成之后，执行下述的式(82)的运算。

【数式20】

sol＝10

即，对权重的合计值(cost)和最大绝对值(absmax)进行乘法而得到的值乘以-1，幂乘电路115针对由此得到的值进行设为10的指数的幂乘运算。由此，幂乘电路115能够计算在进行与包含于最佳路径的2个以上的有向边对应的交换的情况下得到的总体率(sol)。

(伪代码)

图23是示出第1主伪代码1111的图。图24是示出接着第1主伪代码1111的第2主伪代码1112的图。作为一个例子，搜索装置10按照行编号的顺序，执行图23以及图24所示的伪代码。

10行是对p以及ph代入0的代码。

11行是使从11行至58行反复的代码。11行是在最初的循环中对ncycle代入1、每个循环对ncycle加上1、以ncycle是Ncycle以下为条件而执行反复的处理的代码。

12行、13行是使对p加上dp并对ph加上dph的处理执行的代码群。14行是对cost代入0的代码。15行以及16行是对数组xr_b[node]以及数组xc_b[node]代入0的代码群。

17行是使从17行至48行反复的代码。17行是在最初的循环中对i代入0、每个循环对i加上1、以i小于node为条件执行反复的处理的代码。

18行是使从18行至47行反复的代码。18行是在最初的循环中对j代入0、每个循环对j加上1、以j小于node为条件执行反复的处理的代码。

19行是定义xout以及yout的代码。

21行是调出并执行TE函数的代码。TE函数是执行TE处理的函数。21行是将X[i][j]、Y[i][j]、w[i][j]、z[i][j]交给TE函数并从TE函数接收xout以及yout的代码。X[i][j]是i行j列的位置变量。Y[i][j]是i行j列的运动量变量。w[i][j]是i行j列的权重值。z[i][j]是i行j列的不可选择标志。

23行、24行以及25行是将xout储存到X[i][j]、将xout储存到XT[j][i]、将yout储存到Y[i][j]的代码群。XT[j][i]是j行i列的反转位置变量。

27行以及28行是使GC处理执行的代码群。27行是以并非i＝j为条件，使对XR[i]加上xout的处理执行的代码。28行是以并非j＝i为条件，使对XC[j]加上xout的处理执行的代码。XR[i]是第i个节点的第1累计值。XC[j]是第j个节点的第2累计值。

30行至46行是使CC处理执行的代码群。30行以及31行是使在xout大于0.5的情况下对b代入true(真)、在不大于0.5的情况下对b代入false(假)、而不管xout为多少在i＝j的情况下对b代入false的处理执行的代码。

32行至35行是在b为true的情况下使对cost加上w[i][j]、对xr_b[i]加上1、对数组xc_b[j]加上1的处理执行的代码群。

37行是使对constraint代入false的处理执行的代码。

38行是使从38行至42行反复的代码。38行是在最初的循环中对k代入0、每个循环对k加上1、以k小于node为条件使循环执行的代码。

39行是判定是否满足(xr_b[k]>1)或者(xc_b[k]>1)或者(xr_b[k]！＝xc_b[k])中的任意一个的代码。40行是在满足39行的代码的情况下使对constraint代入true的处理执行的代码。

43行以及44行是在constraint为true的情况下，使对cost代入0的处理执行的代码。

46行是对cost和最大绝对值(absmax)进行相乘而得到的值乘以-1而针对由此得到的值进行成为10的指数的幂乘运算的代码。sol表示在进行了与包含于最佳路径的2个以上的有向边对应的交换的情况下得到的总体率。

49行是使从49行至57行反复的代码。49行是在最初的循环中对i代入0、每个循环对i加上1、以i小于node为条件使循环执行的代码。

50行是使从50行至56行反复的代码。50行是在最初的循环中对j代入0、每个循环对j加上1、以j小于node为条件使循环执行的代码。

51行是定义yout的代码。

53行是调出并执行MX函数的代码。MX函数是执行MX处理中的与FM电路77对应的处理的函数。53行是将XR[i]、XC[j]、XC[i]、XR[j]、XT[i][j]、X[i][j]交给MX函数并从MX函数接收yout的代码。

55行是从Y[i][j]减去yout的代码。

图25是示出TE伪代码1113的图。搜索装置10在21行中调出TE函数的情况下，按照编号顺序执行图25所示的伪代码。

111行是定义接受xin、yin、win以及zin并输出xout以及yout的代码。此外，xin被代入X[i][j]。yin被代入Y[i][j]。win被代入w[i][j]。zin被代入z[i][j]。

112行以及113行是定义nx1、nx2、nx3、ny1、ny2以及ny3的代码群。115行是使对ny1代入yin的处理执行的代码。116行是使计算xin+dt×yin、并对nx1代入计算结果的处理执行的代码。

118行是使在nx1大于0.5的情况下对nx2代入1、在nx1是0.5以下的情况下对nx2代入0的处理执行的代码。

120行至122行是在nx1大于1或者nx1小于0的情况下使对nx3代入nx2并对ny1代入0的处理执行的代码群。123行至125行是在nx1为0以上1以下的情况下使对nx3代入nx1并对ny2代入ny1的处理执行的代码群。

129行是使计算{ny2-dt×(1-p)×(nx3-x0)-dt×Mc×(ph×win+(1-ph)×w0)}并对ny3代入计算结果的处理执行的代码。此外，dt、x0、Mc以及w0是预先决定的常数。

130行是使在zin为true的情况下对xout代入0、在zin为false的情况下对xout代入nx3的处理执行的代码。131行是使在zin为true的情况下对yout代入0、在zin为false的情况下对yout代入ny3的处理执行的代码。

图26是示出MX伪代码1114的图。搜索装置10在53行中调出MX函数的情况下，按照编号顺序执行图26所示的伪代码。

211行是定义接受XRi、XCj、XCi、XRj、XTij、Xij并输出yout的代码。此外，XRi被代入XR[i]。XCj被代入XC[j]。XCi被代入XC[i]。XRj被代入XR[j]。XTij被代入XT[i][j]。Xij被代入X[i][j]。

212行是使计算dt×Mp×{2×XRi+2×XCj-XCi-XRj+XTij-2×Xij}，并对yout代入计算结果的处理执行的代码。此外，Mp是预先决定的常数。

(并联化)

图27是示出并联化的TE电路31的图。

TE电路31也可以包括多个子TE电路210(多个子自演进电路)。TE电路31可以包括例如2以上(N×N)以下的子TE电路210。多个子TE电路210具有与TE电路31相同的结构，相互并行地执行TE处理。

多个子TE电路210的各个子TE电路210关于多个有向边中的与其他子TE电路210不同的有向边，从存储器21读出前一时刻下的位置变量、前一时刻下的运动量变量、权重值、以及不可选择标志。然后，多个子TE电路210的各个子TE电路210关于多个有向边中的与其他子TE电路210不同的有向边，在执行TE处理之后，将对象时刻下的位置变量以及更新途中的对象时刻下的运动量变量写入到存储器21。

另外，在TE电路31包括多个子TE电路210的情况下，存储器21以使多个子TE电路210能够并行地读出位置变量(X

例如，TE电路31包括与N行N列的矩阵中的N个行对应的N个子TE电路210。TE电路31通过包括N个子TE电路210，能够使针对N×N个位置变量等的读出以及写入的处理容易。

另外，在该情况下，X存储器电路41包括与N个行对应的N个子X存储器电路220。N个子X存储器电路220分别存储对应的行的N个位置变量(X

同样地，Y存储器电路42包括与N个行对应的N个子Y存储器电路222。N个子Y存储器电路222分别存储对应的行的N个运动量变量(Y

同样地，W存储器电路43包括与N个行对应的N个子W存储器电路224。N个子W存储器电路224分别存储对应的行的N个权重值(w

同样地，Z存储器电路44包括与N个行对应的N个子Z存储器电路226。N个子Z存储器电路226分别存储对应的行的N个不可选择标志(z

N个子TE电路210的各个子TE电路210从对应的行的、子X存储器电路220、子Y存储器电路222、子W存储器电路224以及子Z存储器电路226读出位置变量(X

图28是示出并联化的MX电路34的图。

MX电路34也可以包括多个子MX电路230(多个子多体相互作用电路)。关于多个子MX电路230，MX电路34可以包括例如2个以上(N×N)以下的子MX电路230。多个子MX电路230具有与MX电路34相同的结构，相互并行地执行MX处理。

多个子MX电路230的各个子MX电路230关于多个有向边中的与其他子MX电路230不同的有向边，从存储器21读出对象时刻下的位置变量、反转位置变量以及更新途中的对象时刻下的运动量变量。进而，多个子MX电路230的各个子MX电路230关于多个有向边中的与其他子MX电路230不同的有向边，从存储器21读出结束节点的第1累计值及第2累计值、以及开始节点的第1累计值及第2累计值。然后，多个子MX电路230的各个子MX电路230关于多个有向边中的与其他子MX电路230不同的有向边，在执行MX处理之后，将更新后的对象时刻下的运动量变量写入到存储器21。

另外，在MX电路34包括多个子MX电路230的情况下，存储器21以使多个子MX电路230能够并行地读出位置变量(X

例如，MX电路34包括与N行N列的矩阵中的N个行对应的N个子MX电路230。MX电路34通过包括N个子MX电路230，能够使针对N×N个位置变量等的读出以及写入的处理容易。

在该情况下，X存储器电路41包括与N个行对应的N个子X存储器电路220。Y存储器电路42包括与N个行对应的N个子Y存储器电路222。

另外，XR存储器电路45包括与N个行对应的N个子XR存储器电路242。N个子XR存储器电路242分别存储对应的行的第1累计值(XR

另外，XC存储器电路46包括与N个列对应的N个子XC存储器电路244。N个子XC存储器电路244分别存储对应的列的第2累计值(XC

XT存储器电路47包括与N个行对应的N个子XT存储器电路246。N个子XT存储器电路246分别存储对应的行的N个反转位置变量(XT

N个子MX电路230的各个子MX电路230从对应的行的子X存储器电路220、子Y存储器电路222以及对应的行的子XT存储器电路246读出位置变量(X

图29是将并联化的GC电路32的结构与XR存储器电路45以及XC存储器电路46一起示出的图。图30是示出利用并联化的GC电路32的位置变量的取得顺序以及第1累计值及第2累计值的计算顺序的图。

GC电路32在针对N个行并行地执行TE处理的情况下，能够并行地计算N个第1累计值(xr

并联化的GC电路32包括N个行方向累加器262、总加法器264、以及解复用器266。

N个行方向累加器262与N个行对应起来。N个行方向累加器262的各个行方向累加器262对对应的行的N个位置变量(x

N个行方向累加器262的各个行方向累加器262将计算出的累加值作为对应的行的第1累计值(xr

总加法器264按照每个时钟循环，对包含于N个行的N个位置变量(x

解复用器266按照每个时钟循环，逐个选择包含于XC存储器电路46的N个子XC存储器电路244。解复用器266按照每个时钟循环，将从总加法器264输出的加法值作为对应的列的第2累计值(xc

图31是示出并联化前以及并联化后的TE处理以及MX处理的定时的图。

在针对每N行并联化而执行TE处理的情况下，TE电路31以(N+λ

在此，GC电路32能够与TE处理并行地执行GC处理。MX电路34在GC电路32执行GC处理之后、即在从TE处理结束起经过λ

以上，由针对每N行并联化的搜索装置10实施的1次的步骤的处理时间成为{(2×N)+λ

此外，搜索装置10也可以并非每N行，而以其他并联度进行并联化。例如，搜索装置10既可以对整体的处理进行2分割，也可以进行4分割。另外，搜索装置10也可以进行对整体的处理进行N×N分割的并联处理。

如以上那样的第2实施方式所涉及的搜索装置10能够用简易的结构高速地输出搜索有向图的最佳路径的最佳路径问题的解。

(第3实施方式)

接着，说明第3实施方式所涉及的套利系统300。

图32是示出套利系统300的结构的图。

套利系统300是编入有参照图7至图31说明的第2实施方式所涉及的搜索装置10的搜索系统的一个例子。此外，在本实施方式中，套利系统300进行汇兑的交易。但是，套利系统300不限于汇兑，而可以应用于任意的对象的套利。

套利系统300具备搜索装置10、接收装置312、UDP处理部314、输入管理装置316、交易装置318、TCP处理部320以及发送装置322。

搜索装置10是参照图7至图31说明的装置。例如，搜索装置10是作为专用电路安装到FPGA、门阵列或者面向特定用途的集成电路等的半导体装置。

成为搜索装置10的搜索对象的有向图中的多个节点分别与套利的交易对象对应。在本例子中，多个节点分别与货币对应。

另外，多个有向边分别与从与开始节点对应的交易对象向与结束节点对应的交易对象的交换对应。在本例子中，多个有向边分别与从与开始节点对应的货币向与结束节点对应的货币的交换对应。

另外，多个权重值分别表示进行与分配的有向边对应的交换的情况的交换率的对数值。在本例子中，在将进行从与开始节点对应的货币(i)向与结束节点对应的货币(j)的交换的情况的交换率设为r

在搜索装置10中，作为最佳路径，检测对路径分配的2个以上的权重值的累加值成为最小的闭路。此外，在权重值w

搜索装置10将与多个有向边的各个对应的多个比特(b

进而，搜索装置10计算进行与包含于检测到的最佳路径的2个以上的有向边对应的2个以上的交换的情况的总体率(sol)。总体率(sol)通过sol＝Π(r

另外，搜索装置1按照每一定期间，搜索并输出最佳路径。例如，搜索装置10也可以按照每整体的处理时间(例如N

接收装置312从市场服务器经由网络，接收事件分组。事件分组包括表示对多个有向边中的至少1个有向边分配的权重值的信息。例如，事件分组包括与某一个有向边对应的交换率。

在本例子中，事件分组包括头部信息、配对ID、售价(Bid)、以及买价(Ask)。配对ID是识别货币(i)和货币(j)的配对的识别信息。此外，货币(i)是与有向图的第i个节点对应的货币。另外，货币(j)是与有向图的第j个节点对应的货币。

售价(Bid)表示从货币(i)向货币(j)的交换率(r

市场服务器不定期地广播事件分组。接收装置312依次接收不定期地发送的事件分组，提供给UDP处理部314。

UDP处理部314针对从接收装置312提供的事件分组，进行依照通信协议的信息处理，抽出包含于事件分组的、确定有向边的信息以及表示权重值的信息(例如交换率)。

在本例子中，事件分组是依照UDP(User Datagram Protocol：用户数据报协议)协议的分组。因此，在本例子中，UDP处理部314执行依照UDP协议的处理，抽出配对ID、售价(Bid)以及买价(Ask)。

输入管理装置316在内部存储与多个有向边对应的多个权重值。输入管理装置316每当接收事件分组时，从UDP处理部314取得表示对包含于事件分组的至少1个有向边分配的权重值的信息。输入管理装置316根据包含于取得的事件分组的信息，生成权重值，改写存储的多个权重值中的某一个。

在本例子中，输入管理装置316每当接收事件分组时，从UDP处理部314取得配对ID、售价(Bid)以及买价(Ask)。输入管理装置316通过每当接收事件分组时针对售价(Bid)进行负的对数运算，生成与表示从货币(i)向货币(j)的交换的有向边对应的权重值(w

然后，输入管理装置316按照每一定期间改写存储于搜索装置10具备的存储器21的多个权重值。例如，设为搜索装置10按照每预定时间(例如N

另外，输入管理装置316将存储于搜索装置10的多个权重值的全部一并改写。例如，在搜索装置10存储有N×N个权重值的情况下，输入管理装置316将N×N个权重值全部改写。例如，输入管理装置316以及搜索装置10也可以通过N×N×Wdata根布线连接。在此，Wdata是为了表示1个权重值而所需的比特数。而且，输入管理装置316也可以在1个时钟循环一并地改写搜索装置10存储的N×N个权重值。由此，输入管理装置316能够在短时间内改写存储于搜索装置10的多个权重值。

交易装置318从搜索装置10，按照每一定期间取得作为最佳路径的搜索结果的多个比特(b

在判断为执行套利的情况下，交易装置318生成指示执行与被选择为最佳路径的2个以上的有向边对应的交换的订购分组。此外，交易装置318也可以关于与被选择为最佳路径的2个以上的有向边对应的2个以上的交换，在确认关于某1个有向边的约定之后，生成关于接下来的有向边的订购分组。

TCP处理部320针对由交易装置318生成的订购分组，进行依照通信协议的信息处理。在本例子中，订购分组是依照TCP(Transmission Control Protocol：传输控制协议)协议的分组。因此，TCP处理部320将订购分组包含于依照TCP协议的分组。

发送装置322将从TCP处理部320输出的订购分组经由网络发送给执行对象物的交易的买卖服务器。

图33是示出输入管理装置316的结构的图。

输入管理装置316包括传送电路332、操纵电路334、以及地址解码器336。

传送电路332包括与包含于有向图的多个有向边分别对应的多个缓冲存储器340。多个缓冲存储器340分别存储对对应的有向边分配的权重值。

在本例子中，传送电路332包括N×N个缓冲存储器340。N×N个缓冲存储器340被分割成UT部342、LT部344、以及DI部346。

UT部342存储属于矩阵中的上三角分量(UT)的权重值。即，UT部342存储与表示从与第i个节点对应的货币向与第j个节点对应的货币的交换的有向边对应的权重值，其中i

LT部344存储属于矩阵中的下三角分量(LT)的权重值。即，LT部344存储与表示从与第j个节点对应的货币向与第i个节点对应的货币的交换的有向边对应的权重值，其中i

DI部346存储属于矩阵中的对角分量的权重值。DI部346包括N个缓冲存储器340。

在本例子中，N×N个缓冲存储器340的各个缓冲存储器340是能够存储多值数据的D型触发器。在该情况下，缓冲存储器340包括输入端子D、使能端子EN以及输出端子Q。

操纵电路334每当接收事件分组时，取得配对ID、售价(Bid)以及买价(Ask)。

操纵电路334通过每当接收事件分组时，针对售价(Bid)执行负的对数运算(-log(Bid))，计算与表示从与第i个节点对应的货币(i)向与第j个节点对应的货币(j)的交换的有向边对应的权重值(w

进而，操纵电路334每当接收事件分组时针对买价(Ask)执行正的对数运算(+log(Ask))，从而计算与表示从与第j个节点对应的货币(j)向与第i个节点对应的货币(i)的交换的有向边对应的权重值(w

操纵电路334同时输出与从货币(i)向货币(j)的交换对应的权重值(w

操纵电路334每当接收事件分组时，根据配对ID确定货币配对(货币(i)和货币(j)的组)。操纵电路334将表示确定的货币配对的地址提供给地址解码器336。

地址解码器336根据表示货币配对的地址选择包含于UT部342的N×(N-1)/2个缓冲存储器340中的对应的1个缓冲存储器340。另外，地址解码器336根据表示货币配对的地址，选择包含于LT部344的N×(N-1)/2个缓冲存储器340中的对应的1个缓冲存储器340。

地址解码器336对包含于UT部342的选择出的1个缓冲存储器340的使能端子EN、以及包含于LT部344的选择出的1个缓冲存储器340的使能端子EN提供选择信号(Select

包含于UT部342的N×(N-1)/2个缓冲存储器340的各个缓冲存储器340在对使能端子EN提供选择信号(Select

另外，包含于LT部344的N×(N-1)/2个缓冲存储器340的各个缓冲存储器340也在对使能端子EN提供选择信号(Select

此外，包含于DI部346的N个缓冲存储器340在系统起动中，对使能端子EN提供控制信号(Cntrol)，对输入端子D提供权重值的初始值(Clinit)。权重值的初始值(Clinit)是不对权重值的合计值造成影响的值、例如是0。

然后，传送电路332将存储于N×N个缓冲存储器340的N×N个权重值一并地写入到搜索装置10具备的存储器21。例如，传送电路332按照每预定时间(例如N

这样的输入管理装置316在比传送电路332靠前的操纵电路334中，每当接收事件分组时，针对售价(Bid)以及买价(Ask)执行对数运算。传送电路332每当接收事件分组时，改写2个权重值。另外，传送电路332与事件分组的接收非同步地，将N×N个权重值一并输出给搜索装置10。输入管理装置316当假设在传送电路332的后级执行对数运算的情况下，必须并行地执行N×N的对数运算。相对于此，本实施方式的输入管理装置316在比传送电路332靠前的操纵电路334中执行对数运算。由此，本实施方式的输入管理装置316能够用少的电路结构执行对数运算。

另外，传送电路332例如在1个时钟循环中，将N×N个权重值发送给搜索装置10，更新存储于搜索装置10的存储器21的N×N个权重值。因此，传送电路332能够在短时间内更新存储于搜索装置10的存储器21的N×N个权重值。由此，搜索装置10能够针对汇兑的变化高速地检测最佳路径。

另外，传送电路332也可以除了N×N个权重值以外，还存储N×N个交换率。在该情况下，操纵电路334将包含于事件分组的交换率(售价(Bid)以及买价的倒数(1/Ask))也发送给传送电路332，存储到对应的缓冲存储器340。然后，传送电路332除了N×N个权重值以外，将N×N个交换率也发送给搜索装置10的存储器21。由此，搜索装置10能够使用N×N个交换率，容易地执行N×N个权重值的标准化运算。

虽然说明了本发明的几个实施方式，但这些实施方式仅为例示，并未意图限定发明的范围。这些新的实施方式能够以其他各种方式实施，能够在不脱离发明的要旨的范围内，进行各种省略、置换、变更。这些实施方式、其变形包含于发明的范围、要旨中，并且包含于权利要求记载的发明和其均等范围中。

此外，能够将上述实施方式总结为以下的技术方案。

技术方案1

一种搜索装置，搜索对有向边分配有权重值的有向图中的最佳路径，

所述搜索装置具备运算部，该运算部关于假想的多个粒子各自的位置以及运动量，从初始时刻至结束时刻按照每单位时间来更新位置以及运动量，

所述多个粒子与对应于最佳路径搜索问题的0-1最佳化问题所包含的多个比特相对应，

所述多个比特与所述有向图所包含的多个有向边对应，所述多个比特分别表示对应的有向边是否被选择为所述最佳路径，

所述运算部按照每所述单位时间，

关于所述多个粒子的各个粒子，根据对应的粒子在比对象时刻提前1个单位时间的前一时刻下的运动量，计算对应的粒子在所述对象时刻下的位置，

关于所述有向图所包含的多个节点的各个节点，计算与出来的2个以上的有向边对应的、累加2个以上的粒子在所述对象时刻下的位置而得的第1累计值，

关于所述有向图所包含的所述多个节点的各个节点，计算与进入的2个以上的有向边对应的、累加2个以上的粒子在所述对象时刻下的位置的第2累计值，

关于所述多个粒子的各个粒子，根据结束节点的所述第1累计值及所述第2累计值、以及开始节点的所述第1累计值及所述第2累计值、以及对对应的有向边分配的权重值，计算对应的粒子在所述对象时刻下的运动量，

在更新了位置以及运动量直至所述结束时刻为止之后，所述运算部根据对应的粒子在结束时刻下的位置，决定所述多个比特各自的值。

技术方案2

根据技术方案1所述的搜索装置，其中，

所述运算部按照每所述单位时间，

关于所述多个粒子的各个粒子，根据对对应的有向边分配的所述对象时刻下的位置、以及与和对应的有向边相反朝向的有向边对应的粒子在所述对象时刻下的位置，还计算所述对象时刻下的运动量。

技术方案3

根据技术方案1或者2所述的搜索装置，其中，

在更新了位置以及运动量直至所述结束时刻为止之后，所述运算部通过利用预先设定的阈值对所述结束时刻下的所述多个粒子各自的位置进行二值化，决定所述多个比特各自的值。

技术方案4

根据技术方案1至3中的任意一项所述的搜索装置，其中，

所述运算部按照每所述单位时间，

关于所述多个粒子的各个粒子，在所述对象时刻下的位置小于预先决定的第1值的情况下，将所述对象时刻下的位置修正为所述第1值，在大于预先决定的第2值的情况下，将所述对象时刻下的位置修正为所述第2值，

所述第2值大于所述第1值。

技术方案5

根据技术方案1至4中的任意一项所述的搜索装置，其中，

所述运算部按照每所述单位时间，

关于所述多个粒子的各个粒子，在所述对象时刻下的位置小于所述第1值或者大于所述第2值的情况下，将所述前一时刻下的所述运动量修正为预先决定的值或者通过预先决定的运算决定的值。

技术方案6

根据技术方案1至5中的任意一项所述的搜索装置，其中，

所述运算部关于所述多个粒子的各个粒子，

通过对所述前一时刻下的位置、和对所述前一时刻下的运动量乘以所述单位时间而得到的值进行加法运算，计算所述对象时刻下的位置。

技术方案7

根据技术方案2至6中的任意一项所述的搜索装置，其中，

所述运算部按照每所述单位时间，关于所述多个粒子的各个粒子，

根据对应的有向边的结束节点的所述第1累计值及所述第2累计值、对应的有向边的开始节点的所述第1累计值及所述第2累计值、对对应的有向边分配的权重值、所述对象时刻下的位置、以及与和对应的有向边相反朝向的有向边对应的粒子在所述对象时刻下的位置，计算所述对象时刻下的运动量的时间微分值，

通过对所述前一时刻下的运动量、和对所述对象时刻下的运动量的时间微分值乘以所述单位时间而得到的值进行加法运算，计算所述对象时刻下的运动量。

技术方案8

根据技术方案7所述的搜索装置，其中，

所述运算部按照每所述单位时间，

关于所述多个粒子的各个粒子，对所述对象时刻下的运动量的时间微分值加上时间变化参数，

关于所述时间变化参数，将所述初始时刻下的运动量的时间微分值设为0，以使所述时间变化参数的至少一部分在所述结束时刻成为0的方式按照每所述单位时间发生变化。

技术方案9

根据技术方案7所述的搜索装置，其中，

在所述有向图的节点的数量是N、并且搜索闭路作为所述最佳路径的情况下，所述运算部关于所述多个粒子的各个粒子，通过式(1)计算所述对象时刻下的运动量的时间微分值，其中，N为2以上的整数，

【数式1】

i表示节点的索引，是1以上N以下的整数，

j表示节点的索引，是i以外的1以上N以下的整数，

w

x

x

y

XR

XC

XR

XC

M

技术方案10

根据技术方案7所述的搜索装置，其中，

在所述有向图的节点的数量是N、并且作为所述最佳路径搜索从指定的路径开始节点至指定的路径结束节点的情况下，所述运算部关于所述多个粒子的各个粒子，通过式(2)、式(3)以及式(4)计算所述对象时刻下的运动量的时间微分值，其中，N为2以上的整数，

【数式2】

s表示所述路径开始节点的索引，是1以上N以下的指定的整数，

v表示所述路径结束节点的索引，是s以外的1以上N以下的指定的整数，

k表示节点的索引，是s以及v以外的1以上N以下的整数，

l表示节点的索引，是s、v以及k以外的1以上N以下的整数，

w

w

w

x

x

y

XR

XC

XR

XC

XR

XC

M

技术方案11

根据技术方案10所述的搜索装置，其中，

所述运算部将x

x

x

x

x

技术方案12

一种搜索方法，通过信息处理装置搜索对有向边分配有权重值的有向图中的最佳路径，其中，

所述信息处理装置关于假想的多个粒子各自的位置以及运动量，从初始时刻至结束时刻按照每单位时间来更新位置以及运动量，

所述多个粒子与对应于最佳路径搜索问题的0-1最佳化问题所包含的多个比特相对应，

所述多个比特与所述有向图所包含的多个有向边对应，所述多个比特分别表示对应的有向边是否被选择为所述最佳路径，

所述信息处理装置按照每所述单位时间，

关于所述多个粒子的各个粒子，根据对应的粒子在比对象时刻提前1个单位时间的前一时刻下的运动量，计算对应的粒子在所述对象时刻下的位置，

关于所述有向图所包含的多个节点的各个节点，计算与出来的2个以上的有向边对应的、累加2个以上的粒子在所述对象时刻下的位置而得的第1累计值，

关于所述有向图所包含的所述多个节点的各个节点，计算与进入的2个以上的有向边对应的、累加2个以上的粒子在所述对象时刻下的位置的第2累计值，

关于所述多个粒子的各个粒子，根据结束节点的所述第1累计值及所述第2累计值、以及开始节点的所述第1累计值及所述第2累计值、以及对对应的有向边分配的权重值，计算对应的粒子在所述对象时刻下的运动量，

在更新了位置以及运动量直至所述结束时刻为止之后，所述信息处理装置根据对应的粒子在结束时刻下的位置，决定所述多个比特各自的值。

技术方案13

一种程序，用于使信息处理装置搜索对有向边分配有权重值的有向图中的最佳路径，其中，

使所述信息处理装置关于假想的多个粒子各自的位置以及运动量，从初始时刻至结束时刻按照每单位时间来更新位置以及运动量，

所述多个粒子与对应于最佳路径搜索问题的0-1最佳化问题所包含的多个比特相对应，

所述多个比特与所述有向图所包含的多个有向边对应，所述多个比特分别表示对应的有向边是否被选择为所述最佳路径，

使所述信息处理装置按照每所述单位时间，

关于所述多个粒子的各个粒子，根据对应的粒子在比对象时刻提前1个单位时间的前一时刻下的运动量，计算对应的粒子在所述对象时刻下的位置，

关于所述有向图所包含的多个节点的各个节点，计算与出来的2个以上的有向边对应的、累加2个以上的粒子在所述对象时刻下的位置而得的第1累计值，

关于所述有向图所包含的所述多个节点的各个节点，计算与进入的2个以上的有向边对应的、累加2个以上的粒子在所述对象时刻下的位置的第2累计值，

关于所述多个粒子的各个粒子，根据结束节点的所述第1累计值及所述第2累计值、以及开始节点的所述第1累计值及所述第2累计值、以及对对应的有向边分配的权重值，计算对应的粒子在所述对象时刻下的运动量，

在更新了位置以及运动量直至所述结束时刻为止之后，使所述信息处理装置根据对应的粒子在结束时刻下的位置，决定所述多个比特各自的值。

技术方案14

一种搜索装置，搜索对有向边分配有权重的有向图中的最佳路径，所述搜索装置具备：

存储器，存储与所述有向图所包含的多个有向边对应的多个位置变量、与所述多个有向边对应的多个运动量变量、以及与所述多个有向边对应的多个权重值；

控制电路，控制从初始时刻至结束时刻按照每单位时间对与所述多个有向边分别对应的位置变量及运动量变量进行时间积分的运算；

自演进电路，按照每所述单位时间，关于所述多个有向边的各个有向边，根据对应的有向边在比对象时刻提前1个单位时间的前一时刻下的运动量变量更新对应的有向边在所述对象时刻下的位置变量，以及根据对应的有向边在所述对象时刻下的位置变量及对对应的有向边分配的权重值，更新对应的有向边在所述对象时刻下的运动量变量；以及

多体相互作用电路，按照每所述单位时间，关于所述多个有向边的各个有向边，根据对应的有向边以外的有向边在所述对象时刻下的位置变量、及对应的有向边在所述对象时刻下的位置变量，还更新对应的有向边在所述对象时刻下的运动量变量。

技术方案15

根据技术方案14所述的搜索装置，其中，

所述多个位置变量以及所述多个运动量变量表示假想的多个粒子的位置以及运动量，

所述多个粒子与0-1最佳化问题所包含的多个比特对应，依照所述0-1最佳化问题来表示整体的能量，

所述多个比特与所述多个有向边对应，所述多个比特分别表示对应的有向边是否被选择为所述最佳路径，

所述0-1最佳化问题包括使用所述多个比特来表示对选择出的路径所包含的2个以上的有向边分配的权重的合计值的成本函数、和使用所述多个比特来表示满足所述最佳路径的制约条件的惩罚函数，

所述自演进电路以及所述多体相互作用电路关于所述多个有向边的各个有向边，执行按照每所述单位时间对所述位置变量以及所述运动量变量进行时间积分的运算。

技术方案16

根据技术方案15所述的搜索装置，还具备：

二值化电路，该二值化电路通过利用预先设定的阈值对所述结束时刻下的与所述多个有向边的各个对应的位置变量进行二值化，计算所述0-1最佳化问题所包含的所述多个比特各自的解。

技术方案17

根据技术方案16所述的搜索装置，还具备：

累计值计算电路，该累计值计算电路按照每所述单位时间，关于所述有向图所包含的多个节点的各个节点，计算与出来的2个以上的有向边对应的、将2个以上的所述对象时刻下的位置变量累加的第1累计值，以及关于所述多个节点的各个节点，计算与进入的2个以上的有向边对应的、将2个以上的所述对象时刻下的位置变量累加的第2累计值，

所述多体相互作用电路按照每所述单位时间，关于所述多个有向边的各个有向边，

根据结束节点的所述第1累计值及所述第2累计值、开始节点的所述第1累计值及所述第2累计值、对应的有向边在所述对象时刻下的位置变量、以及与和对应的有向边相反朝向的有向边对应的所述对象时刻下的位置变量，还更新对应的有向边在所述对象时刻下的运动量变量。

技术方案18

根据技术方案17所述的搜索装置，其中，

所述自演进电路针对每个有向边依次从所述存储器读出所述前一时刻下的位置变量以及运动量变量，针对每个有向边依次计算所述对象时刻下的位置变量以及更新途中的所述对象时刻下的运动量变量，并写入到所述存储器。

技术方案19

根据技术方案17或者18所述的搜索装置，其中，

所述多体相互作用电路针对每个有向边依次从所述存储器读出所述对象时刻下的位置变量以及更新途中的所述对象时刻下的运动量变量，针对每个有向边依次计算更新后的所述对象时刻下的运动量变量，并写入到所述存储器。

技术方案20

根据技术方案17至19中的任意一项所述的搜索装置，其中，

所述自演进电路按照每所述单位时间，关于所述多个有向边的各个有向边，从所述存储器读出所述前一时刻下的位置变量以及运动量变量，计算所述对象时刻下的位置变量以及更新途中的所述对象时刻下的运动量变量，并写入到所述存储器，

所述多体相互作用电路按照每所述单位时间，关于所述多个有向边的各个有向边，从所述存储器读出所述对象时刻下的位置变量以及更新途中的所述对象时刻下的运动量变量，计算更新后的所述对象时刻下的运动量变量，并写入到所述存储器，

所述多体相互作用电路以与所述自演进电路执行处理的期间不重复的方式，执行处理。

技术方案21

根据技术方案17至20中的任意一项所述的搜索装置，其中，

所述自演进电路按照每所述单位时间，关于所述多个有向边的各个有向边，在对应的有向边在所述对象时刻下的位置变量小于预先决定的第1值的情况下，将所述对象时刻下的位置变量修正为所述第1值，在对应的有向边在所述对象时刻下的位置变量大于预先决定的第2值的情况下，将所述对象时刻下的位置变量修正为所述第2值，

所述第2值大于所述第1值。

技术方案22

根据技术方案21所述的搜索装置，其中，

所述自演进电路按照每所述单位时间，关于所述多个有向边的各个有向边，在所述对象时刻下的位置变量小于所述第1值或者大于所述第2值的情况下，将所述对象时刻下的运动量变量修正为预先决定的值或者通过预先决定的运算决定的值。

技术方案23

根据技术方案17至22中的任意一项所述的搜索装置，其中，

所述存储器还存储与所述多个有向边对应的、表示可选择或者不可选择为路径的多个不可选择标志，

所述自演进电路关于所述多个有向边的各个有向边，在对应的有向边的不可选择标志表示不可选择的情况下，将所述对象时刻下的位置变量以及所述对象时刻下的运动量变量置换为预先决定的值。

技术方案24

根据技术方案17至23中的任意一项所述的搜索装置，还具备：

标准化电路，该标准化电路在所述最佳路径的搜索以前，根据所述多个权重值中的最大绝对值对所述多个权重值分别进行标准化，将标准化后的所述多个权重值写入到所述存储器。

技术方案25

根据技术方案17至24中的任意一项所述的搜索装置，还具备成本计算电路，

所述成本计算电路按照每所述单位时间，

通过利用预先设定的阈值对与所述多个有向边的各个有向边对应的位置变量进行二值化，关于所述多个有向边的各个有向边，判定是否在所述对象时刻的阶段中被选择为所述最佳路径，

判定在所述对象时刻的阶段中被选择为所述最佳路径的2个以上的有向边是否满足所述制约条件，

在满足所述制约条件的情况下，计算将对被选择为所述最佳路径的2个以上的有向边分配的权重值合成的所述权重的合计值。

技术方案26

根据技术方案17至25中的任意一项所述的搜索装置，其中，

所述自演进电路包括多个子自演进电路，

所述多个子自演进电路的各个子自演进电路关于所述多个有向边中的与其他子自演进电路不同的有向边，从所述存储器读出所述前一时刻下的位置变量以及运动量变量，将所述对象时刻下的位置变量以及更新途中的所述对象时刻下的运动量变量写入到所述存储器。

技术方案27

根据技术方案17至26中的任意一项所述的搜索装置，其中，

所述多体相互作用电路包括多个子多体相互作用电路，

所述多个子多体相互作用电路的各个子多体相互作用电路关于所述多个有向边中的与其他子多体相互作用电路不同的有向边，从所述存储器读出所述对象时刻下的位置变量以及更新途中的所述对象时刻下的运动量变量，计算更新后的所述对象时刻下的运动量变量，并写入到所述存储器。

技术方案28

根据技术方案17至27中的任意一项所述的搜索装置，其中，

所述有向图具有N个节点，N为3以上的整数，

所述N个节点的各个节点被分配1至N的固有的索引，

所述存储器存储位置矩阵，所述位置矩阵储存由所述自演进电路计算出的所述对象时刻下的N×N个位置变量，

在所述位置矩阵中，行编号表示有向边中的开始节点的索引，列编号表示有向边中的结束节点的索引，

在所述位置矩阵中，将0作为行编号和列编号相同的对角分量的要素来储存，

所述累计值计算电路包括：

与N个行对应的N个行方向累加器、和

对N个位置变量进行加法运算的总加法器，

所述累计值计算电路从所述位置矩阵中的N个行的各个行并行地取得N个位置变量，

所述N个行方向累加器的各个行方向累加器通过对对应的行所包含的N个位置变量进行累加，计算对应的节点的所述第1累计值，

所述总加法器通过对同一列所包含的N个位置变量进行加法运算，按照每列计算对应的节点的所述第2累计值。

技术方案29

一种搜索系统，搜索对有向边分配有权重的有向图中的最佳路径，所述搜索系统具备：

权利要求14至28中的任意一项所述的搜索装置；以及

输入管理装置，将所述多个权重值写入到所述搜索装置具备的所述存储器，

所述输入管理装置一并地改写存储于所述存储器的所述多个权重值，

所述搜索装置搜索所述最佳路径。

技术方案30

根据技术方案29记载的搜索系统，其中，

所述输入管理装置包括：

传送电路，包括与所述多个权重值对应的多个缓冲存储器；以及

操纵电路，取得事件分组，取得所述事件分组所包含的、表示对所述多个有向边中的至少1个有向边分配的权重值的信息，

所述操纵电路根据取得的所述事件分组所包含的所述信息，生成权重值，将生成的权重值写入到所述传送电路所包含的所述多个缓冲存储器中的对应的缓冲存储器，

所述传送电路通过将存储于所述多个缓冲存储器的所述多个权重值一并地输出给所述搜索装置，并行地一并改写到所述存储器。

技术方案31

根据技术方案30所述的搜索系统，其中，

所述事件分组包括将所述多个有向边中的至少1个有向边选择为所述最佳路径的情况下的交换率，

所述操纵电路通过对取得的所述事件分组所包含的所述交换率进行对数运算，生成权重值。

技术方案32

一种套利系统，指示套利，所述套利系统具备：

接收装置；

输入管理装置；

权利要求14至28中的任意一项所述的搜索装置；

交易装置；以及

发送装置，

所述有向图所包含的多个节点分别对应于交易对象，

所述多个有向边分别对应于从与开始节点对应的交易对象向与结束节点对应的交易对象的交换，

所述多个权重值分别表示进行了与分配的有向边对应的交换的情况下的交换率的对数值，

所述搜索装置将所述权重值的累加值为最大或者最小的路径检测为所述最佳路径，

所述接收装置从市场服务器取得包括与所述多个有向边中的某一个有向边对应的交换率的事件分组，

所述输入管理装置根据取得的所述事件分组，生成对应的有向边的权重值，改写所述搜索装置具备的所述存储器的权重值，

所述交易装置根据进行了与由所述搜索装置检测的所述最佳路径所包含的2个以上的有向边对应的交换的情况下的总体率，生成订购分组，该订购分组指示执行与被选择为所述最佳路径的2个以上的有向边对应的交换，

所述发送装置将所述订购分组发送给买卖服务器。