Иллюстрированный самоучитель по введению в экспертные системы



     цвет мочи здорового человека | газ 3101 |          

Поиск в пространстве состояний


Фундаментальная идея, которая появилась в результате этих первых опытов, получила наименование поиск в пространстве состояний. По существу, идея очень проста. Множество проблем можно сформулировать в терминах трех важнейших ингредиентов:

  • исходное состояние проблемы, например исходное состояние головоломки;

  • тест завершения — проверка, достигнуто ли требуемое конечное состояние или найдено решение проблемы (примером может послужить правило определения, собрана ли головоломка);

  • множество операций, которые можно использовать для изменения текущего состояния проблемы, например шаги или перемещения фигур при сборке головоломки.

    Один из способов представления такого концептуального пространства состояний — граф, в котором состояниям соответствуют узлы, а операциям — дуги. Рассмотрим в качестве примера задачу построения слова из некоторого множества букв, как в игре Scrabble. Задавшись набором операций установки букв, можно сформировать пространство состояний.

    Предположим, что множество доступных букв включает Т, С и А. На каждом уровне графа мы будем добавлять по одной определенной букве. Каждая ветвь, исходящая из узла, соответствует установке буквы в определенную позицию в последовательности, а эта последовательность должна образовать осмысленное слово (рис. 2.1). Если это произошло, то головоломка считается собранной (например, если образовалась комбинация "act" или "cat"). (Сейчас мы не будем стремиться собрать какое-нибудь сложное слово вроде "scrabble", которое может принести играющему больше очков.)

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

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

  • оно конечно, поскольку существует только п! способов расставить я букв;

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

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



    Содержание  Назад  Вперед