Пространство состояний
Система и её состояние
Поиск решения задачи часто можно сформулировать в терминах нахождения кратчайшего пути между двумя узлами на некотором графе. Чтобы прояснить это утверждение, введем понятие системы и её состояния. Для этого рассмотрим две головоломки: пятнашки и Ханойские башни.
Пятнашки - это коробка,
в которой находятся 15 костяшек.
Нормальным положением будем считать то, которое приведено ниже (дырка - "костяшка"
под номером 0 находится в левом верхнем углу).
Стоит перемешав костяшки, попрбовать собрать головоломку (вернувшись к исходному положению).
Размер коробки
×
можно редактировать.
Ханойские башни состоят из 3-х стержней. На первый надеты n дисков увеличивающегося сверху вниз диаметра. Эти диски необходимо по одному переложить с первого стержня на второй. Можно использовать все стержни, но диски большего диаметра должны всегда находиться ниже дисков меньшего диаметра (можно менять число дисков: и стержней: ):
Обе эти задачи характеризуются:
- начальным состоянием (положение костяшек в коробке или дисков на башнях),
- правилами получения других состояний (перемещаем костяшки или диски),
- целевым состоянием, к которому необходимо прийти, используя эти правила.
Описание состояния
Способ описания данной системы, естественно, зависит от её устройства. В пятнашках c n костяшками (включаяя дырку с номером 0) состояние удобно описывать массивом desk[n]. Например, в "восьмишках" (n=9) возможны следующие состояния, для которых сверху приведен массив desk[n], а ниже, соответствующее ему игровое состояние:
| 0,1,2,3,4,5,6,7,8 | 8,7,6,0,4,1,2,5,3 | 8,0,6,5,4,7,2,3,1 | ||
В ханойской головоломке текущее состояние (расположение дисков по стержням) можно описать массивом disks размера nDisks. Каждый i-й элемент массива является номером (от нуля) стержня (башни) на котором находится i-й диск. Номера дисков также идут начиная с нуля, и меньшему номеру соответствует диск меньшего диаметра. Если ограничиться 10-ю стержнями, массив disks можно представлять в виде строки без запятых между числами. Ниже нарисованы два различных разрешенных состояний системы с 5-ю дисками и 3-я стержнями (над картинками приведено строковое описание состояния):
| 00000 | 11200 | |
Пространство ханойских башен
Наиболее компактное описание состояния системы, часто позволяет оценить число её возможных состояний. Строка типа "11200" состояния ханойской головоломки является записью числа с D = nDisks разрядами в системе исчисления по основанию T = nTowers. Поэтому число возможножных состояний равно TD. Для T = D = 3 существует 27 состояний, граф которых образует разновидность треугольника Серпинского (для наглядности слева в именах узлов графа стоят строковые описания состояния, а справа соответствующие им картинки с дисками):
Граф имеет достаточно простую регулярную структуру, с большим числом циклов. Это приводит к тому, что ханойская головоломка оказывается достаточно простой и для её оптимального решения (по крайней мере в случае 3-х стрежней) существует незатейливый алгоритм.
Пространство пятнашек
Состояние в пятнашках с n костяшками (включая дырку) характерезуется некоторой перестановкой n чисел от исходного порядка 0,1,2,...,n-1. Поэтому число возможных состояний равно n!. На самом деле, правила перестановки костяшек таковы, что ровно половина состояний оказывается недоступна (если вытащить из коробки две костяшки и переставить их местами, получится "несобираемая головоломка"). Поэтому реальное пространство поиска равно n!/2. Для пятишек (2x2, n=4) число достижимых состояний равно 12, для восьмишек (3x3, n=9) их уже 181'440, а для классических пятнашек состояний очень много: 10'461'394'944'000 ~ 1013.
Нарисовать полное постранство состояний для пятишек не сложно и его топология очень проста (обычное кольцо):
Для пятишек с их 181'440 состояниями полный граф привести проблематично. Ограничимся только состояниями, удалёнными от целевого на расстояние не более 4 хода:
На эту глубину граф имеет древестный вид с одним или двумя ветвлениями, однако, уже на расстоянии 5 существует состояние [4,3,2,0,1,5,6,7,8] (ниже оно второе) из которого можно за 5 ходов (налево) или за 7 (направо) добраться до целевого [0,1,2,3,4,5,6,7,8]
Самыми удалёнными (на 31 ход) от целевого состояния являются два:
| 8,7,6,0,4,1,2,5,3 | 8,0,6,5,4,7,2,3,1 |
Приведём ещё граф классических пятнашек на глубину 4 от целевого узла (он в центре). В этом случае из каждого узла выходит 2 ребра (дырка в углу), 3 ребра (дырка с краю) или 4 ребра (дырка в центральной части):
Цикл также начинается на глубине 5 с узла [5,4,2,3,0,1,6,7,8,9,10,11,12,13,14,15], а число Бога в этой головоломке равно 80.
В реальных задачах, обычно, графы возможных состояний системы очень велики, поэтому их узлы и рёбра переходов строятся по мере поиска решения некоторой задачи.
Дерево решения
Начнём от начального состояния переберать все соседние состояния.
Далее, соседей, соседей и т.д. При этом будем запоминать состояния в которых мы уже
были и повторно их соседей не рассматривать.
В результате, вместо графа, пространство поиска превратиться в дерево.
Например для Ханойской головоломки (3 диска и 3 стержня) дерево
от стартового состояния (все 3 на нулевом стержне) в корне имеет вид:
Поиск на деревьях несколько проще, чем на графах, поэтому мы начнём с них.