Как реализовать быстрый поиск кратчайшего пути для сокобана из 1 ящика?

Question

На одном из моих университетских курсов (в области структур данных и алгоритмов) нам дается бонусное задание на основе игры Сокобан:

С одним главным исключением: у нас есть только один ящик, чтобы подтолкнуть к нашей цели.

Пример ввода

8 8
MMMMMMMM
M.....?M
M....TTM
M....TTM
M..!...M
M....+.M
M......M
MMMMMMMM

Здесь в первой строке указаны размеры (b x h) доски (в данном случае 8 на 8). Далее следуют h строк или b символов. Значение этих символов таково: . место для ходьбы, ? цель (красная точка в gif), ! ящик и + - наша позиция.

Нас просят вывести кратчайшее решение головоломки. (Обратите внимание, что головоломка может быть неразрешимой.) Мы выводим это в 2 строки, первая говорит нам, сколько ходов, а вторая говорит нам правильный путь. Например, это будет:

Пример вывода

10
WWNNNWNEEE

Теперь, поиск алгоритма, который работает, на самом деле не проблема. Поскольку мы ищем кратчайший путь, а узлы на этом конкретном графике по существу не взвешены, я реализовал поиск в ширину. В общих чертах моя текущая реализация выглядит так:

0. Since the maze doesn't change, describe each state as a whole number based on the coordinates 
     of the crate and the player. - This defines a state uniquely and reduces memory costs.
1. Create a dictionary of visited states.
2. Get the input positions of the goal, crate and player.
3. Set up a Queue of move sequences.
4. Pop a move sequence from the Queue.
5. If this move sequence wins the game, go to step 8.
6. Make new move sequences which are copies of the original, each with a different legal move appended.
7. Append these new move sequences to the Queue.
8. Go to step 4
9. Print the output.

Это, конечно, относительно простой алгоритм. Проблема в том, что это недостаточно быстро. В одном из финальных тестовых примеров мы бросаем 196 x 22 лабиринт, подобный «уровню», в котором есть решение, которое занимает 2300 шагов. Нас просят решить этот уровень в течение 10 секунд, но мой алгоритм занимает больше 10 минут.

Из-за этого я немного растерялся. Мне уже удалось увеличить скорость алгоритма в 10 раз, и мне осталось пройти 2 порядка ...

Поэтому я спрашиваю здесь: что делает этот алгоритм таким медленным и как я могу ускорить его?

Answer 1

Да, ваш полный поиск в BFS будет медленным .Вы проводите большую часть поиска по дереву в совершенно бесполезных ходах, ваш игрок безрезультатно бегает по области лабиринта.

Измените фокус своей цели: во-первых, найдите лабиринт для ящик вместо отправки игрока в разные стороны.Включите эвристику для перемещения ящика ближе к цели.Убедитесь, что ходы в ящике возможны: для каждого хода есть место «отталкивания».

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

MMMMMMMM
M54321?M
M6543TTM
M7654TTM    
M876567M   <== crate is on the farther 6
M987678M   <== player is on the nearer 7
Ma98789M
MMMMMMMM

Здесь вы сначала попытаетесь найти законные толчки, чтобы переместить коробку вдольпуть 654321 ?.Вы также можете обновить это, сделав штраф (перемещая игрока без толчка) за любое изменение направления.

Эта эвристика даст вам очень хорошую верхнюю границу для решения;затем вы можете отследить точки принятия решения, чтобы попробовать другие пути, всегда сохраняя свое «самое короткое решение» для любой позиции.

Также отслеживайте, где вы были, чтобы не тратить время на петли позиции: никогда повторять движение (положение и направление).

Помогает ли это вам начать движение?

Answer 2

Вместо того, чтобы использовать чистый поиск ДФС движений игрока, рассмотрите только те ходы ящика , которые доступны вам в данный момент. Например, в самом первом кадре вашего gif, в начале симуляции, единственное возможное движение ящика - это верхний правый квадрат.

Аналогия была бы для игры в шахматы на первом ходу, вы не рассматривали бы ходы ферзя или слона, так как все они заблокированы пешками.

После того, как вы успешно нашли последовательность ходов ящиков, ведущую к решению, вернитесь и проследите ходы игрока, необходимые для построения последовательности ходов ящиков.

Это улучшает временную сложность, потому что временная сложность будет зависеть от количества ящиков, присутствующих на карте, а не от общих квадратов.