Применение эвристического поиска для нахождения решения в игре в "15"

Решение задач, таких как "поиск решения в игре 15", путем перебора приводит к комбинаторному взрыву.
Существует единственный эффективный способ борьбы с комбинированным взрывом - использование эвристик.

Эвристика - это любое правило сокращающее перебор.

При использовании эвристик в пространствово состоящий необходимо ввести некоторую дополнительную информацию, которая позволяет обосновать выбор очередной вершины.
Обычно эта дополнительная эвристическая информация используется для вычисления оценочных функций.
Оценочная функция "f" полностью зависит от конкретной задачи.
Она должна обеспечивать возможность ранжирования вершин - кандидатов на раскрытие с тем, чтобы выделить ту вершину, которая с наибольшей вероятностью находится на лучшем пути к цели.
f(n) - значение оценочной функции для вершины n.

Теперь применим этот медод для более конкретной задачи...
Вместо 16 позиций возьмём 8, т.к. нет смысла усложнять принцип лишними комбинациями решений.

f(n)=g(n)+h(n)
g(n) - стоимость пути из начальной вершины в вершину n при весе всех ребер (ходов) =1.
h(n)=CP+3*Y
СР - Суммарное расстояние
СР (сумма) = CPi (от 1-го до 8-ми)
где CPi - расстояние между текущем и конечным положением фишки i
CРi = растояние по вертикали + растояние по горизонтали

Пример 1:

конечное:
1
2
3
8
_
4
7
6
5
начальное:
_
2
3
1
8
4
7
6
5
СР1=1
СР8=1
остальные=0

Пример 2:

конечное:
1
2
3
8
_
4
7
6
5
начальное:
7
4
8
_
1
5
3
2
6
СР1=2 СР5=1
СР2=2 СР6=1
СР3=4 СР7=2
СР4=2 СР8=3
СР(сумма)=17

Y-степень упорядоченности фишек в текущей позиции по отношению к тому порядку, в котором они должны находиться в целевой позиции
Y (сумма) = Yi(от 1-го до 8-ми)
где Yi = 0, если фишки не в центральной позиции и непосредственно за ней по часовой стрелке следует та фишка которая и должна следовать.
1 - если фишка в центральной позиции
2 - если фишка не в центральной позиции и по часовой стрелке за ней следует не та фишка,

Пример 3:

 
1
2
3
8
_
4
7
6
5
1
3
4
8
_
2
7
6
5
СР1=2 СР5=1
СР2=2 СР6=1
СР3=4 СР7=2
СР4=2 СР8=3
СР(сумма)=17
Y1=2
Y2=2
Y3=0
Y4=2

Y5=0
Y6=0
Y7=0
Y8=0
Y(сумма) = Y1+...+Y8 = 6

Пример 3: (детальное рассмотрение)

начальное:
1
3
4
8
_
2
7
6
5
конечное:
1
2
3
8
_
4
7
6
5


S1(22)
1
3
4
8
_
2
7
6
5
S2(32) /
S3(26) /
S4(12) \
\ S4(32)
1
3
4
_
8
2
7
6
5
1
_
4
8
3
2
7
6
5
1
3
4
8
2
_
7
6
5
1
3
4
8
6
2
7
_
5
S6(17)
/
\ S7(19)
  
1
3
_
8
2
4
7
6
5
1
3
4
8
2
5
7
6
_
S8(10)
|
  
1
_
3
8
2
4
7
6
5
S9(17)
|
 \ S10  
_
1
3
8
2
4
7
6
5
1
2
3
8
_
4
7
6
5

 

все
выбор
S1(-,0,22)
S2(1,1,33)
S3(1,1,27)
S4(1,1,19)
S5(1,1,33)
S6(2,2,19)
S7(2,2,21)
S8(3,3,13)
S9(4,4,21)
S10(4,4,4)
1: S1(-,0,22)
2: S4(1,1,19)
3: S6(2,2,19)
4: S8(3,3,13)
5: S10(4,4,4)

 
S1 S2 S3
S4 S5 S6 S7 S8
S9 S10
CP 1
2
3
4
0 0 0
2 2 2
1 1 2
1 1 1
0 0 0 0 0
1 2 1 1 1
1 1 1 1 1
1 1 0 1 0
1 0
1 0
0 0
0 0
5
6
7
8
0 0 0
0 0 0
0 0 0
0 1 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0
0 0
0 0
0 0
Y 1
2
3
4
2 2 2
2 2 2
0 0 1
2 2 2
2 2 2 2 2
1 2 1 1 1
0 0 2 0 0
2 2 0 0 0
2 0
0 0
0 0
0 0
5
6
7
8
0 0 0
0 0 0
0 2 0
0 1 0
0 2 0 2 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0
0 0
0 0
2 0
3*Y
18 27 21
15 27 15 15 9
15 0
сумма
22 32 26
18 32 17 19 10
17 0