4. 套利路径搜索：DFS找环、Bellman-Ford检测负环、路径剪枝优化

套利路径搜索，说白了就是在一个汇率网络中找「赚钱的环」。

你想想看，我们手里有几十个币种，两两之间都有汇率。如果从A币出发，经过一系列兑换，最后回到A币时钱变多了——这就是套利机会。我刚开始做这个系统时，以为直接暴力搜索所有路径就行，结果发现币种一多，路径数量是指数级爆炸的。嗯，这里必须上点算法功夫。

4.1 问题建模：把套利变成图论问题

先把问题抽象一下。每个币种是一个节点，每条兑换路径是一条有向边，边的权重是汇率取负对数后的值。

为什么要取负对数？因为套利的本质是找乘积大于1的环。比如：
1 USDT → 6.5 CNY → 0.9 EUR → 1.01 USDT
乘积 = 6.5 × 0.9 × 1.01 ≈ 5.91，这明显不对——等等，我举的例子有问题。

实际汇率应该是：1 USDT = 6.5 CNY，1 CNY = 0.13 EUR，1 EUR = 1.15 USDT。
乘积 = 6.5 × 0.13 × 1.15 ≈ 0.97，小于1，亏钱了。

如果乘积大于1，比如1.02，就说明有2%的套利空间。但图论算法通常处理的是「路径和」而不是「路径积」。所以我们对汇率取负对数：

weight = -ln(汇率)

这样一来，找乘积大于1的环，就变成了找路径和为负数的环——也就是负环。

4.2 深度优先搜索(DFS)找环

DFS找环是最直观的方法。从每个币种出发，沿着兑换路径走，如果走回了起点，就找到了一个环。

我个人习惯用递归实现，配合一个访问标记数组。但要注意：不能简单地标记「已访问」就跳过，因为同一个节点可以在不同路径中被多次访问。

def find_cycles_dfs(graph, max_depth=5):
    cycles = []
    
    def dfs(current, start, path, visited, depth):
        if depth > max_depth:
            return
        for neighbor, rate in graph[current].items():
            if neighbor == start and depth >= 2:
                # 找到了一个环
                cycles.append((path + [neighbor], calc_product(path, neighbor)))
                continue
            if neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor, start, path + [neighbor], visited, depth + 1)
                visited.remove(neighbor)
    
    for node in graph:
        dfs(node, node, [node], {node}, 0)
    
    return cycles

我在项目中遇到过一个问题：币种一多（比如30个以上），DFS的搜索空间就爆炸了。每个节点平均有10条边，深度5层，那就是10^5 = 10万条路径。如果再考虑所有起点，那就是300万条——这还只是5层。

4.3 Bellman-Ford算法检测负环

DFS虽然直观，但效率太低。真正工业级用的是Bellman-Ford算法。

Bellman-Ford原本是求单源最短路径的，但它有个绝活：可以检测负环。算法会迭代V-1轮（V是节点数），每轮松弛所有边。如果第V轮还能松弛，说明存在负环。

def bellman_ford_detect_negative_cycle(graph, source):
    # 初始化距离
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    predecessor = {node: None for node in graph}
    
    # V-1轮松弛
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    predecessor[v] = u
    
    # 第V轮检测
    for u in graph:
        for v, weight in graph[u].items():
            if dist[u] + weight < dist[v]:
                # 存在负环！回溯路径
                cycle = []
                visited = set()
                current = v
                while current not in visited:
                    visited.add(current)
                    cycle.append(current)
                    current = predecessor[current]
                cycle = cycle[cycle.index(current):]
                cycle.append(current)
                return cycle[::-1]
    
    return None

说白了，Bellman-Ford就是通过「多轮松弛」来逼近最短路径。如果V轮之后还能更新，说明路径可以无限缩短——也就是存在负环。

4.4 路径剪枝优化

算法选好了，但实际数据中还有很多「假机会」。比如一个环的套利空间只有0.01%，扣掉手续费还亏钱。所以必须做剪枝。

我常用的剪枝策略有四种：

剪枝策略	说明	效果
最小套利阈值	只保留套利空间 > 0.1% 的环	过滤掉90%的无效路径
最大深度限制	路径长度不超过5跳	控制搜索空间
手续费预扣	每条边加上0.1%的手续费	避免纸上富贵
热门币种优先	只搜索交易量前20的币种	聚焦流动性好的机会

def prune_and_search(graph, min_profit=0.001, max_depth=5):
    # 预扣手续费
    fee_rate = 0.001
    for u in graph:
        for v in graph[u]:
            graph[u][v] -= fee_rate
    
    # 只保留热门币种
    hot_coins = get_top_volume_coins(20)
    pruned_graph = {c: graph[c] for c in hot_coins if c in graph}
    
    # 用Bellman-Ford搜索
    results = []
    for source in hot_coins:
        cycle = bellman_ford_detect_negative_cycle(pruned_graph, source)
        if cycle:
            profit = calculate_profit(cycle, original_rates)
            if profit > min_profit:
                results.append((cycle, profit))
    
    return sorted(results, key=lambda x: -x[1])

4.5 知识体系总览

下面这张图总结了套利路径搜索的完整流程：

嗯，到这里套利路径搜索的核心内容就讲完了。DFS适合小规模数据快速验证，Bellman-Ford才是生产环境的首选。加上合理的剪枝策略，你就能在毫秒级内找到真正的套利机会。

---

公众号:蓝海资料掘金营，微信deep3321