Нахождение кратчайшего пути, чтобы посетить все неблокированные квадраты на сетке

Похоже, это проблема NP-Complete.

Гамильтонов путь в графе сетки NP-Complete был показан здесь: Пути Гамильтона в Grid Graphs.

Примечание график сетки = подграф полной сетки.

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

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

Ключевым моментом является то, что для формулировки и решения TSP (или любой другой формулировки задачи, если на то пошло), вы ДОЛЖНЫ иметь матрицу расстояний. Матрица расстояний не задана в самом начале, поэтому ее нужно разрабатывать с нуля.

Это похоже на задачу Knights Tour, где типичное решение оценивает все возможные маршруты, исходящие из стартовой клетки. Если тур не может быть завершен, для возврата к предыдущим решениям используется возврат с возвратом. Ваша проблема более расслабленная, так как вы можете посещать площади более одного раза. Задачи «Маршрут рыцарей» и «Путешествующий Салман» обычно требуют посещения каждой площади ровно один раз.

См. http://en.wikipedia.org/wiki/Knight's_tour

Попробуйте построить его как граф (где каждый узел имеет не более 8 других узлов) и относитесь к нему как к http://en.wikipedia.org/wiki/Travelling_salesman_problem

Вы должны смоделировать проблему как полный граф, где расстояние между двумя узлами (белые прямоугольники) - это длина кратчайшего пути между этими узлами. Эти длины пути могут быть вычислены с помощью алгоритма Флойда-Уоршалла . Тогда вы можете рассматривать его как «Коммивояжер» , как писал световой кодер.

РЕДАКТИРОВАТЬ: чтобы было понятнее: вы можете описать каждый "интересный" путь через лабиринт последовательностью различных белых квадратов. Потому что, если у вас есть произвольный путь, посещающий каждое белое поле, вы можете разделить его на подпути, каждый из которых заканчивается новым белым ящиком, который до сих пор не посещался. Каждый из этих подпутей от белого ящика A до B может быть заменен кратчайшим подпутьем от A до B, поэтому вам нужна матрица кратчайших путей между всеми парами узлов.

Хотя эвристика, основанная на TSP, является разумным подходом, неясно, как она дает оптимальный ответ. Проблема (как указывает Морон) - это проблема остовного следа, и в ссылке, приведенной в комментарии, есть много частных случаев, для которых существуют оптимальные по линейному времени решения. Одна уловка, которая отличает проблему OP от формулировки сеточного графа, использованной в цитируемой статье, - это возможность перемещаться по диагонали, что немного меняет игру.