Русская Википедия:Задача о гамильтоновом пути
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полныШаблон:Sfn.
Связь задач о гамильтоновом пути и гамильтоновом цикле
Существует простое отношение между задачами нахождения гамильтонова пути и нахождения гамильтонова цикла. В одном направлении задача о гамильтоновом пути для графа эквивалентна задаче о гамильтоновом цикле в графе H, полученного из графа G путём добавления новой вершины и соединения её со всеми вершинами графа G. Таким образом, поиск гамильтонова пути не может быть существенно медленнее (в худшем случае, как функция числа вершин), чем поиск гамильтонова цикла.
В обратном направлении задача о гамильтоновом цикле для графа G эквивалентна задаче о гамильтоновом пути в графе H, полученном копированием одной вершины v графа G (в v'), то есть вершина v' будет иметь ту же окрестность, что и v, и добавлением двух вспомогательных вершин степени один, одна из которых соединена с v, а другая с v'[1].
Задача о гамильтоновом цикле является также частным случаем задачи коммивояжёра, полученной установкой всех расстояний между двумя пунктами в единицу, если они смежны, и двум в противном случае. После решения задачи коммивояжёра следует проверить, что полное расстояние равно n (если так, маршрут является гамильтоновым циклом, если же гамильтонова цикла нет, кратчайший путь будет длиннее этой величины).
Алгоритмы
Есть n! различных последовательностей вершин, которые могут быть гамильтоновыми путями в заданном графе с n вершинами (и их столько в полном графе), так что алгоритм полного перебора, который перебирает все возможные последовательности, был бы очень медленным.
Ранний точный алгоритм нахождения гамильтонова цикла в ориентированном графе был алгоритмом перебора (алгоритм Мартелло)Шаблон:Sfn.
Процедура поиска Франка РубинаШаблон:Sfn разбивает рёбра графа на три класса — те, которые должны быть на пути, те, которые пути принадлежать не могут, и рёбра, для которых решение не принято. В процессе поиска набор правил принятия решений классифицирует рёбра, для которых решение не принято, и определяет, остановиться или продолжить поиск. Алгоритм разбивает граф на компоненты, которые могут быть обработаны отдельно.
Для решения задачи за время <math>O(n^2 2^n)</math> может быть использован алгоритм динамического программирования Беллмана, Хелда и Карпа. В этом методе определяется для каждого набора S вершин и каждой вершины v из S, существует ли путь, проходящий через все вершины S и заканчивающийся в v. Для каждой пары (S,v) путь существует тогда и только тогда, когда v имеет соседнюю вершину w такую, что существует путь для <math>(S \setminus v,w)</math>, который можно получить из уже полученной информации динамического программированияШаблон:SfnШаблон:Sfn.
Андреас Бьёрклунд даёт альтернативный подход, использующий принцип включения/исключения для сокращения числа перебираемых гамильтоновых циклов и задача подсчёта циклов может быть решена путём вычисления определителя некоторой матрицы.
Используя этот метод, он показал, как решить задачу о гамильтоновом цикле для произвольных графов с n вершинами с помощью алгоритма Монте-Карло за время <math>O(1{,}657^n)</math>. Для двудольных графов этот алгоритм можно улучшить до времени <math>o(1{,}415^n)</math>Шаблон:Sfn.
Для графов с максимальной степенью три аккуратный поиск с возвратом может найти гамильтонов цикл (если таковой существует) за время <math>O(1{,}251^n)</math>Шаблон:Sfn.
Гамильтоновы пути и циклы можно найти с помощью SAT решателя.
Ввиду сложности решения задач о гамильтоновом пути и цикле на обычных компьютерах, они изучались для нестандартных моделей вычислений. Например, Леонард Адлеман показал, что задачи о гамильтоновом пути могут быть решены с помощью ДНК-компьютера. Используя параллелелизм, свойственный химическим реакциям, задача может быть решена с помощью нескольких шагов химических реакций, линейно зависящих от числа вершин графа. Однако это требует факториальное число молекул ДНК, участвующих в реакцииШаблон:Sfn.
Оптическое решение гамильтоновой задачи предложил ОльтеанШаблон:Sfn. Идея заключается в создании подобной графу структуры из оптических кабелей и расщепителей луча, через которую прогоняется луч в порядке решения задачи. Слабым моментом этого подхода является экспоненциальный рост требуемой энергии от числа узлов.
Сложность
Задача нахождения гамильтонова цикла или пути имеет сложность Шаблон:Не переведено 5. Аналогичная задача разрешимости — проверить, существует ли гамильтонов цикл или путь. Ориентированные и неориентированные задачи о гамильтоновом цикле являлись двумя из 21 NP-полных задач Карпа. Они остаются NP-полными даже для неориентированных планарных графов максимальной степени триШаблон:Sfn, для ориентированных планарных графов с полустепенью входа и выхода, не превосходящими двухШаблон:Sfn, для неориентированных планарных 3-регулярных двудольных графов без мостов, для 3-связных 3-регулярных двудольных графовШаблон:Sfn, подграфов квадратной решёткиШаблон:Sfn и для кубических подграфов квадратной решёткиШаблон:Sfn.
Однако 4-связные планарные графы всегда гамильтоновы, согласно результату Татта, а задача нахождения гамильтонова цикла в этих графах может быть выполнена за линейное времяШаблон:Sfn путём вычисления так называемого пути Татта. Татт доказал этот результат, показав, что любой 2-связный планарный граф содержит путь Татта. Пути Татта, в свою очередь, можно вычислить за квадратичное время даже для 2-связных планарных графовШаблон:Sfn, что может быть использовано для поиска гамильтоновых циклов и длинных циклов в обобщённых планарных графах.
Складывая всё вместе, остаётся открытой задача, всегда ли 3-связные 3-регулярные двудольные планарные графы должны содержать гамильтонов цикл и если должны, задача, ограниченная этими графами, не будет NP-полной (см. статью «Гипотеза Барнетта»).
В графах в которых все вершины имеют нечётную степень, довод, связанный с леммой о рукопожатиях, показывает, что число гамильтоновых циклов через фиксированное ребро всегда чётно, так что если дан один гамильтонов цикл, то и другой должен существоватьШаблон:Sfn. Однако поиск этого второго цикла не выглядит как простая вычислительная задача. Пападимитриу определил класс сложности Шаблон:Не переведено 5, чтобы собрать вместе задачи, подобные этойШаблон:Sfn.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
