Обзор исследований в области искусственного интеллекта


Обзор исследований в области искусственного интеллекта - стр. 4


Рис. 2.1. Дерево пространства состояний головоломки 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, а потом уже строятся его потомки.


Начало  Назад  Вперед