Эвристики в пятнашках


Эвристики

Напомним, что эвристика это оценка расстояния от данного состояния к целевому. Если эвристика совпадает с истинным значением, то поиск идёт сразу в оптимальном направлении, раскрывая только состояния на кратчайшем пути и непосредственных к нему соседях. Когда эвристика занижена (меньше истинного расстояния), начинает преобладать поиск в ширину и алгоритм раскрывает большое число узлов. При этом гарантируется (если хватит времени и памяти) нахождение оптимального решения. Наконец, если эвристика завышена (больше истинного расстояния), поиск может ускорится, но решение не обязательно будет оптимальным (найден будет не кратчайший путь).

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


Восьмушки

d  count
0 1
1 2
2 4
3 8
4 16
5 20
6 39
7 62
8 116
9 152
10 286
11 396
12 748
13 1024
14 1893
15 2512
16 4485
17 5638
18 9529
19 10878
20 16993
21 17110
22 23952
23 20224
24 24047
25 15578
26 14560
27 6274
28 3910
29 760
30 221
31 2
Возьмём в качестве начального состояния базовую конфигурацию восьмушек:
0,1,2,3,4,5,6,7,8
d = 0
и посчитаем число состояний, отстоящих от начального на различные расстояния. Справа приведена соответствующая таблица. Два состояния удалены на максимальное расстояние 31:
8,7,6,0,4,1,2,5,3 8,0,6,5,4,7,2,3,1
d = 31 d = 31
Это число принято называть числом Бога (можно подумать другие числа не от него). В общем случае число Бога - это максимально возможная длина решения головоломки при самом "неудачном" начальном состоянии и оптимальной стратегии. Последовательность ходов решения полностью определяется положением дырки. Для этих двух состояний по два различных кратчайших решений имеют вид:

3,4,5,8,7,6,3,0,1,2,5,4,7,6,3,0,1,2,5,4,7,6,3,0,1,2,5,8,7,6,3,0 3,0,1,2,5,4,7,8,5,4,3,6,7,4,1,2,5,8,7,4,3,0,1,4,3,6,7,4,5,2,1,0
1,2,5,4,7,6,3,4,1,0,3,4,5,8,7,6,3,4,1,2,5,8,7,4,1,2,5,8,7,4,3,0 1,0,3,6,7,8,5,2,1,4,7,8,5,2,1,0,3,4,7,8,5,2,1,0,3,6,7,4,5,2,1,0

Расстояние между этими состояниями равно 16 с перемещениями дырки: 3,4,7,6,3,4,1,0,3,6,7,8,5,4,3,0,1.

Общее число допустимых состояний равно 9!/2=181440. Распределение по длинам имеет максимум при d=24 и монотонно убывает при удалении от него. При этом существует 7279 состояний с d < 16, что составляет лишь 4% от общего числа допустимых состояний. Число состояний, которые удалены на треть от максимального расстояния (d < 11) равно 706 или 0.4%.


Примеры эвристик

Рассмотрим две простейшие эвристики. Напомним, что в классе Fifteen состояние системы хранится в массиве desk с числом элементов nX * nY, где nX,nY - количество ячеек по горизонтали и вертикали. Функция fromString преобразует строку в массив. Так как вычисление расстояния между произвольными состояниями достаточно медленная операция, эвристики будем всегда вычислять по отношению к целевому состоянию 0,1,2,3....

Первая эвристика - число костяшк не на своих местах:

Fifteen.prototype.value1 = function (st)
{
   if(st)
      this.fromString(st);                        // воссоздаём состояние из строки

   var s = this.desk.length-1;                    // число костяшек (без дырки)
   for(var k = this.desk.length; k--; )           // бежим по костяшкам
      if(this.desk[k]===k && this.desk[k] > 0)    // если на своём месте и не дырка
         s--;                                     // уменьшаем расстояние
   return s;
}

Вторая эвристика - суммарное манхэттенское расстояние костяшек от своих мест в целевом состоянии:

Fifteen.prototype.value2 = function (st)
{
   if(st)
      this.fromString(st);                        // воссоздаём состояние из строки

   var s = 0;                                     // суммарное расстояние до цели
   for(var k = this.desk.length; k--; ){          // бежим по костяшкам
      var kd = this.desk[k];                      // k-я костяшка стоит на kd месте
      if(!kd)                                     // дырку не учитываем
         continue;
      var id = kd % this.nX, jd = (kd-id)/this.nX;// у него "координаты" (i,j)
      var ik = k  % this.nX, jk = (k-ik)/this.nX; // а должны быть координаты (ik,jd)
      s += Math.abs(ik-id) + Math.abs(jk-jd);     // манхэттенское расстояние
   }
   return s;
}

Обе эвристики допустимые, т.к. за один ход оценку можно уменьшить только на 1. Если бы правила позволяли вытаскивать и переносить костяшку на своё место, то эвристика места value1 была бы точной. Аналогично точной была бы "манхэттенская эвристика" value2, если бы костяшки можно было двигать невзирая на наличие соседей ("скользить по ним"). Это примеры ослабленных задач в которых меньше ограничений, чем в исходной задаче. Стоимость решения в ослабленной задаче - это допустимая эвристика исходной.


Сравнение эвристик

Сравним между собой приведенные выше эвристики. Для получения кооректной таблицы, необходимо выбрать поиск в ширину, начальное состояние сделать целевым (нажать кнопку init), а конечным сделать любое недостижимое состояние (например, после нажатия init поставить 2 нуля). Тогда запустится полный перебор (решения нет) в ширину, в котором будет вычисляться истинное расстояние к стартовому узлу и сравниваться с соответствующими эвристиками. Не забываем также поставить галочку у "эвристики". Галочка у "состояния" выведет все состояния (осторожно! - их много и стоит ставить ограничение по глубине).

Размер поля (nX:, nY:)
ограничение по глубине:
метод:
эвристики состояния
начальное состояние:
конечное  состояние:
h1 = , h2 = ,

Нажми на старт


Приведём результат запуска этого скрипта для восьмишек 3x3, где для узлов на каждом расстоянии d от целевого вычисляется среднее значение aver1 и отклонение от него (по всем узлам на данном расстоянии) первой эвристики (эвристика места) и затем для второй (манхэттенская эвристика):
dcountaver1sigm1min1max1aver2sigm2min2max2h1>h2
121.00.0111.00.0110
242.00.0222.00.0220
383.00.0333.00.0330
4163.90.3344.00.0440
5204.60.7355.00.0550
6395.01.0365.80.6460
7625.41.1476.60.8570
81165.81.2387.41.1480
91526.11.2388.21.2590
102866.21.3288.71.64100
113966.31.2189.31.83110
127486.41.2289.72.04120
1310246.41.23810.12.15130
1418936.51.22810.42.34140
1525126.61.23810.92.35150
1644856.71.22811.12.44160
1756386.81.03811.72.45170
1895296.81.02812.02.54180
19108786.91.03812.62.45190
20169937.01.02812.92.44200
21171107.10.93813.62.45210
22239527.10.93813.82.44220
23202247.20.83814.72.47210
24240477.20.83814.82.46220
25155787.30.83815.72.49210
26145607.30.84815.82.38220
2762747.40.74816.82.29210
2839107.40.73816.72.210220
297607.40.75817.52.511210
302217.10.85816.72.912220
3127.00.07721.00.021210

Как видно, "эвристика правильных мест" хорошо работает только для малых расстояний (d < 7). На больших расстояниях она даёт заниженное значение и не является эффективной. "Манхэттенская эвристика" работает существенно лучше. Более того, являясь допустимой, она всегда даёт большее значение расстояния к целевому состоянию. Впрочем, далеко от него её предсказательная сила также падает.