文章合集引擎基础设施策略项目
文章/套利

从零认识 RICH：用颜色编码寻找短盈利环

套利课程第 8 课。了解机器人为什么需要限制步数的环、RICH 算法（VLDB 2025）背后的颜色编码技巧、一份可运行的小型 Python 实现，以及坦诚说明哪些内容做了简化。

10 分钟阅读套利 课程 初学者

《打造自己的套利机器人》课程第 8 课。Bellman-Ford 和 SPFA 能找到任意一个可盈利的环。今天我们来了解一种近期研究算法的核心思路，它能找到不错的短环。

为什么“任意一个环”还不够

假设 Bellman-Ford 找到了一个有 9 步的盈利环。每一步都是一笔交易，每笔交易都有手续费、延迟，而且在交易完成前价格可能会变化。在区块链交易所，每一步还可能要付网络费用。和一个利润稍低的 3 步环相比，9 步环在实际中几乎总是更差。

所以机器人要解决的是另一个问题：寻找步数不超过 k 的盈利环。计算机科学家把它称为 k 跳负环问题。机器人会选一个 k（常见的是 3、4 或 5）。

本课介绍的研究论文是《RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage》（Luo、Jiang 等人，PVLDB 第 18 卷，VLDB 2025）。作者报告称，RICH 在加密货币和外汇数据上的速度最高可达早期方法的 32.7 倍。它的基础是一个古老的技巧——颜色编码，再加上一些减少计算量的工程方法。今天我们实现核心技巧，先不讲工程部分。本课的简化版本不是论文中的代码。

直接穷举的方法及其局限

要从起点寻找步数不超过 k 的最佳环，可以尝试所有长度不超过 k 的路径。如果有 300 种货币、每种有 6 个交易对，那么每个起点出发、长度为 4 的路径大约有 6⁴ = 1296 条，数量不多。如果这 300 种货币每种都和另外 100 种交易，那么就是 100⁴ = 每个起点 1 亿条路径，这就太多了。

更聪明的方法是使用动态规划：记下每个节点在每个步数下到达它的最低成本。这正是把轮数限制为 k 的 Bellman-Ford。问题在于，走 k 步成本最低的路径可能会重复经过同一种货币。例如 USD、EUR、USD、EUR、USD 这条 4 步路径并不是一个真正的新机会，只是把 2 步的环重复走了两遍。我们想要的是每种货币只经过一次的环，这叫简单环。强制路径不能重复节点，就是问题变难的原因。

颜色编码技巧

这个技巧听起来有点傻，但很有效。

  1. 从 k 种颜色中随机给每种货币一种颜色。（如果 k = 3，每种货币随机涂成红色、绿色或蓝色。）
  2. 现在只寻找每一步颜色都不同的环：一种红色、一种绿色、一种蓝色。这样的环不可能重复经过同一种货币，因为重复货币会重复颜色。
  3. 这个受限搜索很容易，因为你只需要记住已经使用了哪些颜色，而不用记住哪些货币。k 种颜色只有 2ᵏ 种已用颜色集合。k = 3 时有 8 种，k = 5 时有 32 种。
  4. 某个真正的盈利环可能会被漏掉，因为它的两种货币碰巧分到了相同颜色。但如果重新随机上色并重复搜索，就有机会找到它。一条包含 k 种货币的环被分到 k 种不同颜色的概率是 k!/kᵏ（k = 3 时：6/27，约 22%；k = 4 时：24/256，约 9%）。重复 50 或 100 次后，漏掉它的可能性就很小了。

打个比方：给人群中的每个人随机涂上三种颜色之一，然后寻找由三种不同颜色的人组成的小组。换一组新的随机颜色后再找一次，如此重复。每一组三个真正的朋友，迟早会同时得到三种不同颜色。

一起看一个小例子

货币：USD、EUR、GBP、JPY。寻找经过 USD、步数不超过 3 的最佳环。

假设本轮随机得到的颜色是：USD 红色、EUR 绿色、GBP 蓝色、JPY 绿色。

搜索会保存一张表。每一行表示：“我现在在这个节点，用过这些颜色，目前最低成本是这个数，路径是这条。”

  • 开始：位于 USD，使用了 {红色}，成本为 0。
  • 第 1 步：从 USD 到 EUR（绿色，未使用过）：到达 EUR，使用 {红色、绿色}，成本 +0.1054。从 USD 到 GBP（蓝色）：到达 GBP，使用 {红色、蓝色}，成本 +0.2877（0.75 的权重）。
  • 第 2 步：从 EUR 到 GBP（蓝色，未使用过）：到达 GBP，使用 {红色、绿色、蓝色}，成本为 0.1054 + 0.1278 = 0.2332。从 EUR 到 JPY（绿色）：绿色已经用过，跳过。
  • 闭合成环：从 GBP 回到 USD 的成本为 −0.2624。总成本为 0.2332 − 0.2624 = −0.0292。总成本为负，因此 USD、EUR、GBP、USD 是一个盈利的简单环。

如果颜色是 USD 红色、EUR 绿色、GBP 绿色，本轮搜索就会跳过这个环（EUR 和 GBP 都是绿色），之后一轮用不同颜色时就有机会找到它。

代码

import math, random

random.seed(7)
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,
         ("USD", "JPY"): 150.0, ("JPY", "USD"): 0.0066,
         ("EUR", "JPY"): 160.0, ("JPY", "EUR"): 0.0062}
nodes = sorted({n for edge in rates for n in edge})
w = {edge: -math.log(r) for edge, r in rates.items()}

def best_cycle_through(start, k, rounds=200):
    """Cheapest cycle through `start` with at most k steps, by colour-coding."""
    best = (math.inf, None)
    for _ in range(rounds):
        colour = {n: random.randrange(k) for n in nodes}
        # table[(node, 已用颜色集合)] = (cost, path)；集合用位掩码表示
        table = {(start, 1 << colour[start]): (0.0, [start])}
        for _step in range(k - 1):
            for (node, used), (cost, path) in list(table.items()):
                for (a, b), wt in w.items():
                    if a != node or b == start:
                        continue
                    bit = 1 << colour[b]
                    if used & bit:
                        continue                      # 这种颜色已经用过
                    key = (b, used | bit)
                    if key not in table or cost + wt < table[key][0]:
                        table[key] = (cost + wt, path + [b])
        for (node, used), (cost, path) in table.items():
            if (node, start) in w and cost + w[(node, start)] < best[0]:
                best = (cost + w[(node, start)], path + [start])
    return best

cost, path = best_cycle_through("USD", 3)
print(path, "cost", round(cost, 4), "money x", round(math.exp(-cost), 4))

输出：

['USD', 'EUR', 'GBP', 'USD'] cost -0.0292 money x 1.0296

程序找到了这条三步盈利环，它的收益倍数为 1.0296。

这个简化版本省略了什么

  • 它在内层循环中扫描所有边，速度较慢。真正的实现会把出边存放在每个节点下面。
  • 它没有预先缩减图。论文介绍了图缩减和紧凑编码，它们是大部分提速的来源。
  • 它给出的结果带有随机性：随机颜色可能会漏掉某个环，但增加轮数后，漏掉的概率会降低。
  • 它只处理一个起点。机器人会遍历每个起点，或者让所有起点共用一张表。

把本课当作一种理解颜色编码如何缩小搜索范围的方法（只有 2ᵏ 种颜色集合），至于工程实现，可以阅读论文。

什么时候值得用？

如果只需要知道是否存在任何盈利环，就用 Bellman-Ford 或 SPFA。如果很多步的环对你没有用（因为手续费、延迟、网络费用），就用颜色编码这类限制步数的搜索方法；这种情况几乎总是会遇到。对于 k 较小、包含几百种货币的图，搜索成本足够低，可以在每次价格更新时运行。

让 AI 智能体编写并测试代码

一个含糊的请求：

实现 RICH。

一个说明范围和检查方法的请求：

不要实现完整的 RICH 论文。编写 colour_cycle.py，实现函数 best_cycle_through(start, k, rounds)，通过颜色编码寻找经过起始货币、步数不超过 k 的最低成本简单环：给每种货币随机分配颜色，使用以 (node，已用颜色的位掩码) 为键的表，并重复多轮随机着色。测试：使用本课中的 10 种汇率，起点为 USD、k = 3 时，必须返回 USD、EUR、GBP、USD，收益倍数为 1.0296。测试 2：把所有汇率乘以 0.95 时，必须返回没有负成本的结果。请按节点存储出边，不要扫描所有边。

然后问智能体：“和论文相比，你省略了哪些内容？”好的智能体会列出省略的部分。如果它声称自己实现了完整论文，不要轻信。

练习

  1. 运行代码。你应该会看到收益倍数 1.0296。
  2. 把 rounds 从 200 改成 3、5 和 10，每个设置使用不同随机种子运行 20 次。漏掉这个环的次数是多少？与每轮 k!/kᵏ = 6/27 的概率对比一下（k = 3）。
  3. 手算 10 轮后漏掉一个三种货币环的概率：(1 − 6/27)¹⁰ ≈ 0.08。
  4. 手算 USD、JPY、EUR、USD 这条环的汇率乘积（150 × 0.0062 × 1.10）。结果是 1.023，这是第二条盈利环，收益比第一条小。用 k = 3 和 rounds = 200 运行代码，确认程序更喜欢第一条环，然后根据权重说明原因。

接下来学什么

世界 2 到此结束。现在你的第一阶段程序已经能在汇率图中寻找盈利环。但这些汇率都是盘口最优价，只适用于极小的交易量。世界 3 将打开订单簿，研究一个环实际能承载多少资金。第 9 课从读取和遍历订单簿开始。

继续阅读