Last updated
世界的本质：2 * 3 = 6无定价缺陷的货币汇率关系：2 * 3 = 6
有定价缺陷的货币汇率关系：2 * 3 > 5.9
用环形表示有缺陷汇率关系：2 * 3 * 1/5.9 > 1
取ln的环形有缺陷汇率关系：-ln2 + -ln3 + -ln(1/5.9) < 0，
就是一个负权环。
然后用Bellman-Ford-Moore算法去找，时间复杂度是 O(N^3)。
你要做的是，把市场数据下载到一个服务器里，
用货币名称作为顶点V，用 -ln(汇率)作为边权E，
建立货币市场，带边权有向图 G(V,E) 的邻接矩阵，
用这个 B-F-M 算法，从图的邻接矩阵表示里面，寻找其中的套利路径。INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex v ∈ G.V
v.d = ∞
v.π = NIL
s.d = 0
RELAX(u,v,w)
if v.d > u.d + w(u,v)
v.d = u.d + w(u,v)
v.π = u
//算法本体开始
BELLMAN-FORD-FIND-NEGATIVE-CYCLE(G,w,s)
//第一部分：初始化，引用INITIALIZE-SINGLE-SOURCE(G,s)
INITIALIZE-SINGLE-SOURCE(G,s)
//第二部分：计算，引用RELAX(u,v,w)
for i <- 1 to |V[G]| - 1
do for each edge (u,v) ∈ E[G]
do RELAX(u,v,w)
//第三部分：检验，FIND-NEGATIVE-CYCLE。
for each edge (u,v) ∈ E[G]
do if d[v] > d[u] + w(u,v)
then mark v
x <- v
while π[x] is not marked
do mark π[x]
x <- π[x]
return marked nodes
return NIL