Стратегии Сокращения для вычисления общего количества гамильтоновых путей в двумерной сетке

Question

Недавно я пытался найти общее количество гамильтоновых путей (в основном, начиная с начальной вершины, посещение каждого узла точно один раз и достижение конечной вершины). Грубая сила dfs идет на длинную прогулку по сетке среднего размера 7x8. Я придумал некоторые из этих стратегий сокращения. Цель этих методов сокращения состоит в том, что частичный путь, который не может быть гамильтоновым путем, не должен быть продолжен дальше.

Алгоритм DFS: начать для начальной вершины, посетить ее соседние узлы и выполнить рекурсию. Ведите подсчет количества посещенных узлов и, достигнув конечной вершины, проверьте, совпадает ли общее количество посещенных узлов с общим количеством узлов в сетке. Это будет экспоненциальная сложность, так как для каждой вершины вы можете идти в 4 направлениях, которые будут иметь O(4^n). Поэтому следует сосредоточиться на том, чтобы отклонить путь как можно скорее и не ждать, пока не достигнет конечной вершины.

Методы обрезки:

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

2) Для данного частичного пути каждый узел, который еще предстоит посетить, должен иметь как минимум 2 градуса, чтобы один соседний узел мог использоваться для входа в этот узел, а другой другой сосед - для выхода.

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

Заранее спасибо!!!

Answer 1

Существует решение O(n^2 * 2^n), которое работает для общих графов. Структура идентична алгоритму O(2^n * n^2), описанному здесь,

http://www.algorithmist.com/index.php/Traveling_Salesperson_Problem

За исключением записи минимальных расстояний, вы записываете счет.

Любая обрезка, которую вы можете сделать поверх этого, все равно поможет.