Коммивояжёр с неравенством треугольника: дерево, обход и срезки

Если ты объяснишь, почему остовное дерево не тяжелее оптимального маршрута, где в алгоритме двойного дерева нужно неравенство треугольника и откуда у Кристофидеса 3/2, листай до «Теперь сам».

Как думаешь, что здесь нижняя граница

В прошлых уроках нижней границей была средняя нагрузка: её видно по входу. У коммивояжёра на восьми городах наилучший маршрут ищется перебором 7! / 2 = 2520 порядков, а на сотне - никак. Что можно посчитать быстро и про что точно известно, что лучший маршрут не короче?

Подумай до чтения. Сумма n самых коротких рёбер? Это граница, но слабая: самые короткие рёбра могут все сходиться в одном городе. Расстояние до самого дальнего города, умноженное на два? Тоже граница, тоже слабая. Нужна такая, у которой рядом лежит способ построить маршрут, - и такая есть в разделе о кратчайших путях и остовах.

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

Обход музея по плану коридоров. План - дерево: из холла расходятся крылья, из крыльев - залы. Чтобы увидеть все залы, можно идти вдоль стены, держась правой рукой: зайдёшь в каждый тупик и вернёшься, и по каждому коридору пройдёшь ровно дважды - туда и обратно.

Теперь представь, что в музее можно пройти из любого зала в любой напрямую, и прямой проход не длиннее обходного. Тогда возвраты по уже пройденным коридорам не нужны: увидев зал, сразу идёшь к следующему новому. Маршрут стал короче прогулки вдоль стены, а та была ровно вдвое длиннее плана коридоров.

Механизм: граница, обход, срезка

Задача. Города и расстояния между каждой парой; найти замкнутый маршрут через все города по разу с наименьшей суммой. Неравенство треугольника: для любых трёх городов d(a, c) ≤ d(a, b) + d(b, c) - дорога напрямую не длиннее дороги через третий город. Задачу с этим условием (и симметричными расстояниями) называют метрическим коммивояжёром; расстояния на плоскости ему подчиняются.

Граница. Убери из оптимального маршрута любое ребро - останется путь через все города. Путь - частный случай остовного дерева, значит, он не легче минимального: вес МОД ≤ OPT − ребро ≤ OPT. Минимальное остовное дерево (МОД) строится алгоритмом Прима за O(n²) на полном графе.

Двойное дерево. Обход дерева в глубину, записанный как прогулка, проходит каждое ребро дважды: её длина 2 · вес МОД ≤ 2 · OPT. Порядок первого посещения вершин (прямой порядок обхода) - это и есть маршрут: прогулка без повторов. Каждый пропущенный повтор заменяет кусок a → x → … → b прямым переездом a → b, и по неравенству треугольника он не длиннее.

Кристофидес (1976; Сердюков независимо, 1978). Двойка берётся из того, что каждое ребро дерева идёт дважды. Но дублировать нужно не всё: чтобы обойти граф, проходя каждое ребро ровно раз, достаточно, чтобы граф был связен и у всех вершин была чётная степень - тогда есть эйлеров цикл. Дерево связно, а вершин нечётной степени в нём чётное число. Соединим их минимальным по весу паросочетанием (набором рёбер без общих вершин, как в разделе о потоках, но покрывающим все нечётные вершины) и добавим к дереву: степени стали чётными, эйлеров цикл со срезками даёт маршрут. Вес паросочетания не больше OPT / 2: оптимальный маршрут, срезанный до нечётных вершин, распадается на два паросочетания, и лёгкое из них не тяжелее половины. Итого OPT + OPT / 2. Почти полвека 3/2 было лучшим, пока в 2020 году Карлин, Кляйн и Овейс Гарен не улучшили её на величину порядка 10⁻³⁶ - важно не число, а то, что граница оказалась не окончательной.

Правило

Минимальное остовное дерево не тяжелее оптимального маршрута - это нижняя граница. Прямой порядок обхода дерева даёт маршрут не длиннее 2 · вес МОД ≤ 2 · OPT, если расстояния подчиняются неравенству треугольника: только оно гарантирует, что срезка не удлиняет путь. Кристофидес достраивает дерево минимальным паросочетанием нечётных вершин и получает 3/2.

Разбор: восемь точек на плоскости

ostov - алгоритм Прима, он заодно запоминает, кто чей ребёнок в дереве; obhod - прямой порядок через стек; perebor - точный ответ, ветви и границы из раздела о переборе: путь, уже длиннее рекорда, дальше не продолжается.

import math

def rasst(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def ostov(tochki):
    n = len(tochki)
    v_dereve = [False] * n
    blizhe = [math.inf] * n
    roditel = [-1] * n
    deti = []
    for i in range(n):
        deti.append([])
    blizhe[0] = 0
    ves = 0
    for shag in range(n):
        u = -1
        for v in range(n):
            if not v_dereve[v] and (u == -1 or blizhe[v] < blizhe[u]):
                u = v
        v_dereve[u] = True
        ves = ves + blizhe[u]
        if roditel[u] >= 0:
            deti[roditel[u]].append(u)
        for v in range(n):
            d = rasst(tochki[u], tochki[v])
            if not v_dereve[v] and d < blizhe[v]:
                blizhe[v] = d
                roditel[v] = u
    return [ves, deti]

def obhod(deti):
    poryadok = []
    stek = [0]
    while len(stek) > 0:
        u = stek.pop()
        poryadok.append(u)
        for i in range(len(deti[u]) - 1, -1, -1):
            stek.append(deti[u][i])
    return poryadok

def dlina(tochki, marshrut):
    s = 0
    for i in range(len(marshrut)):
        s = s + rasst(tochki[marshrut[i - 1]], tochki[marshrut[i]])
    return s

def perebor(tochki, put, ostalis, proshli, luchshee):
    if proshli >= luchshee:
        return luchshee
    if len(ostalis) == 0:
        return min(luchshee, proshli + rasst(tochki[put[-1]], tochki[0]))
    for k in range(len(ostalis)):
        v = ostalis[k]
        shag = rasst(tochki[put[-1]], tochki[v])
        drugie = ostalis[:k] + ostalis[k + 1:]
        luchshee = perebor(tochki, put + [v], drugie, proshli + shag,
                           luchshee)
    return luchshee

tochki = [[0, 0], [2, 7], [6, 1], [8, 6], [3, 3], [9, 0], [5, 9], [1, 4]]
ves, deti = ostov(tochki)
marshrut = obhod(deti)
print(round(ves, 2), deti)
print(marshrut, round(dlina(tochki, marshrut), 2))
opt = perebor(tochki, [0], [1, 2, 3, 4, 5, 6, 7], 0, math.inf)
print(round(opt, 2), round(dlina(tochki, marshrut) / opt, 3))

24.14 [[7], [6], [5], [], [2], [], [3], [4, 1]]
[0, 7, 4, 2, 5, 1, 6, 3] 40.87
32.23 1.268

Дерево весит 24,14 - это нижняя граница, видная без перебора. Значит, оптимум не меньше 24,14, а маршрут двойного дерева (40,87) не длиннее 2 · 24,14 = 48,28. Перебор подтверждает: оптимум 32,23, отношение 1,268 - далеко от двойки.

Посмотри на сам маршрут: … 5, 1, 6 …. Город 5 стоит в правом нижнем углу (9, 0), город 1 - в левом верхнем (2, 7). Это срезка через всю карту: в дереве 1 висит на 7, и обход возвращается к нему после правого поддерева. Срезка законна и не длиннее обходного пути по дереву, но она же и показывает, откуда берётся потеря. Именно такие пересечения убирает локальный поискРазбирается в разделе 22, глава «Локальный поиск, отжиг, эвристики»: 2-opt: развернуть кусок маршрута и убрать пересечения следующей главы.

Разбор: где неравенство треугольника не выполняется

Пять городов, центр 0 в одном переезде от всех. Между окраинами есть дешёвые дороги 1-3, 3-2, 2-4 по 2, а остальные переезды между окраинами стоят 100 - например, через горы.

d = [[0, 1, 1, 1, 1],
     [1, 0, 100, 2, 100],
     [1, 100, 0, 2, 2],
     [1, 2, 2, 0, 100],
     [1, 100, 2, 100, 0]]

def dlina(marshrut):
    s = 0
    for i in range(len(marshrut)):
        s = s + d[marshrut[i - 1]][marshrut[i]]
    return s

def zamykanie(d):
    n = len(d)
    k = []
    for i in range(n):
        k.append(d[i][:])
    for t in range(n):
        for i in range(n):
            for j in range(n):
                if k[i][t] + k[t][j] < k[i][j]:
                    k[i][j] = k[i][t] + k[t][j]
    return k

print(dlina([0, 1, 2, 3, 4]), dlina([0, 1, 3, 2, 4]))
print(d[1][2], d[1][0] + d[0][2])
k = zamykanie(d)
print(k[1])
print(k[1][2] + k[2][3] + k[3][4] + k[4][0] + k[0][1])

204 8
100 2
[1, 0, 2, 2, 2]
8

Минимальное дерево - звезда с центром 0, вес 4. Прямой порядок обхода 0, 1, 2, 3, 4 даёт 204, а лучший маршрут 0, 1, 3, 2, 4 - 8. Отношение 25,5, и, меняя 100 на миллион, его можно сделать каким угодно. Причина во второй строке: d(1, 2) = 100, а через центр - 2. Срезка, которая по доказательству не удлиняет путь, здесь удлиняет его в пятьдесят раз.

Лечение, когда возвращаться в город можно (курьер может проехать через склад дважды): заменить расстояния кратчайшими путями - алгоритм Флойда-Уоршелла из раздела о кратчайших путях, функция zamykanie. Кратчайшие расстояния неравенству треугольника подчиняются всегда. В новой таблице d(1, 2) = 2, и тот же порядок 0, 1, 2, 3, 4 стоит 8 - каждый переезд на деле едет через центр. Если же каждый город строго по разу, лечения нет: без неравенства треугольникаРазбирается в разделе 22, глава «Пределы приближения - PTAS, APX и почему дальше нельзя»: Разрыв: почему некоторые задачи нельзя приблизить коммивояжёра нельзя приблизить ни с каким множителем, если P ≠ NP.

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

Метрику принимают на веру. Тарифы, где перелёт с пересадкой дешевле прямого, время в пробках, стоимость с платными дорогами - неравенство треугольника нарушается, и гарантия 2 исчезает молча. Проверка - тройной цикл по всем городам, O(n³), дешевле любого спора.

Путают дерево с маршрутом. Вес дерева - граница, а не ответ: маршрут из примера на 69% длиннее дерева. В отчёте пишут оба числа: «маршрут 40,87, лучший возможный - не короче 24,14».

Ждут от двойного дерева хорошего маршрута. Гарантия двойная, а на практике потеря 20-40% и видимые глазом пересечения. Двойное дерево - стартовая точка для улучшения, а не конечный ответ.

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

Развоз по городу, обход стеллажей сборщиком на складе, порядок сверления отверстий в плате, порядок съёмки точек дроном. Расстояния во всех этих задачах метрические или превращаются в метрические кратчайшими путями. Двойное дерево - двадцать строк кода и O(n²) времени, и оно отвечает на вопрос, который задают раньше, чем «как ехать»: «сколько это займёт хотя бы приблизительно». Вес дерева снизу, двойной вес сверху - вилка, внутри которой лежит лучший маршрут.

Теперь сам

1. Четыре города в вершинах квадрата со стороной 1. Чему равен вес МОД, длина лучшего маршрута и какую гарантию даёт двойное дерево?
2. Почему вес МОД не больше OPT, а не просто «примерно равен»? Укажи, какое ребро убрать.
3. Дерево весит 50. Двойное дерево построило маршрут длиной 97. В каких пределах лежит оптимум?