Урок 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 подешевле. Запишем новую стоимость. Этот шаг называют релаксацией дороги.
Алгоритм Беллмана-Форда просто снова и снова проверяет все дороги и выполняет релаксацию, пока оценки меняются.
Пример с расчетами
Есть три города 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 раундов.
Еще один раунд: как проявляется отрицательный цикл
Предположим, что сумма стоимостей дорог в круге меньше нуля. С каждым новым проходом по кругу значения будут становиться все меньше. Значит, улучшения не прекратятся.
Алгоритм Беллмана-Форда использует это свойство. Он выполняет 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 мы разберем прием, который позволяет пропустить большую часть этой работы.
Важные ограничения
- Алгоритм Беллмана-Форда возвращает один отрицательный цикл, а не самый выгодный.
- Курсы меняются, пока идут вычисления. Найденный круг — это снимок рынка на один момент.
- Алгоритм использует курсы вроде среднерыночных и не знает, сколько валюты можно продать или купить. Это этап 2 (уроки 9 и 10).
Попросим ИИ-агента написать и проверить код
Расплывчатый запрос:
Реализуй алгоритм Беллмана-Форда для поиска арбитража.
Запрос с проверкой:
Напиши файл bellman.py с функцией find_cycle(rates). Она принимает словарь {("USD","EUR"): 0.90, ...}, переводит курсы в веса с помощью отрицательного натурального логарифма, запускает алгоритм Беллмана-Форда с дополнительным раундом и хранением предшественников, а затем возвращает список названий валют в цикле или 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. Затем проверьте расчеты небольшим фрагментом кода.
- Узнайте, сколько обычных раундов нужно для этого графа, прежде чем изменения прекратятся. Добавьте счетчик.
Что дальше
В каждом раунде алгоритм Беллмана-Форда заново проверяет все дороги, даже те, которые не могли повлиять на результат. В уроке 7 мы разберем SPFA — ленивую версию, которая проверяет только дороги, начинающиеся в вершине, значение которой только что улучшилось.
