Русская Википедия:Задача о гамильтоновом пути

Материал из Онлайн справочника
Версия от 18:52, 17 августа 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} '''Задача о гамильтоновом пути''' и '''задача о гамильтоновом цикле''' — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (Ориентиров...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи 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.

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Задача_о_гамильтоновом_пути&oldid=9894398