Пятнашки — это головоломка, которая представляет собой набор из 15 костяшек с числами в квадратной коробке. Костяшки расположены таким образом, что одна ячейка остается пустой:
|
⇒ |
|
Цель игры — упорядочить костяшки по номерам, перемещая их в коробке. Желательно сделать как можно меньше перемещений.
Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Моя программа решает ее с помощью алгоритма A*.
Данный алгоритм является эвристической версией алгоритма поиска в ширину на графе. Вершины для обхода выбираются в соответствии с эвристикой — предполагаемым количеством ходов до цели. В этой программе для оценки расстояния до цели я использовал следюущие эвристики: «Манхэттенское расстояние», «Линейный конфликт», «Последний ход», «Угловые фишки».
Скачать 15-2009-02-14.tar.bz2 (11,3 Кб)
Манхэттенское расстояние — это сумма расстояний по строкам и столбцам от текущего расположения костяшки до ее правильной позиции:
|
⇒ |
|
На этой схеме манхэттенское расстояние равно 4.
Считается, что костяшка I и костяшка J находятся в линейном конфликте по строке, если они обе стоят в своей строке, но костяшка I находится левее костяшки J, хотя на самом деле должна быть справа:
|
⇒ |
|
На этой схеме I = 15, J = 13.
Мы должны подвинуть одну из костяшек со строки, поэтому можем добавить 2 к манхэттенскому расстоянию. Аналогичным образом рассматривается линейный конфликт по столбцу.
Рассмотрим правый верхний угол. Пусть «3» или «8» стоит на своей позиции, а на месте «4» — любая другая костяшка:
|
|
В таком случае, чтобы поставить «4» на место, костяшки придется подвинуть. Для этого добавим 2 к манхэттенскому расстоянию. Если «3» или «8» участвует в линейном конфликте (linear conflict), то двойка уже добавлена.
Аналогично с левым верхним и левым нижним углами. Правый нижний угол в эвристике не рассматривается, так как очень сложно скомбинировать этот случай с эвристикой «Последний ход».
На последнем ходу мы либо двигаем костяшку «15» влево, либо «12» — вверх:
|
⇒ |
|
|
⇒ |
|
Если костяшки не находятся на требуемых позициях («15» — в крайнем правом ряду или «12» — в самой нижней строке), манхэттенское расстояние не учитывает переход через угол. Следовательно, мы можем добавить к нему 2.
Выполните следующие команды:
tar xvf 15-xxxx-xx-xx.tar.gz cd 15-xxxx-xx-xx cmake -DCMAKE_BUILD_TYPE=Release . make
Синтаксис:
./15 [source-state] [target-state]
где параметры source-state и target-state — это текстовые файлы с начальным и конечным состояниями головоломки.
В файлах состояний хранятся числа от 0 до 15:
13 11 15 5 10 8 9 7 1 6 3 2 4 12 14 0
Если оба параметра не заданы, то начальное состояние задается случайным образом, а конечное берется равным собранной головоломке:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
Перед запуском решателя задача проверяется на разрешимость, и если начальное состояние не может быть приведено к конечному, то в начальном состоянии меняются местами два соседних ненулевых числа.
board size = 4, 16 using random data for source and target usage: ./15 [source] [target] source state: 3 7 11 15 2 13 9 4 5 14 6 12 8 10 1 0 target state: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 warning: unsolvable case, fixing source state: source state: 3 7 11 15 2 13 9 4 5 14 6 12 8 1 10 0 target state: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 num_pos=153022 time step 1234619518: =49, closed=152144, open=3, pos/sec=76511.000000 building path ... Result: step=0 3 7 11 15 2 13 9 4 5 14 6 12 8 1 10 0 step=1 3 7 11 15 2 13 9 4 5 14 6 0 8 1 10 12 [...] step=48 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 steps=49 time=1.825000