Algoritma Graf untuk Pengesanan Arbitraj: Dari Bellman-Ford ke RICH

Bahagian 1 daripada siri "Rantaian Arbitraj Kompleks antara Niaga Hadapan dan Spot"

Bayangkan pasaran mata wang kripto sebagai organisma hidup yang bernafas di mana ribuan harga berubah setiap saat merentasi ratusan bursa. Dalam kekacauan ini, perbezaan harga sementara timbul—"ketidakcekapan"—yang membolehkan keuntungan tanpa risiko. Inilah arbitraj. Namun kami bukan bercakap tentang pertukaran dua langkah yang mudah. Kami menyelami rantaian berbilang aset yang kompleks di mana keuntungan mungkin hanya ditemui dengan melompat dari BTC ke ETH, kemudian ke SOL, kemudian ke USDT, dan akhirnya kembali ke BTC.

Bagaimana kami menemui rantaian ini di antara jutaan kemungkinan dalam masa nyata? Jawapannya terletak pada Teori Graf.

Dalam artikel ini, kami akan menelusuri laluan dari algoritma klasik kepada penyelidikan akademik mutakhir, melaksanakan semuanya dalam Rust untuk prestasi maksimum.

Visualisasi berteknologi tinggi bagi graf arbitraj: nod mewakili aset, dan tepi mewakili pasangan perdagangan. Kitaran yang diserlahkan mewakili peluang menguntungkan yang dikesan.

1. Pasaran sebagai Graf

Untuk menerapkan algoritma graf, kita mesti terlebih dahulu mewakili pasaran dengan betul.

1.1 Bucu dan Tepi

• Bucu (Nod): Aset (BTC, ETH, USDT, dll.).
• Tepi (Pautan): Pasangan perdagangan (BTC/USDT, ETH/BTC).
• Pemberat: Kadar pertukaran.

Jika kita mempunyai kadar $R(i, j)$ (berapa banyak aset $j$ yang kita peroleh untuk 1 unit aset $i$), peluang arbitraj wujud jika kitaran $(i_1, i_2, \dots, i_k, i_1)$ menghasilkan: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Dari Pendaraban ke Penambahan

Komputer jauh lebih pantas dalam menambah berbanding mendarab, dan kebanyakan algoritma laluan terpendek direka untuk jumlah. Kami menggunakan helah matematik yang mudah: logaritma. Memandangkan $\ln(a \times b) = \ln(a) + \ln(b)$, syaratnya menjadi: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Atau, dengan membalikkan tanda untuk mencari kitaran negatif: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Kini, setiap tepi mempunyai pemberat $w = -\ln(R)$. Tugas kami adalah untuk mencari kitaran dengan jumlah pemberat negatif.

2. Pendekatan Klasik: Bellman-Ford

Algoritma Bellman-Ford adalah "Hello World" dalam pengesanan arbitraj. Ia direka untuk mencari laluan terpendek dan dapat mengesan kitaran negatif secara semula jadi.

2.1 Algoritma dalam Rust

Menggunakan crate petgraph, kami boleh melaksanakan ini dengan cekap:

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::algo::bellman_ford;

fn find_arbitrage_bellman_ford(
    graph: &DiGraph<&str, f64>, 
    start_node: NodeIndex
) -> Option<Vec<NodeIndex>> {
    // Bellman-Ford mengembalikan jarak atau ralat jika kitaran negatif ditemui
    match bellman_ford(graph, start_node) {
        Ok(_) => None, // Tiada kitaran negatif
        Err(error) => {
            // Dalam pelaksanaan sebenar, kami akan membina semula kitaran 
            // menggunakan peta pendahulu daripada ralat
            println!("Arbitraj dikesan!");
            None 
        }
    }
}

2.2 Kerumitan dan Limitasi

Bellman-Ford berjalan dalam $O(V \times E)$, di mana $V$ adalah bilangan aset dan $E$ adalah bilangan pasangan perdagangan.

• Kelebihan: Menjamin penemuan kitaran jika ia wujud.
• Kelemahan: Terlalu perlahan untuk Dagangan Frekuensi Tinggi (HFT) apabila bilangan aset bertambah. Ia juga hanya menemui satu kitaran pada satu masa.

3. SPFA: Alternatif yang Lebih Pantas

Shortest Path Faster Algorithm (SPFA) adalah versi Bellman-Ford yang dioptimumkan yang menggunakan baris gilir untuk mengelakkan pengiraan berulang.

use std::collections::VecDeque;

fn spfa_negative_cycle(n: usize, adj: &Vec<Vec<(usize, f64)>>) -> bool {
    let mut dist = vec![0.0; n];
    let mut count = vec![0; n];
    let mut in_queue = vec![false; n];
    let mut queue = VecDeque::new();

    for i in 0..n {
        in_queue[i] = true;
        queue.push_back(i);
    }

    while let Some(u) = queue.pop_front() {
        in_queue[u] = false;
        for &(v, weight) in &adj[u] {
            if dist[v] > dist[u] + weight {
                dist[v] = dist[u] + weight;
                count[v] = count[u] + 1;
                if count[v] >= n {
                    return true; // Kitaran negatif dikesan
                }
                if !in_queue[v] {
                    queue.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    false
}

Dalam praktik, SPFA sering berjalan dalam $O(k \times E)$ di mana $k \ll V$, menjadikannya jauh lebih pantas untuk graf pasaran yang jarang.

4. Penyelidikan Moden: Algoritma RICH

Pada tahun 2024, penyelidik mencadangkan algoritma RICH (Rapid Identification of Cyclic High-profitability). Tidak seperti Bellman-Ford, RICH dioptimumkan khusus untuk graf kewangan di mana:

1. Graf bersaiz kecil hingga sederhana (ratusan aset).
2. Pemberat berubah setiap milisaat.
3. Kami perlu mencari kitaran yang paling menguntungkan, bukan sekadar kitaran mana-mana.

4.1 Inovasi Utama RICH

• Pemangkasan: Ia serta-merta membuang laluan yang tidak mungkin membawa kepada kitaran yang menguntungkan berdasarkan laluan terbaik yang diketahui semasa.
• Carian Berlapis: Ia mencari kitaran dengan panjang yang semakin meningkat (3-kaki, 4-kaki, 5-kaki) menggunakan pengoptimuman topeng bit.
• Kemas Kini Berperingkat: Daripada menjalankan semula algoritma penuh, ia hanya mengemas kini bahagian graf yang terjejas oleh perubahan harga.

5. Cabaran Pelaksanaan: Yuran dan Kecairan

Perdagangan sebenar tidak percuma. Kitaran berbilang kaki $(A \to B \to C \to A)$ menanggung tiga yuran perdagangan berasingan.

5.1 Menggabungkan Yuran

Kami mesti menyesuaikan pemberat tepi kami: $w = -\ln(R \times (1 - \text{fee}))$ Ini memangkas graf dengan ketara, kerana banyak kitaran teori dihapuskan oleh kos pelaksanaan.

5.2 Kecairan dan Gelinciran

Apabila anda membeli lebih banyak aset, harga naik (gelinciran). Kitaran yang kelihatan menguntungkan untuk $100 mungkin menjadi kerugian untuk$10,000. Model graf lanjutan menggunakan pemberat parametrik, di mana $w$ adalah fungsi volum $V$. Ini mengubah masalah dari carian laluan terpendek yang mudah kepada masalah Pengoptimuman Cembung pada graf.

6. Mengapa Rust?

Dalam dunia arbitraj, 100 mikrosaat adalah perbezaan antara keuntungan dan peluang yang "terlepas".

• Keselamatan Memori: Tiada jeda pengumpul sampah (GC) yang boleh membekukan bot pada saat kritikal.
• Abstraksi Tanpa Kos: Kami boleh menggunakan struktur graf aras tinggi tanpa kehilangan prestasi penunjuk mentah.
• Konkurensi: "Fearless Concurrency" Rust membolehkan kami menghurai suapan WebSocket dari 10 bursa secara selari dan mengemas kini graf bersama dengan selamat.

Kesimpulan

Algoritma graf adalah enjin di sebalik arbitraj kripto moden. Walaupun Bellman-Ford menyediakan asas, sistem moden menggunakan varian yang dioptimumkan seperti SPFA atau algoritma khusus seperti RICH.

Dalam bahagian seterusnya siri ini, kami akan melihat Arbitraj Niaga Hadapan-Spot, di mana kami mengembangkan graf kami dari pertukaran aset mudah untuk memasukkan kadar pembiayaan dan strategi tunai-dan-bawa.

Adakah anda membina sistem perdagangan kependaman rendah? Semak Templat HFT Rust Sumber Terbuka kami.