Передо мной стоит задача поиска оптимального решения для игры пятнашки (если оно существует). То есть имеется разобранная комбинация, и за минимально возможное количество ходов нужно её привести к начальной (т.е. найти последовательность шагов). Если использовать рекурсивный полный перебор, то он очень быстро загнётся. Скажите, существует ли алгоритм решения, и если да, то какой?
1 ответ
Со стороны трудно понять, в чём принципиальная сложность алгоритма.
- Существует 16! = 2 * 1013 исходных позиций, из которых половина неразрешима.
- По моим оценкам, за 4 хода пустая клетка может оказаться на одном из 7 мест, и при этом создаётся в среднем 36 разных позиций. Т.е. за 2n ходов возникает 6n позиций.
- Поскольку 616 = 2,8 * 1013, то весь пасьянс не должен занять более 32 ходов.
- Несложная программка позволит сформировать массив примерно на 60 миллионов позиций (в котором пустая клетка может находиться на одном из 8 мест), из которых можно добраться к финишу ровно за 20 ходов (20 шагов алгоритма Дейкстры), и записать для каждой из них оптимальные траектории пустой клетки.
- Перебором не глубже 12 шагов (примерно 200000 позиций) из произвольной начальной позиции должна достигаться одна из позиций массива.
- Остальное - непринципиальные детали.