Рынок: выгодный круг Беллманом-Фордом и шум округления

Если ты умеешь найти и восстановить отрицательный цикл и знаешь, зачем сравнению на числах с плавающей точкой нужен допуск, листай до «Теперь сам».

Как думаешь, выгоден ли этот круг

На рынке три товара. Рыбу меняют на зерно по 1,05, зерно на соль по 1,05, соль на рыбу по 1 / 1,1025. Произведение курсов - ровно единица: круг честный, ни прибыли, ни убытка. Что скажет программа, которая ищет отрицательный цикл по весам −log курса?

Ответь себе до чтения. По математике сумма −log равна −log 1 = 0, цикл не отрицательный, выгоды нет. Но компьютер хранит 1 / 1,1025 и логарифмы не точно, а с ошибкой в последнем знаке. Ошибка может лечь в любую сторону - и если она отрицательная, честный круг станет «выгодным», а игрок, нашедший его, - богаче на ноль целых ноль десятых, бесконечно.

На что это похоже

Обмен валют в трёх обменниках подряд с округлением до копейки. Курсы подобраны «в ноль», но каждый обменник округляет по-своему, и после круга у тебя то на копейку больше, то на копейку меньше. Банк, который хочет поймать арбитраж, обязан решить, что считать прибылью: копейку от округления или реальную разницу курсов.

Механизм: отрицательный цикл, родители и допуск

Беллман-Форд ищет кратчайшие пути при отрицательных весах: V − 1 раз пробегает все рёбра и улучшает dist[куда], если dist[откуда] + вес меньше. Если и на V-м круге что-то улучшилось, в графе есть отрицательный цикл, достижимый от старта. Чтобы найти выгодный круг где угодно на рынке, берут фиктивный старт с ребром веса 0 в каждый товар - то есть просто начинают с dist = 0 у всех.

Сам цикл восстанавливают по родителям. Вершина, улучшенная на последнем круге, лежит на цикле или после него. V шагов по родителям гарантированно заводят внутрь цикла: путь по родителям длиннее V вершин обязан повторить вершину. Дальше идут по родителям, пока не вернутся в ту же вершину, - это и есть круг, только в обратном порядке.

Сравнение dist[откуда] + вес < dist[куда] на числах с плавающей точкой ненадёжно у нуля: суммы логарифмов несут ошибку порядка 10⁻¹⁶ на операцию. Поэтому улучшение засчитывают, только если оно больше допуска - порога, ниже которого разница считается шумом. Выбирают его между двумя числами. Снизу - накопленная ошибка: круг из k сделок складывает k логарифмов, каждый с ошибкой около 10⁻¹⁶ от своей величины, - для k до сотни и курсов от 0,001 до 1000 это меньше 10⁻¹². Сверху - наименьшая выгода, которую надо ловить: −log(1 + p) ≈ −p, и выгода в 0,0001% за оборот - это 10⁻⁶. Порог 10⁻¹² лежит между ними с запасом в обе стороны. Одна оговорка: допуск применяют к каждому улучшению отдельно, и выгода, размазанная по многим сделкам мельче допуска каждая, тоже пропадёт. Поэтому порог берут меньше выгоды на ОДНУ сделку, а не на весь круг.

Правило

Выгодный круг обмена - отрицательный цикл по весам −log курса: Беллман-Форд с dist = 0 у всех товаров находит его за V · E и восстанавливает по родителям. Сравнения на числах с плавающей точкой делают с допуском: без него честный круг объявляется выгодным, а допуск сам решает, какая выгода слишком мала, чтобы её замечать.

Разбор: круг на шести товарах

Шесть товаров, четырнадцать сделок. Единственный выгодный круг тот же, что в уроке о техзадании, но искать его теперь будет не перебор, а Беллман-Форд.

import math

tovary = ["рыба", "зерно", "доски", "камень", "соль", "железо"]
# [что отдаём, что получаем, сколько дают за единицу]
sdelki = [[0, 1, 3], [1, 0, 0.3], [1, 2, 0.45], [2, 1, 2],
          [2, 3, 0.8], [3, 0, 0.97], [3, 4, 1.4], [4, 3, 0.6],
          [4, 5, 0.25], [5, 4, 3.9], [5, 0, 2.4], [0, 5, 0.4],
          [1, 4, 0.2], [4, 2, 0.7]]
N = len(tovary)
DOPUSK = 1 / 10 ** 12           # меньше этого - шум округления

def vygodnyj_krug():
    # вес сделки - -log курса; выгодный круг - отрицательный цикл.
    # Фиктивный старт: dist = 0 у всех товаров сразу (раздел 11)
    dist = [0] * N
    roditel = [-1] * N
    rasslableno = -1
    proverok = 0
    for krug in range(N):
        rasslableno = -1
        for s in sdelki:
            proverok = proverok + 1
            ves = -math.log(s[2])
            if dist[s[0]] + ves < dist[s[1]] - DOPUSK:
                dist[s[1]] = dist[s[0]] + ves
                roditel[s[1]] = s[0]
                rasslableno = s[1]
    if rasslableno == -1:
        return [[], proverok]
    # на N-м круге улучшение было - вершина на цикле или за ним;
    # N шагов по родителям гарантированно заводят внутрь цикла
    v = rasslableno
    for i in range(N):
        v = roditel[v]
    krug = [v]
    u = roditel[v]
    while u != v:
        krug.append(u)
        u = roditel[u]
    krug.append(v)
    krug.reverse()
    return [krug, proverok]

otvet = vygodnyj_krug()
nazv = []
proizv = 1
for i in range(len(otvet[0])):
    nazv.append(tovary[otvet[0][i]])
    if i > 0:
        for s in sdelki:
            if s[0] == otvet[0][i - 1] and s[1] == otvet[0][i]:
                proizv = proizv * s[2]
print("круг:", " -> ".join(nazv))
print("за оборот:", round(proizv, 4), "| проверок сделок:", otvet[1])

круг: камень -> рыба -> зерно -> доски -> камень
за оборот: 1.0476 | проверок сделок: 84

Шесть кругов по четырнадцати сделкам - 84 проверки, и круг найден вместе с маршрутом: начинать можно с любого товара на нём, выгода та же, 4,76% за оборот. Простых кругов на этом рынке 15, но на тридцати товарах, где меняется всё на всё, их астрономически много - а Беллман-Форд сделает 30 · E проверок. Граница правила: алгоритм находит ОДИН отрицательный цикл, а не самый выгодный. Найти круг с наибольшей выгодой за оборот - задача другая и в общем случае трудная, но игре это и не нужно: любой выгодный круг - уже дыра, которую закрывают курсами.

Разбор: честный круг и шум округления

Три товара, курсы подобраны так, что произведение - ровно 1. Запускаем тот же алгоритм без допуска и с допуском 10⁻¹².

import math

# честный рынок: курсы подобраны так, что круг даёт ровно 1
sdelki = [[0, 1, 1.05], [1, 2, 1.05], [2, 0, 1 / 1.1025]]
N = 3

def est_krug(dopusk):
    # Беллман-Форд с фиктивным стартом: улучшение на N-м круге -
    # отрицательный цикл, то есть «выгодный» круг обмена
    dist = [0] * N
    for krug in range(N):
        uluchsheno = False
        for s in sdelki:
            ves = -math.log(s[2])
            if dist[s[0]] + ves < dist[s[1]] - dopusk:
                dist[s[1]] = dist[s[0]] + ves
                uluchsheno = True
    return uluchsheno

proizv = 1
summa = 0
for s in sdelki:
    proizv = proizv * s[2]
    summa = summa - math.log(s[2])
print("произведение курсов:", proizv)
print("сумма -log меньше нуля:", summa < 0)
print("без допуска - выгодный круг:", est_krug(0))
print("с допуском 10^-12 -", "выгодный круг:", est_krug(1 / 10 ** 12))

произведение курсов: 1.0
сумма -log меньше нуля: True
без допуска - выгодный круг: True
с допуском 10^-12 - выгодный круг: False

Произведение курсов вышло ровно 1.0, а сумма −log - отрицательной, на 10⁻¹⁷: логарифм и деление 1 / 1,1025 округлились так, что ошибки не сократились. Алгоритм без допуска честно нашёл «отрицательный цикл» - игроку сообщат о выгодном круге, которого нет. Допуск убрал ложную тревогу. Граница правила: допуск - это решение, а не исправление. Настоящий круг с выгодой 10⁻¹³ тоже станет невидимым; для игры это неважно - выгоду в стотриллионную долю никто не заметит, - а для бухгалтерии недопустимо. Там курсы хранят точными дробями или целыми в копейках и сравнивают произведения числителей и знаменателей без логарифмов - длинная арифметика из раздела 18 это позволяет.

Что ломается без этого

Ложный арбитраж. Монитор экономики каждые пять минут сообщает о выгодном круге, админы проверяют руками - выгоды ноль. Через неделю на сообщения перестают смотреть, и настоящую дыру пропускают.

Круг без маршрута. Алгоритм ответил «отрицательный цикл есть», но не сказал какой - и геймдизайнер перебирает курсы вслепую.

Перебор кругов. На десяти товарах всё работало, после патча с тридцатью товарами проверка экономики не закончилась.

Зачем это в работе

Поиск арбитража между валютными парами и биржами, проверка тарифов на «можно обойти, купив по частям», обнаружение циклов в графе обмена баллов лояльности - всё это отрицательный цикл после логарифма. А допуск в сравнении чисел с плавающей точкой нужен везде: в геометрии раздела 23, в физике игры, в финансах, - и везде он решает, где кончается шум.

Теперь сам

1. Курсы: рыба → соль 2, соль → железо 0,7, железо → рыба 0,75. Выгоден ли круг? Чему равна сумма −log с точностью до сотых?
2. Беллман-Форд на 40 товарах и 300 сделках: сколько проверок сделок в худшем случае?
3. Почему после V шагов по родителям вершина обязательно на цикле?