Цикл с наибольшей прибылью в день: среднее и отношение на цикле

Если ты умеешь сводить цикл с наименьшим отношением к отрицательному циклу при весах c − λ·t и знаешь формулу Карпа, листай до «Теперь сам».

Как думаешь, какой круг выгоднее

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

Прежде чем читать дальше, попробуй угадать ответ на маленьком примере. Круг A → B → A: рейсы с прибылью 10 за 2 дня и 2 за 1 день. Круг A → C → A: 30 за 9 дней и 0 за 1 день. Какой круг лучше по прибыли за рейс и какой - по прибыли за день? И почему «найти самый прибыльный цикл» без деления не имеет смысла?

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

Выбор подработки на долгий срок. Одна приносит 30 тысяч за проект, но проект идёт десять дней. Другая - 12 тысяч за три дня. Сравнивать по сумме за проект бессмысленно: важна ставка за день, потому что работать будешь не один проект, а год. Самая выгодная подработка - не самая дорогая, а с лучшей ставкой, и «лучшая ставка» - это отношение, а не сумма.

Механизм: поиск по ответу и формула Карпа

НАИМЕНЬШЕЕ ОТНОШЕНИЕ Σc / Σt по циклам (t > 0)

цикл с Σc / Σt < λ  ⇔  Σc − λ·Σt < 0  ⇔  Σ(c − λ·t) < 0
                     ⇔  при весах c − λ·t есть отрицательный цикл

двоичный поиск по λ:
    отрицательный цикл есть  → оптимум < λ:  hi = λ
    нет                       → оптимум ≥ λ:  lo = λ
каждая проверка - Беллман-Форд, O(V·E); итераций - по нужной точности

Признак «есть цикл с отношением меньше λ» монотонен по λ: если такой цикл есть при λ, он есть и при любом большем. Поэтому двоичный поиск по ответу, знакомый по разделу о поиске, работает и здесь.

Для СРЕДНЕГО веса ребра (все t = 1) есть точный ответ без поиска:

АЛГОРИТМ КАРПА
D[k][v] - наименьший вес пути ровно из k рёбер, кончающегося в v
          (стартовать можно из любой вершины: D[0][v] = 0)
наименьшее среднее =
    min по v  max по k < V  (D[V][v] − D[k][v]) / (V − k)
таблица D - V проходов по рёбрам: O(V·E)

Идея формулы: путь из V рёбер обязательно содержит цикл; разность D[V][v] − D[k][v] - вес куска, который можно «выкинуть», и максимум по k проверяет, нельзя ли сделать путь лучше, заменив кусок. Доказательство длинное, а результат - точное рациональное число без всякой точности поиска.

Правило

Цикл с наименьшим отношением Σc / Σt ищут поиском по ответу: при весах c − λ·t отрицательный цикл есть ровно тогда, когда оптимум меньше λ; признак монотонен, проверка - Беллман-Форд, O(V·E) на шаг. Цикл с наименьшим средним весом (t = 1) находит точно алгоритм Карпа за O(V·E) по таблице наименьших весов путей ровно из k рёбер. Наибольшее отношение - наименьшее для весов со знаком минус.

Разбор: два круга судна

круг A→B→A: прибыль 10 + 2 = 12, дней 2 + 1 = 3 → 4 в день,  6 за рейс
круг A→C→A: прибыль 30 + 0 = 30, дней 9 + 1 = 10 → 3 в день, 15 за рейс

проверка λ = 3.5 (стоимость c = −прибыль, вес c + λ·t для «прибыли > λ»):
    A→B→A: −12 + 3.5·3  = −1.5  < 0
    → цикл с прибылью больше 3.5 в день есть
проверка λ = 4.5:
    A→B→A: −12 + 4.5·3  = +1.5
    A→C→A: −30 + 4.5·10 = +15     → отрицательных нет: больше 4.5 нельзя

По прибыли за рейс лучше A→C→A (15 против 6), по прибыли в день - A→B→A (4 против 3). Двоичный поиск между 3.5 и 4.5 сойдётся к 4.

Разбор: сорок портов, двести рейсов

Программа строит случайную сеть рейсов с прибылью от −20 до 50 и длительностью от 1 до 9 дней, ищет круг с наибольшей прибылью за рейс точно - Карпом - и поиском по ответу, а потом круг с наибольшей прибылью в день.

import random
from fractions import Fraction

rng = random.Random(15)
V = 40
rebra = []                            # (откуда, куда, стоимость, дни)
for _ in range(200):                  # стоимость = −прибыль рейса
    u, v = rng.randrange(V), rng.randrange(V)
    if u != v:
        rebra.append((u, v, -rng.randint(-20, 50), rng.randint(1, 9)))


def karp():                           # точный минимум среднего веса
    INF = float("inf")
    D = [[INF] * V for _ in range(V + 1)]
    D[0] = [0] * V                    # старт отовсюду: фиктивный исток
    for k in range(1, V + 1):
        for u, v, c, _ in rebra:
            if D[k - 1][u] + c < D[k][v]:
                D[k][v] = D[k - 1][u] + c
    best = None
    for v in range(V):
        if D[V][v] == INF:
            continue
        hudshee = max(Fraction(D[V][v] - D[k][v], V - k)
                      for k in range(V) if D[k][v] < INF)
        best = hudshee if best is None else min(best, hudshee)
    return best


def otricatelnyj_cikl(lam, vremya):   # Беллман-Форд на весах c − λ·t
    d = [0.0] * V
    for _ in range(V):
        izm = False
        for u, v, c, t in rebra:
            w = c - lam * (t if vremya else 1)
            if d[u] + w < d[v] - 1e-12:
                d[v] = d[u] + w
                izm = True
        if not izm:
            return False
    return True


def po_otvetu(vremya):                # двоичный поиск по λ
    lo, hi = -50.0, 50.0
    for _ in range(50):
        mid = (lo + hi) / 2
        if otricatelnyj_cikl(mid, vremya):
            hi = mid                  # есть цикл с отношением < mid
        else:
            lo = mid
    return hi


k = karp()
print("прибыль за рейс, Карп:          ", -k)
print("прибыль за рейс, поиск по ответу:", round(-po_otvetu(False), 6))
print("прибыль за день, поиск по ответу:", round(-po_otvetu(True), 6))

прибыль за рейс, Карп:           214/5
прибыль за рейс, поиск по ответу: 42.8
прибыль за день, поиск по ответу: 16.0

Карп дал точную дробь 214/5 - круг из пяти рейсов с общей прибылью 214; поиск по ответу нашёл то же 42.8 (печатаем шесть знаков после запятой, совпали все). Лучший круг по прибыли в день приносит 16 - это другой круг: у круга Карпа прибыль 214, и при 16 в день его рейсы длились бы 13.375 дня, а дни целые.

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

Первая ошибка - искать «самый прибыльный цикл» по сумме: если есть хоть один цикл с положительной прибылью, по нему можно ходить бесконечно, и «максимум суммы» бесконечен - вопрос имеет смысл только для отношения или среднего. Вторая - взять отношение средних вместо отношения сумм: (10/2 + 2/1) / 2 не равно 12/3. Третья - забыть, что времена должны быть положительными: при t = 0 на цикле отношение не определено, а монотонность признака по λ ломается. Четвёртая - сравнивать числа с плавающей точкой без допуска: в программе проверка d[u] + w < d[v] − 1e−12, иначе ошибки округления порождают «отрицательные циклы» из нуля.

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

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

Теперь сам

Три круга: P - стоимость 12 за 4 рейса, Q - стоимость 9 за 2 рейса, R - стоимость 20 за 8 рейсов (стоимость - сумма весов, рейсы - число рёбер). Какой цикл даст алгоритм Карпа как цикл с наименьшим средним весом? Что покажет проверка при λ = 2.6?