Теория графов
2026-02-26 18:46 Diff
https://ru.hexlet.io/courses/graphs/lessons/np/theory_unit

В этом уроке рассмотрим задачи о командировке и времени выполнения алгоритмов, чтобы посмотреть, как работать с гамильтоновыми циклами и NP-полнотой.

Задача с маршрутом командировки

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

В графовой задаче города — это вершины, ребро между вершинами указывает на возможность прямого проезда между двумя городами, а веса на ребрах — стоимость поездки между двумя соответствующими городами.

Нам нужно найти гамильтонов цикл с минимальным весом. Например, ниже показан граф с выделенным оптимальным решением:

Если проверять все возможные маршруты, то это только усложнит решение задачи. Если каждый город соединен с другим, то существует n! возможных маршрутов.

Можно упростить решение с помощью динамического программирования. Это позволит сократить количество проверяемых маршрутов до (n^2)(2^n), что является значительным улучшением, но все равно является экспоненциальным.

На примере этой задачи мы видим, как математики находят такие алгоритмы, которые работают даже на больших масштабах — например, для карт, состоящих из многих тысяч городов.

Задача с временем выполнения

До сих пор мы рассмотрели несколько алгоритмов работы с графами. Один из самых важных аспектов — скорость их работы. Например, есть алгоритмы, время выполнения которых меняется, если мы меняем количество вершин или ребер в графе. На это указывает NP-полнота — класс сложности. Пока мы не будем углубляться в эту сложную тему, но измерим время работы алгоритмов.

Предположим, у нас есть следующий код на языке Python, который суммирует все значения в списке:

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

Получается, время работы этого алгоритма на конкретном компьютере может составлять 2,3n + 0.2 микросекунды. Константы 2,3 и 0.2 будут варьироваться от компьютера к компьютеру. Нас интересует n. Обычно это записывается как O(n), что читается как «большое O из n». Это говорит нам о порядке роста времени выполнения.

Так как порядок роста равен O(n) — это линейный алгоритм. Получается, если мы удвоим количество элементов в списке, время работы увеличится примерно вдвое. Если мы утроим количество элементов, время работы увеличится примерно втрое.

В качестве другого примера предположим, что мы хотим сложить элементы в матрице n * n. В этом случае время работы может составить 3,4n^2 + 0.2. Мы бы записали это как O(n^2). Это говорит, что время работы растет как квадрат n. Это квадратичный алгоритм:

  • Если мы удвоим количество записей, то время работы увеличится примерно в четыре раза
  • Если мы утроим количество записей, то время работы увеличится примерно в девять раз

Оба примера показывают полиномиальный рост. Это значит, что у алгоритма есть входные данные, у которых есть размер. Например, у алгоритма сортировки массива размером считается количество элементов в массиве. Если для любого входа количество операций при выполнении алгоритма не больше какого-то полинома от размера входа, то это полиномиальный алгоритм.

Любой алгоритм, время работы которого является полиномом, называется алгоритмом полиномиального времени. Для обозначения совокупности всех алгоритмов, выполняющихся за полиномиальное время, используется заглавная буква P.

Не все алгоритмы выполняются за полиномиальное время. Например, если перечислить все подмножества из {1, 2, . . . , n}, это был бы алгоритм O(2^n), поскольку существует 2^n подмножеств. Это пример экспоненциального алгоритма. Здесь простое добавление еще одного элемента к множеству удваивает время работы.

Алгоритмы с полиномиальным временем обычно предпочтительнее алгоритмов с экспоненциальным временем. Чтобы понять почему, рассмотрим огромную разницу в росте между n^2 и 2^n:

10^2 = 100 2^10 = 1024

100^2 = 10000 2^100 = 1.27 * 10^30

1000^2 = 1000000 2^1000 = 1.07 * 10^301

Предположим, что нам нужно выбрать один из двух алгоритмов, чтобы поработать с двумя графами:

  • Первый граф O(n^2)
  • Второй граф O(2^n)

На графе с 1000 вершинами у алгоритма O(n^2) будет время работы примерно 1 000 000 единиц времени. Если эти единицы времени — микросекунды, то на выполнение алгоритма уйдет около секунды. С другой стороны, алгоритм O(2^n) занимает 1,07 * 10^301 единицу времени, что намного больше, чем возраст Вселенной — это число с 301 нулем. С практической точки зрения, экспоненциальный алгоритм непригоден для использования.

Экспоненциальные алгоритмы иногда могут превосходить полиномиальные, если число вершин относительно невелико. Здесь мы опустим детали. Когда число вершин становится достаточно большим, экспоненциальные алгоритмы оказываются намного хуже полиномиальных.

NP-полные проблемы

Существует еще одна группа задач с NP-полнотой, где требуется полиномиальное количество времени:

Все, что находится в P, также находится в NP, но NP содержит некоторые другие проблемы, которых нет в P

Наглядный пример такой задачи — судоку. Если у нас есть решение судоку, несложно проверить, что оно работает. Для этого нужно просмотреть каждую строку, столбец и блок — и убедиться, что нет повторений. При этом решение судоку гораздо сложнее. Никто не знает полиномиального алгоритма, который бы находил решения для n * n судоку.

Разберем еще один похожий пример: проблему суммы подмножеств. Нам нужно понять, можно ли найти подмножество набора целых чисел, сумма элементов которого равна 0.

Например, задано такое множество {-20,-12,-10,-7,-3, 4, 5, 9, 18, 25}. Чтобы найти подмножество, сумма элементов которого равна 0, потребуется некоторое время. При этом можно проверить, что {-12,-10, 4, 18} работает — на это требуется очень мало времени.

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

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

Проблема P=NP

В математике существует одна из самых важных проблем — проблемой P=NP. То есть никто не знает, равны ли между собой P и NP. Если мы можем проверить правильность решения, значит ли это, что мы можем решить такую проблему? Не совсем. За решение этой проблемы полагается приз в миллион долларов. Большинство математиков и компьютерных ученых считают, что P не равна NP, но не все с этим согласны. Правда пока никто не приблизился к решению проблемы.

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

Если проблема эйлеровой цепи находится в P, значит, существует полиномиальный алгоритм, который определяет, имеет ли граф эйлерову цепь или нет. Перебор и проверка степеней каждой вершины, чтобы узнать, все ли они четные, — это полиномиальный алгоритм. Алгоритм Гирхольцера и алгоритм Флери для нахождения таких схем также являются полиномиальными алгоритмами.

Проблема гамильтонова цикла является NP-полной, так как если кто-то дает нам гамильтонов цикл в графе, то легко проверить, что это действительно гамильтонов цикл. Однако люди доказали, что полиномиальное решение проблемы гамильтонова цикла даст полиномиальное решение любой другой проблемы в NP.

Получается, проблема гамильтонова цикла — NP-полная. Никто не нашел решения проблемы гамильтонова цикла за полиномиальное время, и очень вероятно, что никто и никогда не найдет.

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

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

Еще пример: поиск максимальных независимых множеств является NP-полной проблемой, но если мы просто хотим найти максимальные независимые множества на деревьях, то это является управляемой полиномиально-временной проблемой.

Выводы

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