Эвристики в пятнашках
Эвристики
Напомним, что эвристика это оценка расстояния от данного состояния к целевому. Если эвристика совпадает с истинным значением, то поиск идёт сразу в оптимальном направлении, раскрывая только состояния на кратчайшем пути и непосредственных к нему соседях. Когда эвристика занижена (меньше истинного расстояния), начинает преобладать поиск в ширину и алгоритм раскрывает большое число узлов. При этом гарантируется (если хватит времени и памяти) нахождение оптимального решения. Наконец, если эвристика завышена (больше истинного расстояния), поиск может ускорится, но решение не обязательно будет оптимальным (найден будет не кратчайший путь).
В этом документе, на примере пятнашек, мы обсудим применение различных эвристик и сравним их между собой. Кроме этого будет более подробно изучено пространство этой головоломки.
Восьмушки
| 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 |
| 8,7,6,0,4,1,2,5,3 | 8,0,6,5,4,7,2,3,1 | |
| d = 31 | d = 31 |
Расстояние между этими состояниями равно 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 и отклонение от него (по всем узлам на данном расстоянии) первой эвристики (эвристика места)
и затем для второй (манхэттенская эвристика):
| d | count | aver1 | sigm1 | min1 | max1 | aver2 | sigm2 | min2 | max2 | h1>h2 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 1.0 | 0.0 | 1 | 1 | 1.0 | 0.0 | 1 | 1 | 0 |
| 2 | 4 | 2.0 | 0.0 | 2 | 2 | 2.0 | 0.0 | 2 | 2 | 0 |
| 3 | 8 | 3.0 | 0.0 | 3 | 3 | 3.0 | 0.0 | 3 | 3 | 0 |
| 4 | 16 | 3.9 | 0.3 | 3 | 4 | 4.0 | 0.0 | 4 | 4 | 0 |
| 5 | 20 | 4.6 | 0.7 | 3 | 5 | 5.0 | 0.0 | 5 | 5 | 0 |
| 6 | 39 | 5.0 | 1.0 | 3 | 6 | 5.8 | 0.6 | 4 | 6 | 0 |
| 7 | 62 | 5.4 | 1.1 | 4 | 7 | 6.6 | 0.8 | 5 | 7 | 0 |
| 8 | 116 | 5.8 | 1.2 | 3 | 8 | 7.4 | 1.1 | 4 | 8 | 0 |
| 9 | 152 | 6.1 | 1.2 | 3 | 8 | 8.2 | 1.2 | 5 | 9 | 0 |
| 10 | 286 | 6.2 | 1.3 | 2 | 8 | 8.7 | 1.6 | 4 | 10 | 0 |
| 11 | 396 | 6.3 | 1.2 | 1 | 8 | 9.3 | 1.8 | 3 | 11 | 0 |
| 12 | 748 | 6.4 | 1.2 | 2 | 8 | 9.7 | 2.0 | 4 | 12 | 0 |
| 13 | 1024 | 6.4 | 1.2 | 3 | 8 | 10.1 | 2.1 | 5 | 13 | 0 |
| 14 | 1893 | 6.5 | 1.2 | 2 | 8 | 10.4 | 2.3 | 4 | 14 | 0 |
| 15 | 2512 | 6.6 | 1.2 | 3 | 8 | 10.9 | 2.3 | 5 | 15 | 0 |
| 16 | 4485 | 6.7 | 1.2 | 2 | 8 | 11.1 | 2.4 | 4 | 16 | 0 |
| 17 | 5638 | 6.8 | 1.0 | 3 | 8 | 11.7 | 2.4 | 5 | 17 | 0 |
| 18 | 9529 | 6.8 | 1.0 | 2 | 8 | 12.0 | 2.5 | 4 | 18 | 0 |
| 19 | 10878 | 6.9 | 1.0 | 3 | 8 | 12.6 | 2.4 | 5 | 19 | 0 |
| 20 | 16993 | 7.0 | 1.0 | 2 | 8 | 12.9 | 2.4 | 4 | 20 | 0 |
| 21 | 17110 | 7.1 | 0.9 | 3 | 8 | 13.6 | 2.4 | 5 | 21 | 0 |
| 22 | 23952 | 7.1 | 0.9 | 3 | 8 | 13.8 | 2.4 | 4 | 22 | 0 |
| 23 | 20224 | 7.2 | 0.8 | 3 | 8 | 14.7 | 2.4 | 7 | 21 | 0 |
| 24 | 24047 | 7.2 | 0.8 | 3 | 8 | 14.8 | 2.4 | 6 | 22 | 0 |
| 25 | 15578 | 7.3 | 0.8 | 3 | 8 | 15.7 | 2.4 | 9 | 21 | 0 |
| 26 | 14560 | 7.3 | 0.8 | 4 | 8 | 15.8 | 2.3 | 8 | 22 | 0 |
| 27 | 6274 | 7.4 | 0.7 | 4 | 8 | 16.8 | 2.2 | 9 | 21 | 0 |
| 28 | 3910 | 7.4 | 0.7 | 3 | 8 | 16.7 | 2.2 | 10 | 22 | 0 |
| 29 | 760 | 7.4 | 0.7 | 5 | 8 | 17.5 | 2.5 | 11 | 21 | 0 |
| 30 | 221 | 7.1 | 0.8 | 5 | 8 | 16.7 | 2.9 | 12 | 22 | 0 |
| 31 | 2 | 7.0 | 0.0 | 7 | 7 | 21.0 | 0.0 | 21 | 21 | 0 |
Как видно, "эвристика правильных мест" хорошо работает только для малых расстояний (d < 7). На больших расстояниях она даёт заниженное значение и не является эффективной. "Манхэттенская эвристика" работает существенно лучше. Более того, являясь допустимой, она всегда даёт большее значение расстояния к целевому состоянию. Впрочем, далеко от него её предсказательная сила также падает.