Введение

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

Проблема гамильтонова пути является темой, обсуждаемой в теории сложности и теории графов. Она определяет, содержит ли ориентированный или неориентированный граф G гамильтонов путь – путь, который посещает каждую вершину графа ровно один раз. В постановке задачи может быть указано начало и конец пути, в этом случае необходимо определить начальную вершину s и конечную вершину t. Проблема гамильтонова цикла аналогична проблеме гамильтонова пути, за исключением того, что она спрашивает, содержит ли данный граф гамильтонов цикл. В этой задаче также может быть указано начало цикла. Проблема гамильтонова цикла является частным случаем задачи коммивояжера, который получается путем установки расстояния между двумя городами равным единице, если они смежны, и двум в противном случае, и проверки того, что общее пройденное расстояние равно n. Если это так, то маршрут является гамильтоновым циклом. Проблема гамильтонова пути и проблема гамильтонова цикла относятся к классу NP-полных задач, как показано в книге Майкла Гэри и Дэвида С. Джонсона «Компьютеры и неразрешимость: руководство по теории NP-полноты» и в списке Ричарда Карпа из 21 NP-полной задачи.

Грубая сила

Чтобы определить, содержит ли граф гамильтонов путь, необходимо проверить каждую возможную последовательность вершин во входном графе G. Существует n! различных последовательностей вершин, которые потенциально могут быть гамильтоновыми путями в графе с n вершинами (и являются таковыми в полном графе), поэтому алгоритм полного перебора, проверяющий все возможные последовательности, будет крайне медленным.

Частичные пути

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

Динамическое программирование

Кроме того, для решения задачи можно использовать алгоритм динамического программирования Беллмана, Хелда и Карпа, работающий за время O(n² * 2ⁿ). В этом методе для каждого множества вершин S и каждой вершины v из S определяется, существует ли путь, проходящий ровно через вершины в S и заканчивающийся в v. Для каждой пары (S, v) путь существует тогда и только тогда, когда у вершины v есть сосед w, для которого существует путь для (S − {v}, w), информацию о котором можно получить из уже вычисленных данных в динамической программе.

Монте-Карло

Андреас Бьёрклунд предложил альтернативный подход, основанный на принципе включения и исключения, для сведения задачи подсчета числа гамильтоновых циклов к более простой задаче подсчета цикловых покрытий, которую можно решить, вычисляя определители матриц. Используя этот метод, он показал, как решить задачу о гамильтоновом цикле в произвольных n-вершинных графах с помощью алгоритма Монте-Карло за время O(1.657n); для двудольных графов этот алгоритм можно дополнительно улучшить до времени O(1.415n).

Отслеживание

Для графов с максимальной степенью три, тщательный поиск с возвратом может найти гамильтонов цикл (если он существует) за время O(1.251n).

Булевая удовлетворительность

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

Необычные методы

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

Проверка полиномиального времени

Проблема гамильтонова пути является NP-полной, что означает, что предложенное решение можно проверить за полиномиальное время. Алгоритм определит, является ли `c` допустимым гамильтоновым путем в графе `G`, и в этом случае примет его. Для этого алгоритм сначала проверяет, что все вершины графа `G` встречаются в пути `c` ровно один раз. Если эта проверка пройдена, то алгоритм убедится, что первая вершина в `c` равна `s`, а последняя вершина равна `t`. Наконец, чтобы убедиться, что `c` является допустимым путем, алгоритм должен проверить, что каждое ребро между вершинами в `c` действительно является ребром в графе `G`. Если хотя бы одна из этих проверок не пройдена, алгоритм отклонит путь. В противном случае он примет его. Алгоритм может проверить за полиномиальное время, встречаются ли вершины графа `G` в пути `c` ровно один раз. Кроме того, проверка начальной и конечной вершин, а также ребер между вершинами также занимает полиномиальное время. Следовательно, алгоритм является верификатором за полиномиальное время для задачи о гамильтоновом пути. Производительность NoC (Network-on-Chip) определяется методом, используемым для передачи пакетов данных по сети. Задача о гамильтоновом пути может быть реализована как метод, основанный на путях, в многоадресной маршрутизации. Алгоритмы многоадресной маршрутизации, основанные на путях, определят, существует ли гамильтонов путь от начального узла к каждому конечному узлу, и отправят пакеты по соответствующему пути. Использование этой стратегии гарантирует маршрутизацию без взаимных блокировок и зависаний, повышая эффективность NoC.

Компьютерная графика

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