расстояние = abs(X

кубик

- X. ) + abs(Y

куби

- Y. , .)

Вычисление эвристики производится по описанной выше схеме. Пустая клетка помечается нулём ( нулевой кубик ):

void Vertex:tRecalculateHeuristics() {

строка и столбец каждого кубика (О, 1, 2, 15)

int RowOf[] = { 3, О, О, О, О, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3 };

int ColOf[] = { 3, О, 1, 2, 3, О, 1, 2, 3, О, 1, 2, 3, О, 1, 2 };

int г = 0;

for(int i = 0; i < 4; i++)

for(int j = 0; j < 4; j++)

для нулевого кубика расстояние не вычисляется .if (State[i] [j] != 0)

г += abs(RowOf[State[i][j]] - i) + abs(ColOf[State[i][j]] - j);

Heuristics = r;

Функция Print () служит для печати состояния игры на очередном шаге:

void Vertex::Print() {

for(int i = 0; i < 4; i++)

может оказаться неприемлемой. Нередко скорость работы алгоритма поиска пути критична сама по себе, например при расчёте маршрутов юнитов в стратегиях реального времени.

Решение

Рассмотрим идею А*-поиска на уровне псевдокода. Предположим, что в голове очереди с приоритетами Q всегда находится элемент с минимальной суммой цены и эвристики:

добавить стартовое состо5Шие в очередь Q ПОКА очередь Q не пуста

V =:головной элемент очереди Q .извлечь.головной элемент из Q

. ЕСЛИ V является целевым состоянием - вывести решение на экран

добавить В Q ёершины-потомки V КОНЕЦ ЦИКЛА

Повторюсь, хотя в общем случае процедура А* не обязывает программиста хранить все просмотренные вершины, для игры в 15 это требуется, чтобы восстановить полный ход решения. Кроме того, список просмотренных вер-1пин поможет исключить повторную обработку проанализированных ранее ситуаций.

Чтобы определить ход решения, придётся гфиписать каждой рассматриваемой вершине указатель на вершину-родитель (то есть вершину, из которой мы перешли в текущую). Указатель, приписанный стартовой вершине, равен NULL. Если V - финишная вершина, то ход решения (от финишной вершины к стартовой) определяется с помощью несложного алгоритма:

. ПОКА V;0 NULL напечатать V

V = вершина--родитель V КОНЕЦ ЦИКЛА

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

Например, если кубик, помеченный единицей (Х О, Y - 0), находится в ячейке (1,2) коробки, расстояние для него равно abs(l - 0) + abs(2 - 0) = 3. Для игры в 15 манхэттенское расстояние всегда будет оптимистичной оценкой. Действительно, переместить кубик, помеченный единицей, в верхний левый угол коробки не удастся быстрее, чем за три хода.

Сумма расстояний, вычисленных для каждого из кубиков, и будет составлять эвристику вершины.

Рассмотрим теперь полное решение задачи. Для начала нам понадобится новый тип данных вершина :

struct Vertex {

int State[4][4]; конфигурация кубиков

Vertex *Ancestor; указатель на вершину-родитель

int Cost, Heuristics; цена и эвристика

вычислить эвристику на основе данных State void RecalculateHeuristics();

вывести на экран содержимое вершины void Print();

вывести очередную строку

сору(&State[i][0], &State[i][3] + 1,

ostream iterator<int>(cout, * ));

cout endl;

Глава 4. Рекурсия и перебор с возвратами. Эвристический поиск

cout << endl;

Теперь можно определить очередь с приоритетами Queue и множество всех известных вершин Vertices:

вспомогательная функция для сортировки элементов очереди

struct PQSorter

bool operator О(Vertex *lhs, Vertex *rhs)

{ return lhs->Cost + lhs->Heuristics > rhs->Cdst + rhs->Heuristics; }

функция для сравнения содержимого двух вершин, адресуемых указателями

struct CompareVPtrs : public binary function<Vertex*, Vertex*, bool> {

bool operatorO(Vertex *lhs. Vertex *rhs) {

сравнить содержимое массивов lhs->State и rhs-State return equal((int *)lhs->State, (int *)lhs->State + 16,

(int *)rhs->State);

CompareVP;

priority queue<yertex*, deque<Vertex*>, PQSorter> Queue; set<Vertex*> Vertices;

Функция Initialize о считывает с клавиатуры начальную конфигурацию головоломки и создаёт стартовую вершину, с которой начинается поиск решения:

void Initialize О {

Vertex* StartingState = new Vertex; string line;

считать с клавиатуры четыре строки

for(int i = 0; i < 4; i++)

getline(cin, line);

istringstream is(line);

каждая строка содержит четыре числа

for(int j = 0; j < 4; j++)

is StartingState->State[i][jJ;

цена стартовой вершины равна нулю StartingState->Cost = 0; StartingState->RecalculateHeuristics();

вершины-родителя не существует StartingState->Ancestor = NULL;

добавить вершину в очередь с приоритетами Queue.push(StartingState);

У/ и в список известных вершин Vertices.insert(StartingState); cout endl;

Одна из наиболее важных процедур - получение вершин-потомков для любой заданной вершины:

добавить в список вершины, соседние с GameState

void AddNeighbours(Vertex* GameState)

int zi, zj;

найти нулевой кубик и получить его координаты zi, zj for(int i = 0; i < 4; i++)

for(int j = 0; j < 4; j++)

if(GameState->Stateti]tj] == 0) { zi = i; zj = j; break; }

int di[] = {-1, 0, 1, 0}, dj[] = (0, -1, 0, 1};

нулевой кубик можно сдвинуть в любую

из четырёх сторон

for(int к = 0; к < 4; к++)

i, j - новые координаты нулевого кубика int i = zi + di [к] ; int j = zj + dj [k] ;

если нулевой кубик не выходит за пределы коробки if(i >= О && j >= О && i <= 3 && j <= 3)

создать новую вершину Vertex* V = new Vertex;

скопировать в неё содержимое текущей

сору((int*)GameState->State, (int*)GameState + 16,

(int *)v->State)

новая позиция нулевого кубика v->State[i][j] = 0;

a на его месте - кубик (i, j) состояния GameState v->State[zi][zj] = GameState->StateLi][j];

Ради экономии места я использовал стандартную (медленную) версию функции поиска, чтобы определить, находится ли уже вершина, эквивалентная текзш1ей, во множестве Vertices. Лучше, конечно, использовать бинарный поиск, но для этого придётся приложить дополнительные усилия.

Чтобы обнаружить финишную вершину, нам потребуется функция IsGoaK):

является ли данная вершина финишной?

bool IsGoal(Vertex* s)

расположение кубиков в финишной вершине int Goal[4][4] = ( {1, 2, 3, 4), (5, 6, 7, 8}.

{9, 10, 11, 12), {13, 14, 15, 0} }; сравнить содержимое вершины s с массивом Goal return equal((int *)s->State, (int *)s->State + 16, (int *)Goal);

Осталось запрограммировать несложную функцию main ():

int main(int argc, char* argvt]) {

Initialize(); считать начальную конфигурацию int с = 0; счётчик итераций

while(!Queue.empty()) {

освободить память

for(set<Vertex*>::iterator р = Vertices.begin(); p != Vertices.end(); p++) delete *p;

return 0;

Пример. Поиск решения гшюволомки для начального состояния

12 3 4 5 6 7 8 9 10 11 12 15 13 14 О

потребовал выполнения программой 670 итераций:

12 3 4 5 6 7 8

9 10 11. 12

13 14 15 О

12 3 4 5 6 7 8

9 10 11 О

13 14 15 12

, извлечь головной элемент очереди Vertex* V = Queue.top(); Queue.pop(); С++;

если найдено решение

if(IsGoal(V))

вывести все состояния на пути от финишной конфигурации до стартовой

while(V != NULL)

v->Print();

V - v->Ancestor;

cout с вершин рассмотрено ; break;

else

решение не найдено: добавить в очередь вершины-потомки AddNeighbours(v);

цена = цена вершины-родителя + 1 v->Cost = GaineState->Cost + 1; v->RecalculateHeuristics(); v->Ancestor = GameState;

если вершина с эквивалентным содержимым не рассмот- рена ранее (для сравнения вершин используется функция CompareVP)

if(find if(Vertices.begin О, Vertices.end(),

bind2nd(CompareVP, v)) == Vertices.end())

Queue.push(v); добавить вершину в очередь

Vertices.insert(v); ив список известных вершин

else

удалить уже рассмотренную вершину delete v;