Сайт Алексея Озерицкого

Искусственный интеллект, суперкомпьютерные системы, параллельные вычисления, численные методы, алгоритмы

Пятнашки

  1. Эвристики
  2. Сборка
  3. Использование
  4. Литература
  5. Лицензия

Пятнашки — это головоломка, которая представляет собой набор из 15 костяшек с числами в квадратной коробке. Костяшки расположены таким образом, что одна ячейка остается пустой:

131115 
108912
1632
47145
1234
5678
9101112
131415 

Цель игры — упорядочить костяшки по номерам, перемещая их в коробке. Желательно сделать как можно меньше перемещений.

Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Моя программа решает ее с помощью алгоритма A*.

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

Скачать 15-2009-02-14.tar.bz2 (11,3 Кб)

Эвристики

Манхэттенское расстояние (Manhattan distance)

Манхэттенское расстояние — это сумма расстояний по строкам и столбцам от текущего расположения костяшки до ее правильной позиции:

    
    
   2
    
 2  
    
    
    

На этой схеме манхэттенское расстояние равно 4.

Линейный конфликт (Linear conflict)

Считается, что костяшка I и костяшка J находятся в линейном конфликте по строке, если они обе стоят в своей строке, но костяшка I находится левее костяшки J, хотя на самом деле должна быть справа:

    
    
    
1513  
    
    
    
13 15 

На этой схеме I = 15, J = 13.

Мы должны подвинуть одну из костяшек со строки, поэтому можем добавить 2 к манхэттенскому расстоянию. Аналогичным образом рассматривается линейный конфликт по столбцу.

Угловые фишки (Corner tiles)

Рассмотрим правый верхний угол. Пусть «3» или «8» стоит на своей позиции, а на месте «4» — любая другая костяшка:

  3!4
    
    
    
 
   !4
   8
    
    

В таком случае, чтобы поставить «4» на место, костяшки придется подвинуть. Для этого добавим 2 к манхэттенскому расстоянию. Если «3» или «8» участвует в линейном конфликте (linear conflict), то двойка уже добавлена.

Аналогично с левым верхним и левым нижним углами. Правый нижний угол в эвристике не рассматривается, так как очень сложно скомбинировать этот случай с эвристикой «Последний ход».

Последний ход (Last move)

На последнем ходу мы либо двигаем костяшку «15» влево, либо «12» — вверх:

    
    
    
   15
    
    
    
  15 
    
    
    
   12
    
    
   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

Литература