На одном из моих университетских курсов (в области структур данных и алгоритмов) нам дается бонусное задание на основе игры Сокобан:
С одним главным исключением: у нас есть только один ящик, чтобы подтолкнуть к нашей цели.
Пример ввода
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 порядка ...
Поэтому я спрашиваю здесь: что делает этот алгоритм таким медленным и как я могу ускорить его?