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

Question

Допустим, у вас есть такая сетка (сделанная случайным образом):

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

Вы можете двигаться в любом направлении, даже по диагонали.

Два подвопроса:

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

Answer 1

Вы должны смоделировать проблему как полный график, где расстояние между двумя узлами (белые прямоугольники) - это длина кратчайшего пути между этими узлами. Эти длины пути могут быть рассчитаны с помощью алгоритма Floyd-Warshall . Затем вы можете рассматривать его как «Путешествующий продавец» , как писал glowcoder.

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

Answer 2

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

Answer 3

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

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

Answer 4

Кажется, это проблема NP-Complete.

Гамильтонова траектория в сеточном графе является NP-Complete. Здесь показано: Гамильтоновы траектории в сеточных графах .

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

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

Answer 5

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

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

Answer 6

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