Нерегулярная сетка и гамильтоновы пути

Question

У меня есть вопрос.Есть ли эффективный способ получить гамильтоновы пути между двумя узлами в сеточном графе, оставив некоторые предопределенные узлы?

например.(Сетка 4 * 3)

1 0 0 0
0 0 0 0
0 0 2 3

нахождение гамильтоновых путей в этой сетке ч / б вершин 1 и 2, но не покрывающих 3?Кажется, двудольные графы - это способ, но то, что, по вашему мнению, должно быть наиболее эффективным способом.Сама проблема - NP завершена.

Answer 1

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

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

Answer 2

Удалите узлы, которые вам не нужно включать, и запустите алгоритм грубой силы, чтобы найти гамильтонову траекторию. Для этого потребуется O ((n-h)! + N), то есть NP, где h - количество удаленных узлов, но это лучшее, что вы можете сделать. Также, чтобы найти гамильтонов путь, существует динамический подход, но он тоже экспоненциальный (O (2 ^ n * n ^ 2))