在大量資產中尋找套利時，有沒有最優的方法？
在查看 3 對相關貨幣時尋找套利機會很容易。但是，如果我們假設我們有大量的貨幣，是否有一種最佳的方式來瀏覽它們並檢查大量不同的可能排列？到目前為止，我還沒有找到任何研究，主要問題是我不完全確定如何尋找這個。
謝謝
例如，Thomas H. Cormen、Charles E. Leiserson、Ronald Rivest、Clifford Stein。算法簡介，問題 24-3 說：
24-3 套利
套利是利用貨幣匯率的差異將一個單位的貨幣轉換為多個單位的同種貨幣。例如，假設 1 美元買 49 印度盧比，1 印度盧比買 2 日元，1 日元買 0.0107 美元。然後，通過兌換貨幣，交易者可以從 1 美元開始買入 49 $ \times $ 2 $ \times $ 0.0107 = 1.0486 美元，因此獲利 4.86%。
假設我們得到 $ n $ 貨幣 $ c_1, c_2, \ldots , c_n $ 和 $ n \times n $ 桌子 $ R $ 匯率，這樣一單位貨幣 $ c_i $ 購買 $ R[i, j] $ 貨幣單位 $ c_j $ .
一個。給出一個有效的算法來確定是否存在一系列貨幣 $ <c_{i_1}, c_{i_2}, \ldots , c_{i_k}> $ 這樣
$ R[i_1, i_2] \cdot R[i_1, i_2] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] > 1 $
分析算法的執行時間。
灣。如果存在這樣的序列，請給出一個有效的算法來列印出這樣的序列。分析算法的執行時間。
選定的解決方案說：
問題 24-3 的解決方案
一個。我們可以在合適的加權有向圖上使用Bellman-Ford算法 $ G =(V,E) $ ，我們形成如下。有一個頂點 $ V $ 對於每種貨幣，以及每對貨幣 $ c_i $ 和 $ c_j $ , 有向邊 $ (v_i,v_j) $ 和 $ (v_j,v_i) $ . （因此， $ |V|= n $ 和 $ |E|= n(n - 1) $ .)
為了確定邊緣權重，我們首先觀察
$ R[i_1, i_2] \cdot R[i_1, i_2] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] > 1 $
當且僅當
$ \dfrac{1}{R[i_1, i_2]} \cdot \dfrac{1}{R[i_1, i_2]} \cdots \dfrac{1}{R[i_{k-1}, i_k]} \cdot \dfrac{1}{R[i_k, i_1]} < 1 $ .
取上述不等式兩邊的對數，我們將此條件表示為
$ \lg\dfrac{1}{R[i_1, i_2]} + \lg\dfrac{1}{R[i_1, i_2]} + \cdots +\lg\dfrac{1}{R[i_{k-1}, i_k]} +\lg \dfrac{1}{R[i_k, i_1]} < 0 $ .
因此，如果我們定義邊緣的權重 $ (v_i,v_j) $ 作為
$ w(v_i,v_j) = \lg \dfrac{1}{R[i, j]} = -\lg R[i, j] $ .
然後我們要找出是否存在負權循環 $ G $ 使用這些邊緣權重。
我們可以判斷是否存在負權循環 $ G $ 通過添加一個額外的頂點 $ v_0 $ 和 $ 0 $ -權重邊緣 $ (v_0, v_i) $ 對所有人 $ v_i \in V $ , 執行 Bellman-Ford從 $ v_0 $ ，並使用 Bellman-Ford的布爾結果（如果沒有負權循環則為 TRUE，如果存在負權循環則為 FALSE）來指導我們的答案。也就是說，我們反轉了Bellman-Ford的布爾結果。
這種方法之所以有效，是因為將具有 0 權重邊的新頂點 0 從 0 添加到所有其他頂點不會引入任何新循環，但它確保所有負權循環都可以從 $ v_0 $ .
它需要 $ \Theta(n^2) $ 創造時間 $ G $ ， 其中有 $ \Theta(n^2) $ 邊緣。然後需要 $ O(n^3) $ 是時候執行Bellman-Ford了。因此，總時間為 $ O(n^3) $ .
確定是否存在負權重循環的另一種方法是創建 $ G $ 並且，不添加 $ v_0 $ 及其入射邊，執行任一對最短路徑算法。如果得到的最短路徑距離矩陣在對角線上有任何負值，則存在負權循環。
灣。假設我們執行Bellman-Ford來解決 (a) 部分，我們只需要找到負權循環的頂點。我們可以這樣做。首先，再次放鬆所有邊緣*$$ pp 648ff $$*. 由於存在負權重循環， $ d $ 某個頂點的值 $ u $ 將改變。我們只需要反复遵循 $ \pi $ 價值，直到我們回到 $ u $ . 換句話說，我們可以使用 22.2 節的 PRINT-PATH 過程給出的遞歸方法，但是當它返回頂點時停止它 $ u $ .
執行時間為 $ O(n^3) $ 執行貝爾曼福特，加上 $ O(n) $ 列印循環的頂點，總共 $ O(n^3) $ 時間。
某人的範常式式碼在github中。我不確定它是否正確實施。
相關問題：https ://stackoverflow.com/questions/2282427
相關討論：https ://www.thealgorists.com/Algo/ShortestPaths/Arbitrage
Bellman-Ford 的相關課堂筆記：http: //cseweb.ucsd.edu/classes/sp20/cse101-a/Slides/Week-09/Lec-29.pdf
（我想知道當矩陣稀疏時是否可以進行額外的優化，因為某些貨幣對沒有被引用。我還想知道人們如何處理非線性成本，例如固定費用或根據匯率大小而變化的匯率。）
我覺得這不是一個關於圖論應用的問題的重複，因為這是相反的。
如果您純粹談論貨幣套利，最快的方法似乎是在貨幣圖中找到負循環，其中頂點是貨幣，節點是匯率。