Дерево пространства состояний головоломки Scrabble с буквами Т, С и А

Дерево пространства состояний головоломки Scrabble с буквами Т, С и А

Это пространство состояний обладает двумя интересными свойствами, которые присущи далеко не всем пространствам состояний:

• оно конечно, поскольку существует только п! способов расставить я букв;
  
• оно не содержит повторяющихся узлов, что может привести к образованию петель на графе.
  

Метод формирования анаграмм последовательным перечислением является примером применения алгоритма, получившего наименование generate-and-test (порождение и проверка).

(1) Генерировать новое состояние, модифицируя существующее; например, изменить последовательность букв, добавив новую в существующую последовательность.

(2) Проверить, не является ли образовавшееся состояние конечным (решением); например, проверить, не является ли образовавшаяся последовательность осмысленным словом. Если это так, то завершить, иначе перейти к шагу (1).

Множество решений, которые удовлетворяют условию на шаге (2), иногда называют пространством решений. В некоторых головоломках, например в уже упомянутой "8 ферзей", решений много, а в других существует всего несколько или только одно. Действительно, существует довольно много способов разместить восемь ферзей на шахматной доске так, чтобы ни один из них не оказался под боем, а вот для головоломки "8-Puzzle" существует единственное решение (см. упр. 7).

Алгоритм имеет два основных варианта: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Отличаются варианты порядком формирования состояний на шаге (1). Действительные алгоритмы приведены в упр. 5, а здесь мы дадим только их неформальное описание.

Для любого данного узла N алгоритм поиска в глубину строит потомок этого узла, т.е. формирует состояние, которое образуется в результате применения операторов к узлу N, а потом переходит к формированию узла, ближайшего к N, на том же уровне графа ("соседу" N), т.е. формирует состояние, которое образуется в результате применения оператора к узлу-родителю N. Алгоритм поиска в ширину действует наоборот — сначала формируются все "соседи" узла N, а потом уже строятся его потомки. Таким образом, в алгоритме поиска в ширину просматриваются последовательно состояния, представленные узлами одного и того же уровня на графе (рис. 2.2), а в алгоритме поиска в глубину просматриваются состояния на одном пути, а затем происходит возврат назад на один уровень и формируется следующий путь (рис. 2.3).