SPFA с нуля: ленивая версия Беллмана-Форда

Урок 7 курса "Собери своего арбитражного бота". В уроке 6 вы собрали Беллмана-Форда. Он работает, но тратит лишние усилия. Сегодня вы сделаете его ленивее.

Где Беллман-Форд тратит работу

В уроке 6 мы разобрали прямой вариант метода: заново проверять все дороги в каждом раунде. Это будет нашим ориентиром, потому что любой более быстрый метод должен давать те же ответы.

Беллман-Форд проверяет каждую дорогу в каждом раунде. Но дорога из A в B может улучшить значение для B, только если число у A только что стало меньше. Если A не менялся с прошлого просмотра его дорог, повторная проверка ничего не изменит.

Представьте учителя, который каждый день заново проверяет все 30 тетрадей с домашними заданиями, хотя что-то новое сдали только три ученика. Более ленивый и умный учитель держит список "учеников, у которых что-то изменилось" и проверяет только их. В этом и состоит вся идея SPFA (алгоритма быстрого поиска кратчайшего пути).

Идея

1. Держите очередь: линию узлов, которые надо обработать. Узлы встают в конец и выходят из начала.
2. Начните с того, что в очереди находится только начальный узел.
3. Возьмите передний узел A. Для каждой дороги из A в какой-нибудь B попробуйте улучшить значение (будет ли число у A плюс стоимость меньше числа у B?).
4. Если значение B улучшилось и B еще не ждет в очереди, поставьте его в конец.
5. Повторяйте, пока очередь не опустеет.

Если очередь пуста, все числа окончательны.

Разбор примера

Те же дороги, что в уроке 6: из S в A стоимость 4, из S в B стоимость 5, из A в B стоимость −2.

Начало: S = 0, A = ∞, B = ∞. Очередь: [S].

• Берем S. Дорога из S в A: 0 + 4 = 4 < ∞, значит A = 4, A встает в очередь. Дорога из S в B: 0 + 5 = 5 < ∞, значит B = 5, B встает в очередь. Очередь: [A, B].
• Берем A. Дорога из A в B: 4 − 2 = 2 < 5, значит B = 2. B уже есть в очереди, поэтому второй раз его не добавляем. Очередь: [B].
• Берем B. Из B не ведет ни одной дороги. Очередь: [].

Готово после проверки 3 дорог. Чтобы убедиться, Беллман-Форд проверил бы 3 дороги в раунде 1 и 3 дороги в раунде 2: 6 проверок. Здесь SPFA сделал вдвое меньше работы.

А что с отрицательными циклами?

Если достижим отрицательный цикл, некоторые узлы продолжают улучшаться и снова попадать в очередь бесконечно. Программа никогда не остановится. Нужен сигнал тревоги.

Сигнал такой: считайте, сколько раз каждый узел попадал в очередь. В графе без отрицательных циклов узел попадает туда не больше V − 1 раз (самый дешевый путь к нему использует не больше V − 1 дорог, и каждое попадание соответствует новому, более длинному пути). Поэтому, если узел попадает в очередь V раз, через него проходит отрицательный цикл.

Код

import math
from collections import deque

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"]
out = {n: [] for n in nodes}                       # дороги, исходящие из каждого узла
for (a, b), r in rates.items():
    out[a].append((b, -math.log(r)))

def spfa(nodes, out, start):
    dist = {n: math.inf for n in nodes}
    prev = {n: None for n in nodes}
    entered = {n: 0 for n in nodes}                # сколько раз n добавлялся в очередь
    dist[start] = 0.0
    queue, waiting = deque([start]), {start}
    checks = 0
    while queue:
        a = queue.popleft()
        waiting.discard(a)
        for b, w in out[a]:
            checks += 1
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                prev[b] = a
                if b not in waiting:
                    entered[b] += 1
                    if entered[b] >= len(nodes):   # сигнал тревоги
                        return ("negative cycle through", b, "after", checks, "checks")
                    queue.append(b)
                    waiting.add(b)
    return ("no negative cycle", {n: round(d, 4) for n, d in dist.items()}, checks)

print(spfa(nodes, out, "USD"))

Результат:

('negative cycle through', 'EUR', 'after', 13, 'checks')

SPFA подал сигнал тревоги. Чтобы получить сам круг, используйте предшественников так же, как в уроке 6: отступите от узла, вызвавшего сигнал, на V шагов, а затем пройдите по кругу. Попробуйте сделать это сами.

Скорость: тест, который можно запустить

Здесь рынок с 300 валютами, у каждой по 6 случайных пар. Курсы получены из скрытых истинных значений с комиссией 0.2 процента на каждую сделку, поэтому ни один круг не приносит прибыль (спокойный рынок). Мы считаем проверки дорог от одного и того же старта.

import math, random
from collections import deque
random.seed(1)
N = 300
nodes = list(range(N))
value = [random.uniform(1, 100) for _ in nodes]
edges, out = [], {n: [] for n in nodes}
for a in nodes:
    for b in random.sample(nodes, 6):
        if a != b:
            w = -math.log(value[a] / value[b] * 0.998)
            edges.append((a, b, w)); out[a].append((b, w))

def bf_work():
    dist = [math.inf] * N; dist[0] = 0.0; work = 0
    for _ in range(N - 1):
        changed = False
        for a, b, w in edges:
            work += 1
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w; changed = True
        if not changed: break
    return work

def spfa_work():
    dist = [math.inf] * N; dist[0] = 0.0; work = 0
    q, inq = deque([0]), {0}
    while q:
        a = q.popleft(); inq.discard(a)
        for b, w in out[a]:
            work += 1
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                if b not in inq: q.append(b); inq.add(b)
    return work

print("edges:", len(edges), "Bellman-Ford checks:", bf_work(), "SPFA checks:", spfa_work())

Результат тестового запуска:

edges: 1799 Bellman-Ford checks: 7196 SPFA checks: 1799

Здесь SPFA сделал четверть работы. На практике SPFA обычно намного быстрее на разреженных графах, к которым относятся крипторынки (каждая монета торгуется лишь с несколькими другими). Но худший случай SPFA так же плох, как у Беллмана-Форда: V × E, и редкие графы могут его вызвать. Ускорение зависит от формы данных, поэтому измеряйте на своих данных.

Что когда использовать

Попросите ИИ-агента написать и проверить код

Расплывчатый запрос:

Сделай Беллмана-Форда быстрее.

Запрос с названием метода и проверкой:

В bellman.py добавь spfa_find_cycle(rates), используя очередь, множество "в очереди", счетчик попаданий каждого узла в очередь и предшественников. Функция должна возвращать тот же цикл, что и find_cycle на примере с шестью курсами, и None, когда все курсы умножены на 0.95. Затем напиши bench.py, который строит случайный рынок из 300 валют с 6 парами у каждой (курсы из скрытых значений, умноженных на 0.998), считает проверки дорог для обоих алгоритмов от узла 0 и выводит оба числа. Не меняй find_cycle.

Вы должны увидеть, что у SPFA меньше проверок. Если агент показывает для этих данных у SPFA больше проверок, попросите его объяснить почему и не принимайте ответ "алгоритм лучше в теории".

Ваше упражнение

1. Запустите первую программу. Сделайте так, чтобы она возвращала сам круг через предшественников.
2. Запустите тест производительности. Измените число пар на валюту с 6 до 30. Выигрывает ли SPFA с тем же коэффициентом? Почему более плотный граф может изменить ответ?
3. Измените множитель комиссии 0.998 на 1.001 (рынок с бесплатными деньгами). Запустите spfa_work из теста от узла 0. Он никогда не остановится, потому что в нем нет сигнала тревоги. Остановите его с помощью Ctrl+C, затем добавьте сигнал "V попаданий в очередь" из первой программы и запустите снова. Сколько проверок ему нужно до сигнала?
4. Сохраните код как новую версию.

Что дальше

Оба алгоритма отвечают на вопрос "есть ли где-то прибыльный круг?". Настоящему боту нужно больше: лучший круг с ограниченным числом шагов, который находится снова и снова, пока меняются цены. В уроке 8 показано, как недавний исследовательский алгоритм RICH решает эту задачу.