從零認識 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 次後得到結果。現在把市場變大。每一種貨幣都能和其他每一種交易（這是最糟情況，但很接近大型交易所）時，以下是我在一台筆電上測得的次數和時間：

貨幣數	嘗試的圈	時間
5	320	少於 0.01 秒
8	109 592	0.3 秒
10	9 864 090	25 秒

每新增一種貨幣，工作量大約就乘上十。到 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 千次檢查。這對業餘機器人沒問題，對必須每秒掃描很多次的機器人則很慢。第 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.0296 嗎？
把每個匯率都乘上 0.95（很高的手續費）。再執行一次。你應該得到 None。為什麼？這一圈的乘積是 1.0296 × 0.95³ = 0.883，小於 1。
手算：三座城市 S、A、B，有 S 到 A 成本 4、S 到 B 成本 5、A 到 B 成本 −2 的道路。在紙上做每一輪，然後用一小段程式檢查。
找出這張圖的一般部分停止前需要幾輪。加入一個計數器。

接下來

Bellman-Ford 每一輪都會重新檢查所有道路，連那些不可能改變的也是。第 7 課會介紹 SPFA，它是一個比較懶的版本，只重新檢查剛剛改善過的節點出發的道路。