Гамильтонов цикл и коммивояжёр: трудность порядка

Если ты определишь гамильтонов цикл, сведёшь его к задаче коммивояжёра и объяснишь, почему отсутствие цикла труднее показать, чем его наличие, - листай до «Теперь сам».

Как думаешь, сколько порядков у двадцати адресов

Курьер выезжает со склада, должен побывать по двадцати адресам и вернуться. Адреса можно объезжать в любом порядке.

Ответь себе до чтения: сколько существует разных маршрутов? Первый адрес выбирается двадцатью способами, второй - девятнадцатью, и так далее: 20!, около 2,4 · 10¹⁸; если не различать направление обхода - вдвое меньше. Склад - закреплённое начало, поэтому для двадцати одной точки порядков 20!, а не 21!. При миллиарде маршрутов в секунду на перебор этой половины ушло бы почти сорок лет. Тридцать адресов - уже 10³². И это задача, которую логистическая компания решает каждое утро для каждой машины.

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

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

И здесь та же несимметричность, что у всех задач из NP. Нашёл маршрут - показал его, и все убедились. Не нашёл - остаётся вопрос, плохо искал или маршрута нет.

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

Гамильтонов цикл в графе - цикл, который проходит через каждую вершину ровно один раз. Задача: есть ли он. Она лежит в NP - сертификат - порядок вершин - и NP-полна: к ней сводится 3-SAT. Сведение громоздкое, с отдельным устройством на каждую переменную и скобку, и здесь не приводится.

Необходимые условия просты: граф связен, у каждой вершины не меньше двух соседей, удаление одной вершины не разрывает граф. Достаточные условия тоже есть: например, если вершин n не меньше трёх и у каждой не меньше n / 2 соседей, цикл существует. Но между «необходимо» и «достаточно» лежит широкая полоса графов, для которых ни один простой признак ответа не даёт.

Задача коммивояжёра: даны n городов и расстояния между каждыми двумя; найти самый короткий маршрут, проходящий через все города по одному разу и возвращающийся в исходный. Вариант с ответом «да» или «нет»: есть ли маршрут длиной не больше B.

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

города       вершины графа
расстояние   1, если вершины соединены ребром;   2, если не соединены
порог B      n

Маршрут через n городов состоит из n переездов, каждый длиной 1 или 2. Его длина равна n тогда и только тогда, когда все переезды имеют длину 1, то есть идут по рёбрам графа, - а это и есть гамильтонов цикл. Если цикла нет, в любом маршруте есть хотя бы один переезд длины 2, и длина не меньше n + 1. Перевод занимает n² действий. Вместо двойки подошло бы любое число больше единицы.

В NP задача лежит: сертификат - сам маршрут, его длину легко сложить. Значит, коммивояжёр с порогом NP-полон. Задача на оптимум - найти сам кратчайший маршрут - не легче: зная кратчайший маршрут, можно ответить на вопрос о любом пороге.

Что известно о точных методах:

полный перебор              (n − 1)!      до 12-13 городов
таблица по подмножествам    2ⁿ · n²       до 20-25 городов
перебор с оценками          в худшем случае (n − 1)!,
                            на практике - сотни и тысячи городов

Последняя строка не противоречит NP-полноте: гарантии нет, но на входах из практики хорошие оценки отсекают почти всё.

Правило

Гамильтонов цикл проходит через каждую вершину ровно один раз; задача о его существовании NP-полна. Она сводится к задаче коммивояжёра: расстояние 1 по рёбрам, 2 между несоединёнными вершинами, порог n. Поэтому коммивояжёр с порогом NP-полон, а поиск кратчайшего маршрута не легче.

Разбор: два графа на десяти вершинах

Перебор с возвратом: начинаем с вершины 0, наращиваем путь по рёбрам в ещё не посещённые вершины; когда в пути все вершины, проверяем, есть ли ребро обратно в начало. Начинать с одной вершины достаточно: цикл через все вершины проходит и через нулевую. Счётчик считает вызовы функции.

Оба графа состоят из двух пятиугольников, внешнего и внутреннего, и пяти спиц между ними. Разница в том, как соединены вершины внутреннего пятиугольника: по кругу или звездой, через одну. Внешние вершины - от 0 до 4, внутренние - от 5 до 9, спица соединяет вершину i с вершиной i + 5.

def prodolzhit(sosedi, put, v_puti, schyot):
    schyot[0] = schyot[0] + 1
    if len(put) == len(sosedi):
        return put[0] in sosedi[put[-1]]
    for u in sosedi[put[-1]]:
        if not v_puti[u]:
            v_puti[u] = True
            put.append(u)
            if prodolzhit(sosedi, put, v_puti, schyot):
                return True
            put.pop()
            v_puti[u] = False
    return False

def cikl(n, ryobra):
    sosedi = []
    for v in range(n):
        sosedi.append([])
    for r in ryobra:
        sosedi[r[0]].append(r[1])
        sosedi[r[1]].append(r[0])
    v_puti = [False] * n
    v_puti[0] = True
    put = [0]
    schyot = [0]
    if prodolzhit(sosedi, put, v_puti, schyot):
        return [put, schyot[0]]
    return ["нет", schyot[0]]

prizma = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0],
          [5, 6], [6, 7], [7, 8], [8, 9], [9, 5]]
zvezda = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0],
          [5, 7], [7, 9], [9, 6], [6, 8], [8, 5]]
spicy = [[0, 5], [1, 6], [2, 7], [3, 8], [4, 9]]
print(cikl(10, prizma + spicy))
print(cikl(10, zvezda + spicy))

[[0, 1, 2, 3, 4, 9, 8, 7, 6, 5], 10]
['нет', 274]

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

Второй граф известен как граф Петерсена. У него те же десять вершин и пятнадцать рёбер, у каждой вершины три соседа, все необходимые условия выполнены - а гамильтонова цикла нет. Перебор сделал 274 вызова и исчерпал все пути из вершины 0. Ответ «нет» здесь - не «не нашёл», а «проверил всё»; но проверить всё удалось только потому, что граф мал. Короткого сертификата отсутствия, который проверялся бы быстрее перебора, в общем случае не известно.

Разбор: тот же вопрос, заданный расстояниями

Функция svesti строит таблицу расстояний по графу, как в сведении (на диагонали остаётся 2: расстояние от города до самого себя программа не использует). Функция luchshij_obhod перебирает все маршруты из города 0 и возвращает длину кратчайшего и число вызовов. Начальный рекорд n * 10 - просто число больше любого маршрута; аргументы idti - где стоим, сколько городов посетили и пройденная длина.

def luchshij_obhod(ves):
    n = len(ves)
    rekord = [n * 10]
    v_puti = [False] * n
    v_puti[0] = True
    schyot = [0]
    idti(ves, 0, 1, 0, v_puti, rekord, schyot)
    return [rekord[0], schyot[0]]

def idti(ves, gde, posetili, dlina, v_puti, rekord, schyot):
    schyot[0] = schyot[0] + 1
    if posetili == len(ves):
        if dlina + ves[gde][0] < rekord[0]:
            rekord[0] = dlina + ves[gde][0]
        return
    for u in range(len(ves)):
        if not v_puti[u]:
            v_puti[u] = True
            idti(ves, u, posetili + 1, dlina + ves[gde][u],
                 v_puti, rekord, schyot)
            v_puti[u] = False

def svesti(n, ryobra):
    ves = []
    for a in range(n):
        ves.append([2] * n)
    for r in ryobra:
        ves[r[0]][r[1]] = 1
        ves[r[1]][r[0]] = 1
    return ves

s_ciklom = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5],
            [5, 6], [6, 0], [0, 3], [2, 5]]
bez_cikla = []
for a in [0, 1, 2]:
    for b in [3, 4, 5, 6]:
        bez_cikla.append([a, b])
print(luchshij_obhod(svesti(7, s_ciklom)))
print(luchshij_obhod(svesti(7, bez_cikla)))

[7, 1957]
[8, 1957]

Первый граф - семиугольник с двумя хордами; гамильтонов цикл в нём есть, и кратчайший обход имеет длину 7, по единице на переезд. Второй граф двудольный: вершины 0, 1, 2 соединены только с вершинами 3, 4, 5, 6. Цикл через все вершины в нём невозможен - он должен чередовать доли, а в долях три и четыре вершины. Кратчайший обход - 8: один переезд пришлось сделать не по ребру.

Оба запуска сделали по 1957 вызовов: 1 + 6 + 30 + 120 + 360 + 720 + 720 - число путей всех длин из города 0. Перебор расстояний не обращает внимания на то, что перед ним: он проходит всё. Для семи городов это ничто, для двадцати адресов и склада - десятки лет, как в начале урока.

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

Гамильтонов цикл путают с эйлеровым. Пройти по каждому ребру один раз - лёгкая задача с простым признаком. Пройти через каждую вершину - NP-полная. Этой паре посвящён урок о лёгком рядом с труднымРазбирается в разделе 21, глава «Каталог NP-полных задач и как им пользоваться»: Лёгкое рядом с трудным: пары задач, которые легко перепутать.

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

Таблицу по подмножествам считают спасением. 2ⁿ · n² при n = 30 - около 10¹² действий и гигабайты памяти; при n = 40 - 10¹⁵. Она отодвигает стену с тринадцати городов до двадцати пяти.

«Маршрут оптимален» принимают без проверки. Проверить, что маршрут проходит все города и имеет данную длину, легко. Проверить, что короче нет, - задача того же порядка трудности, что и поиск.

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

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

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

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

Теперь сам

1. Сколько разных замкнутых маршрутов через 6 городов, если начало закреплено, а направление не важно?
2. В графе есть вершина с одним соседом. Может ли в нём быть гамильтонов цикл?
3. Граф с 12 вершинами сведён к задаче коммивояжёра. Кратчайший обход имеет длину 14. Что это значит?
4. Почему в двудольном графе с долями из 3 и 4 вершин нет гамильтонова цикла?
5. Что служит сертификатом в задаче «есть ли маршрут не длиннее B»?