Лёгкое рядом с трудным: пары задач, которые легко перепутать

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

Как думаешь, чем длинный путь хуже короткого

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

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

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

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

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

Механизм: что делает лёгкую задачу лёгкой

лёгкая задача / трудная соседка          что есть у лёгкой
кратчайший путь /                        часть кратчайшего пути -
  самый длинный простой путь             кратчайший путь
цикл по всем рёбрам / по всем вершинам   признак по степеням вершин
формулы: 2 литерала в скобке / 3         скобка - следование,
                                         следования - граф
раскраска в 2 цвета / в 3 цвета          цвет соседа определён однозначно
паросочетание: пары / сочетание троек    увеличивающий путь
наименьший разрез / наибольший разрез    равенство с наибольшим потоком
остовное дерево /                        жадный выбор верен
  дерево на части вершин
линейное программирование /              область решений выпукла
  то же с целыми переменными
покрытие в двудольном графе /            равенство с наибольшим
  в произвольном графе                   паросочетанием

Несколько строк таблицы требуют пояснений.

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

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

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

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

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

Правило

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

Разбор: по рёбрам и по вершинам на трёх графах

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

def ejlerov(n, ryobra):
    stepen = [0] * n
    sosedi = []
    for v in range(n):
        sosedi.append([])
    for r in ryobra:
        stepen[r[0]] = stepen[r[0]] + 1
        stepen[r[1]] = stepen[r[1]] + 1
        sosedi[r[0]].append(r[1])
        sosedi[r[1]].append(r[0])
    dejstvij = len(ryobra)
    for v in range(n):
        if stepen[v] % 2 == 1:
            return [False, dejstvij]
    nachalo = 0
    while nachalo < n - 1 and stepen[nachalo] == 0:
        nachalo = nachalo + 1
    videli = [False] * n
    videli[nachalo] = True
    stek = [nachalo]
    while len(stek) > 0:
        v = stek.pop()
        for u in sosedi[v]:
            dejstvij = dejstvij + 1
            if not videli[u]:
                videli[u] = True
                stek.append(u)
    for v in range(n):
        if stepen[v] > 0 and not videli[v]:
            return [False, dejstvij]
    return [True, dejstvij]

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 gamiltonov(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
    schyot = [0]
    return [prodolzhit(sosedi, [0], v_puti, schyot), schyot[0]]

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]]
dvudolnyj = []
for a in range(4):
    for b in range(4, 10):
        dvudolnyj.append([a, b])
kolco = []
for v in range(10):
    kolco.append([v, (v + 1) % 10])
    kolco.append([v, (v + 2) % 10])
for graf in [zvezda + spicy, dvudolnyj, kolco]:
    print(len(graf), ejlerov(10, graf), gamiltonov(10, graf))

15 [False, 15] [False, 274]
24 [True, 72] [False, 3895]
20 [True, 60] [True, 10]

В каждой строке - число рёбер, ответ и работа для цикла по рёбрам, ответ и работа для цикла по вершинам.

Граф Петерсена: у вершин по три ребра, нечётное число, - цикла по рёбрам нет, и это видно после пятнадцати действий. Цикла по вершинам тоже нет, но чтобы убедиться, понадобилось 274 вызова.

Двудольный граф: степени 6 и 4, чётные, граф связен - цикл по рёбрам есть, 72 действия. Цикла по вершинам нет, потому что в долях четыре и шесть вершин, а цикл в двудольном графе чередует доли и берёт из них поровну; но перебор этого рассуждения не знает и делает 3895 вызовов.

Кольцо: оба цикла есть, и оба находятся быстро.

Счётчик левой проверки - не больше утроенного числа рёбер, во всех случаях. Работа правой - от десяти до почти четырёх тысяч на графах одного размера, и по виду графа заранее не скажешь, какой будет.

Разбор: кратчайший путь и все простые пути

Решётка k × k: вершины - клетки, рёбра - между соседними по стороне; клетка в строке r и столбце c имеет номер r · k + c. Нужен путь из угла в противоположный угол. Функция kratchajshij - обход в ширину. Функция vse_puti перебирает все простые пути между углами, считает их и запоминает длину самого длинного.

def sosedi(v, k):
    spisok = []
    if v % k > 0:
        spisok.append(v - 1)
    if v % k < k - 1:
        spisok.append(v + 1)
    if v >= k:
        spisok.append(v - k)
    if v < k * k - k:
        spisok.append(v + k)
    return spisok

def kratchajshij(k):
    rasstoyanie = {}
    rasstoyanie[0] = 0
    ochered = [0]
    i = 0
    while i < len(ochered):
        v = ochered[i]
        i = i + 1
        for u in sosedi(v, k):
            if u not in rasstoyanie:
                rasstoyanie[u] = rasstoyanie[v] + 1
                ochered.append(u)
    return [rasstoyanie[k * k - 1], len(ochered)]

def vse_puti(v, k, v_puti, dlina, itog):
    if v == k * k - 1:
        itog[0] = itog[0] + 1
        if dlina > itog[1]:
            itog[1] = dlina
        return
    for u in sosedi(v, k):
        if not v_puti[u]:
            v_puti[u] = True
            vse_puti(u, k, v_puti, dlina + 1, itog)
            v_puti[u] = False

for k in [2, 3, 4]:
    v_puti = [False] * (k * k)
    v_puti[0] = True
    itog = [0, 0]
    vse_puti(0, k, v_puti, 0, itog)
    print(k, kratchajshij(k), itog)

2 [2, 4] [2, 2]
3 [4, 9] [12, 8]
4 [6, 16] [184, 14]

В каждой строке: размер решётки, длина кратчайшего пути и число посещённых обходом клеток; затем число простых путей между углами и длина самого длинного в шагах. На решётке 4 × 4 это 14, а не 15: при шахматной раскраске углы одного цвета, путь чередует цвета, и пройти все шестнадцать клеток за нечётное число шагов нельзя.

Обход в ширину посещает каждую клетку один раз: 4, 9, 16. Простых путей - 2, 12, 184. На решётке 5 × 5 их 8512, на 6 × 6 - больше миллиона, на 7 × 7 - больше полумиллиарда.

Кратчайший путь можно искать, не глядя на отдельные пути: достаточно знать расстояние до каждой клетки. Самый длинный простой путь так искать нельзя: годится ли клетка в продолжение, зависит от того, какие клетки уже заняты, а это разное для каждого из миллионов путей. Для решётки ответ находится рассуждением, но для произвольного графа полиномиального способа не известно.

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

Обещано по аналогии. «Кратчайший путь мы умеем, значит, и самый длинный сделаем» - обещание, данное не той задаче.

Требование добавлено «чуть-чуть». В назначении каждому заказу нужен один исполнитель - это паросочетание. Добавили «и один станок» - стало сочетание троек, NP-трудная задача.

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

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

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

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

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

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

Теперь сам

1. У каких графов есть цикл, проходящий по каждому ребру ровно один раз?
2. Почему раскраска в два цвета проверяется обходом, а в три - нет?
3. Нужно соединить кабелем 5 зданий из 40 возможных узлов сети, используя остальные узлы как промежуточные. Какая это задача?
4. Наибольшее остовное дерево - лёгкая задача или трудная?
5. Задача о независимом множестве NP-полна. На каком классе графов она решается быстро и чем?