Гамильтонов цикл

Гамильтонов цикл

Гамильтонов цикл в графе — это такой маршрут обхода вершин графа, при котором посещается по одному разу каждая его вершина, а под гамильтоновым путём понимается незамкнутый путь, но который тоже проходит через каждую вершину графа. Построить гамильтонов цикл представляется необычайно сложной проблемой, и на сегодняшний день не существует оптимального алгоритма для разрешения этой задачи. Можно предположить, что алгоритма, который способен решить эту задачу, вероятнее всего нет. То есть это одна из задач теории сложности алгоритмов, не имеющих на сегодня решения. Возможно сформировать решение, основанное на переборе вариантов, но его сложность будет примерно равна O(n!). К примеру, если выполнить нумерацию всех вершин графа, то нумерация вершин в их последовательности в цикле Гамильтона, выполнит некую перетасовку чисел от единицы до n. Возможно выполнить перебор всех допустимых n! вариантов и для каждого из них сделать проверку соответствия искомому циклу на графе. То есть проверку, что каждая пара соседних вершин в текущем варианте, а также начальная и конечная вершина соединяются ребром. Для такой переборки вариантов возможно применить, например, известный алгоритм перебора с возвратом. Можно переписать данный алгоритм таким образом, чтобы отсекались явно неверные варианты, то есть к уже выстроенному отрезку маршрута будут прибавляться лишь те вершины, которые соединяются ребром с конечной вершиной маршрута и не посещались раньше. После прибавления новой вершины к путевому маршруту, следует сделать рекурсию, то есть запуск алгоритма из новой вершины. По многим параметрам такой алгоритм похож на поиск в глубину, но он имеет и существенное отличие. Оно состоит в том, что в случае возврата пути из какой-либо вершины на предыдущую точку, с оставленной вершины удаляется пометка о её посещении. При таком способе возможен возврат алгоритма на эту же вершину повторно, но уже другим путём. Более того, это обязательно должно произойти, в случае существования гамильтонова пути в этом графе, поскольку гамильтонов должен пройти через каждую вершину.

Рассмотрим пример. Будем считать, что n является числом вершин в графе и все вершины имеют нумерацию от нуля до n−1, а сам граф определяется с помощью матрицы смежности A. Глобальная переменная Path содержит перечень вершин, которые вошли в путевой маршрут. В функцию hamilton заносятся в виде параметров номера вершин, которые прибавляются к маршруту, и она же возвращает признак true, если построение гамильтонова пути оказалось удачным, в противном случае возвращается значение false. При этом в случае удачного построения пути, он сохранится в переменной Path.

Реализация алгоритма на языке С++

Рисунок 1. Реализация алгоритма на языке С++. Автор24 — интернет-биржа студенческих работ

Реализация алгоритма на языке PYTHON

Рисунок 2. Реализация алгоритма на языке PYTHON. Автор24 — интернет-биржа студенческих работ

Функция Hamilton сначала заносит вершину curr последней в список Path. Причём, если размер списка стал равен n, что означает включение всех вершин в состав пути Path, то выполняется проверка соединения ребром первой и последней вершины (только при поиске гамильтонова цикла, для пути это не требуется) и если такое ребро есть, то возвращается значение True (цикл обнаружен). Если же такого ребра нет, то выполняется удаление из Path последней вершины и возврат значения возвращает False (цикл не обнаружен). В случае, когда размер списка менее n, делается отметка, что вершина curr посещалась, и процесс перебора продолжается далее. Поочерёдно выполняется обход всех оставшихся вершин next и в случае соединения ребром вершины next с вершиной curr, если при этом вершина next ещё не посещалась, то делается рекурсивный запуск алгоритма из вершины next с целью найти путь в эту вершину. И если рекурсия из вершины next закончится возвратом True, то есть удачным построением цикла, то алгоритм так же делает возврат True. В этом случае из переменной Path нет никаких удалений, и в списке Path находится весь гамильтонов цикл. Если не выбран ни один из выше указанных вариантов, то выполняется возврат вершины curr, то есть делается пометка, что она не посещалась, её удаляют из окончания списка Path и алгоритм возвращается к обработке последней вершины в списке Path. Следует отметить, что алгоритмическая сложность этого метода будет не меньше, чем n!, и это означает непригодность данного алгоритма для графов большого объёма.

Задача работы коммивояжёра

Задачей, аналогичной и близкой по смыслу процедуре определения гамильтонова цикла, считается задача работы коммивояжёра. Условие задачи следующее. Странствующий торговец, именуемый коммивояжёром, должен объехать n городов и возвратиться к дому. Коммивояжёр не намерен приезжать в каждый город более чем один раз и желает, чтобы маршрут его перемещений был оптимальным, то есть самым коротким из возможных. Это означает поиск внутри неориентированного взвешенного графа маршрута (пути), который обладает наименьшим весом (стоимостью). Проблему коммивояжёра возможно решить по аналогии с задачей гамильтонова цикла (пути), но в этом случае необходимо сделать перебор всех возможных маршрутов. При зацикливании пути необходимо определить его суммарный вес и выполнить сравнение найденного маршрута с весом предыдущего самого лучшего известного маршрута. Оптимально эту операцию выполнять не при окончании замыкания, а единовременно с прибавлением очередной вершины прибавлять вес рассматриваемого ребра, как выстроенного компонента маршрута.