Алгоритмы нахождения числа гамильтоновых путей в графе

Question

Я пытаюсь решить слегка модифицированную версию проблемы Hamiltonian Path .Он изменен тем, что начальная и конечная точки даны нам, и вместо того, чтобы определять, существует ли решение, мы хотим найти число решений (которое может быть 0).

График представлен нам как двумерный массив, узлами которого являются элементы массива.Кроме того, мы можем двигаться только горизонтально или вертикально, а не по диагонали.Излишне говорить, что мы не можем перейти из одного города в два города, потому что для этого нам нужно посетить город дважды.

Я написал решение грубой силы, которое пробует все 4 (3 или 2 для узлов на ребрах) возможных ходов в каждом узле, а затем подсчитывает количество решений (то есть когда оно достигает цели и видит вседругие узлы тоже), но он работал на смешных отрезках времени на входах скромного размера (например, массив 7x7).

Я также подумал об использовании двунаправленного поиска , так как мы знаем цель, но это не очень помогло, так как мы не просто хотим, чтобы окантовки встретились, мы хотим такжечто все узлы были посещены.Более того, может случиться так, что когда все узлы будут исчерпаны между двумя полосами, они заканчиваются таким образом, что их невозможно соединить.

Я чувствую, что есть кое-что, чего я не знаю, что оставляет меня только с помощью грубой силы.Я знаю, что сама проблема является NP-полной, но мне интересно, есть ли какие-либо улучшения по сравнению с грубой силой.Может кто-нибудь предложить что-то еще?

- Правка -

Я упоминал, что использование двунаправленного поиска не очень помогает, и я хотел бы уточнить, почему я так думал.Рассмотрим граф 2x3 с верхним левым и нижним правым узлами, которые являются началом и целью соответственно.Пусть границы двунаправленного поиска перемещаются вправо от начала и влево от цели.После 2 ходов все узлы были бы посещены, но соединить полосы невозможно, так как мы можем идти только в одном направлении от одного узла.Однако, возможно, можно заставить алгоритм работать с некоторыми изменениями, как Дэвид указал в своем ответе ниже.

Answer 1

Согласно Wolfram Alpha ,

... единственный известный способ определения имеет ли данный общий граф Гамильтонов путь должен предпринять исчерпывающий поиск

Я полагаю, что вы хотели бы начать с нахождения одного гамильтонова пути, а затем разделить его на два пути, сделав точку разделения, которая четко разделяет два пути, насколько это возможно. Тогда вы можете найти перестановки в подграфах (и, конечно, повторить!)

Я не знаю точного алгоритма, но я бы начал с такого рода метода «разделяй и властвуй».

Answer 2

Кто-то задал вопрос, очень похожий на ваш в Math Overflow на https://mathoverflow.net/questions/36368/efficient-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-given-pair-of-vert и (1) они не получили потока ответов «вот как это сделать эффективно» (что, вероятно, означает, что нетЭто простой способ), (2) Mathematica, по-видимому, занимает 5 часов, чтобы подсчитать пути между противоположными углами на сетке 7x7, так что вы, возможно, не делаете ничего очень неправильно, и (3) есть несколько интересных указателей среди ответов.

Answer 3

Вы все еще можете использовать двунаправленный поиск, просто добавьте ограничение к поиску, чтобы ранее просмотренные узлы не были кандидатами для поиска.

Еще один подход, который вы могли бы использовать, который мог бы привести к паралеллизуемому решению, -разбить поиск на более мелкие.

Например, попытайтесь решить исходную проблему, решив:

Для каждого узла n, который не является начальным или конечным узлом,найти все пути от начала до n (набор1) и от n до конца (набор2).

После того, как вы найдете set1 и set2, вы можете отбросить все элементы их перекрестного произведениякоторые имеют общий узел, отличный от узла n.

Answer 4

В массиве 7x7 (то есть в общей сложности 7 * 7 = 49 узлов) наличие алгоритма O (n!) Или алгоритма O (2 ^ n * n ^ 2) займет слишком много времени.

Возможно, есть какой-то способ ускорить это, принимая во внимание особые характеристики этого конкретного графа (например, каждый узел имеет не более 4 ребер), но быстрое решение кажется маловероятным (если кто-то случайно не найдет алгоритм за полиномиальное время)для самой проблемы гамильтонова пути).