Поиск кратчайшего пути для посещения всех незаблокированных квадратов на сетке

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

grid

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

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

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

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

Ответы

Ответ 1

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

Это похоже на проблему Knights Tour, где типичное решение оценивает все возможные маршруты, исходящие из стартового квадрата. Когда тур не может быть завершен, то возврат возвращается для возврата к предыдущим решениям. Ваша проблема более расслаблена, так как вы можете посещать квадраты не один раз. Задачи Knights и Traveling Saleman обычно требуют посещения каждого квадрата ровно один раз.

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