从零开始学 Bellman-Ford：寻找负环

《打造自己的套利机器人》课程第 6 课。第 5 课把有利可图的兑换环变成了权重之和小于零的环。今天你将学习一种经典算法，用来寻找这样的环。

先直接试一试

在使用巧妙算法之前，先用最直接的方法解决问题，看看难点在哪里。尝试每一种可能的环，把汇率相乘，再保留最好的那个。

import itertools

rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75}

def brute(rates, max_len):
    nodes = sorted({n for edge in rates for n in edge})
    best, tried = (1.0, None), 0
    for k in range(2, max_len + 1):
        for path in itertools.permutations(nodes, k):
            tried += 1
            cycle = list(path) + [path[0]]
            money = 1.0
            for a, b in zip(cycle, cycle[1:]):
                if (a, b) not in rates:
                    money = None
                    break
                money *= rates[(a, b)]
            if money and money > best[0]:
                best = (money, cycle)
    return best, tried

print(brute(rates, 3))

输出：

((1.0296, ['EUR', 'GBP', 'USD', 'EUR']), 12)

它确实有效：同一个环，同一个 1.0296，尝试了 12 次。现在把市场变大一些。如果每种货币都能和其他每种货币交易（这是最糟糕的情况，但和大型交易所很接近），下面是我在一台笔记本电脑上测得的次数和时间：

每增加一种货币，工作量大约会增加十倍。货币达到 15 种时，你要等上好几天，而真实交易所有几百种货币。这个直接方法是正确的，却没有实际用处。你也能看出原因：它一遍又一遍地检查相同的部分路径。本课剩下的内容会介绍一种方法，让它记住已经学到的信息。

用简单的话说明思路

想象一张由单向道路连接起来的城市地图，每条路都有一个费用。你站在城市 S，想知道前往其他每个城市最便宜的路线。开始时，你会猜“我还不知道”，并把它写成无穷大。接着，你一次又一次地改进自己的猜测。

改进方法如下：查看一条从城市 A 到城市 B、费用为 w 的道路。如果你已知到达 A 的最便宜路线费用加上 w，比你已知的到达 B 的费用更低，那就找到了一条去 B 的更便宜路线。记下新的数字。这个步骤叫作松弛这条道路。

Bellman-Ford 会一遍又一遍地松弛每条道路，直到没有任何改进。

一个计算示例

三个城市 S、A、B 和三条道路：S 到 A 的费用是 4，S 到 B 的费用是 5，A 到 B 的费用是 −2。（允许出现负费用，可以把它想成折扣。）

开始时：S = 0，A = ∞，B = ∞。

第 1 轮，按 S 到 A、S 到 B、A 到 B 的顺序检查道路：

• S 到 A：0 + 4 = 4，比 ∞ 更好，所以 A = 4。
• S 到 B：0 + 5 = 5，比 ∞ 更好，所以 B = 5。
• A 到 B：4 + (−2) = 2，比 5 更好，所以 B = 2。

第 2 轮：没有任何改进。我们停止。最便宜的路线费用是：到 A 为 4，到 B 为 2（路线是 S、A、B）。

最多需要多少轮？一条最便宜的路线不会重复经过同一个城市，所以如果有 V 个城市，它最多经过 V − 1 条道路。每一轮至少会补全多一条道路上的正确信息，因此 V − 1 轮总是足够的。

额外的一轮：负环如何现身

假设一圈道路的总费用小于零。每绕一圈，费用数字就会继续变小，没有尽头。因此，改进不会停止。

Bellman-Ford 会利用这一点。它先运行 V − 1 轮常规计算，然后再运行一轮。如果还有道路能改进，就说明存在负环。如果没有任何改进，就不存在负环。

看第 5 课中的小环示例。取以下权重：USD 到 EUR 为 +0.1054，EUR 到 GBP 为 +0.1278，GBP 到 USD 为 −0.2624。它们的总和是 −0.0292。从 USD 出发，初始值为 0。

• 第 1 轮：EUR = 0.1054，GBP = 0.2332；接着沿 GBP 到 USD，0.2332 − 0.2624 = −0.0292，比 0 更好，所以 USD = −0.0292。
• 第 2 轮：EUR = −0.0292 + 0.1054 = 0.0762，GBP = 0.2040，USD = −0.0584。
• 这个过程会一直继续，每绕一圈就降低 0.0292。

三个节点最多需要 2 轮常规计算，而额外的一轮（第 3 轮）仍然能改进结果。这就是警报。

找出环本身

警报只能说明发现了问题，还没有给出环。我们要为每个节点记下从哪个节点到达这里，这个节点叫作前驱节点。如果额外一轮改进了某个节点，就沿着前驱节点往回走。走 V 步后，我们一定会进入这个环（在 V 个节点上走 V 步，必然会重复经过某个节点）。然后沿着环继续走，直到回到起点。

代码

import math

rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75}
nodes = ["USD", "EUR", "GBP"]
edges = [(a, b, -math.log(r)) for (a, b), r in rates.items()]

def bellman_ford(nodes, edges, start):
    dist = {n: math.inf for n in nodes}
    prev = {n: None for n in nodes}
    dist[start] = 0.0
    for _ in range(len(nodes) - 1):          # V - 1 轮常规计算
        changed = False
        for a, b, w in edges:
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                prev[b] = a
                changed = True
        if not changed:
            break
    for a, b, w in edges:                    # 额外的一轮
        if dist[a] + w < dist[b]:
            prev[b] = a
            x = b
            for _ in range(len(nodes)):      # 回退 V 步：现在已进入环内
                x = prev[x]
            cycle, y = [x], prev[x]
            while y != x:
                cycle.append(y)
                y = prev[y]
            cycle.reverse()
            return cycle + [cycle[0]]
    return None

cycle = bellman_ford(nodes, edges, "USD")
print("cycle:", cycle)
money = 1.0
for a, b in zip(cycle, cycle[1:]):
    money *= rates[(a, b)]
print("1 unit becomes", round(money, 4))

输出：

cycle: ['GBP', 'USD', 'EUR', 'GBP']
1 unit becomes 1.0296

程序找到了第 5 课中的同一个环，只是从环上的另一个节点开始（环没有固定的起点）。最后的检查会把环上的实际汇率相乘，得到我们手算出的 1.0296。

速度有多快？

每一轮都会检查每条道路一次，而最多要检查 V 轮，所以计算量大约是 V × E 步（E 是道路数）。如果一个市场有 300 种货币和 1800 个交易对，每次扫描最多要检查 540,000 次。这对业余机器人来说没问题，但对于需要每秒扫描很多次的机器人来说就很慢。第 7 课会介绍一种技巧，可以跳过大部分计算。

需要如实说明的几点

• Bellman-Ford 返回一个负环，不一定是最好的那个。
• 计算期间汇率会变化。你找到的环只是某一时刻的快照。
• 它使用类似市场中间价的汇率，不知道你实际能交易多少。这属于第 2 阶段（第 9 和第 10 课）。

让 AI 智能体编写并测试程序

含糊的请求：

实现 Bellman-Ford 来寻找套利机会。

自带测试的请求：

编写 bellman.py，其中包含 find_cycle(rates) 函数。它接收字典 {("USD","EUR"): 0.90, ...}，用自然对数的相反数把汇率转换为权重，运行带额外一轮和前驱节点的 Bellman-Ford，并以货币名称列表的形式返回兑换环；如果没有则返回 None。使用这些汇率添加一个测试：USD 到 EUR 为 0.90，EUR 到 GBP 为 0.88，GBP 到 USD 为 1.30，EUR 到 USD 为 1.10，GBP 到 EUR 为 1.10，USD 到 GBP 为 0.75。测试必须打印兑换环和资金倍数，后者必须为 1.0296。再添加第二个测试，将这些汇率全部乘以 0.95：它必须返回 None。

第二个测试很重要。一个总会找到兑换环的程序也能通过第一个测试。

练习

1. 运行代码。资金倍数会是 1.0296 吗？
2. 把每个汇率都乘以 0.95（相当于高额手续费）。再运行一次。你应该会得到 None。为什么？兑换环的汇率乘积是 1.0296 × 0.95³ = 0.883，小于 1。
3. 手算以下情况：三个城市 S、A、B，道路费用分别是 S 到 A 为 4、S 到 B 为 5、A 到 B 为 −2。把每一轮的计算写在纸上，再用一小段代码验证。
4. 对这张图，常规计算部分需要多少轮才会停止？加一个计数器。

接下来

Bellman-Ford 每一轮都会重新检查所有道路，即使某条道路对应的信息不可能发生变化。第 7 课会介绍 SPFA，它是一种延迟检查的版本，只重新检查那些起点刚刚得到改进的节点所连接的道路。