Возможно, есть некоторый способ ускорить это, принимая во внимание особые характеристики этого конкретного графа (например, каждый узел имеет не более 4 ребер), но быстрое решение кажется маловероятным (если кто-то случайно не найдет алгоритм за полиномиальное время для самой задачи о гамильтоновом пути). ).
аюсь решить слегка измененную версиюГамильтонов путь проблема. Он изменен тем, что нам даны начальная и конечная точки, и вместо того, чтобы определить, существует ли решение, мы хотим найтиномер решений (которые могут быть 0).
График представлен нам как двумерный массив, узлами которого являются элементы массива. Кроме того, мы можем двигаться только горизонтально или вертикально, а не по диагонали. Излишне говорить, что мы не можем перейти из одного города в два города, потому что для этого нам нужно посетить город дважды.
Я написал решение грубой силы, которое пробует все 4 (3 или 2 для узлов на краях) возможных ходов в каждом узле, а затем подсчитывает количество решений (то есть, когда оно достигает цели и также видит все другие узлы), но он работал на смешных отрезках времени на входах скромного размера (как, скажем, массив 7x7).
Я тоже думал об использованиидвунаправленный поиск поскольку мы знаем цель, но это на самом деле не помогло, так как мы не просто хотим, чтобы границы встретились, мы также хотим убедиться, что все узлы были посещены. Более того, может случиться так, что когда все узлы будут исчерпаны между двумя полосами, они заканчиваются таким образом, что их невозможно соединить.
Я чувствую, что есть кое-что, чего я не знаю, и это оставляет мне решение только грубой силы. Я знаю, что сама проблема является NP-полной, но мне интересно, есть ли какие-либо улучшения по сравнению с грубой силой. Может кто-то предложить что-то еще?
--Редактировать--
Я упомянул, что использование двунаправленного поиска не очень помогает, и я хотел бы уточнить, почему я так думал. Рассмотрим граф 2x3 с верхним левым и нижним правым узлами, которые являются началом и целью соответственно. Пусть границы двунаправленного поиска перемещаются вправо от начала и влево от цели. После 2 ходов все узлы были бы посещены, но соединить полосы невозможно, так как мы можем идти только в одном направлении от одного узла. Однако, возможно, можно заставить алгоритм работать с некоторыми изменениями, как Дэвид указал в своем ответе ниже.