Введение в экспертные системы



              


Глава 2.1.1. Поиск в пространстве состояний



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


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

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

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









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