Поиск решений

Сформулировав определение задачи, необходимо найти ее решение. Это достигается посредством поиска в пространстве состояний. Для поиска используется так называемое дерево поиска, которое создается с помощью начального состояния и функции определения преемника. Ниже рассмотрен принцип его использования.

Для упрощения обозначим города латинскими буквами A—F (см. рис.3).

Корнем дерева поиска является начальное состояние А (Лос-Анджелес) (см рис.4). Первый этап состоит в проверке того, является ли корневое состояние целевым. Безусловно, оно таковым не является. Поскольку цель не достигнута, необходимо рассмотреть другие состояния, в нашем случае это города Сан-Фернандо (В) и Санта-Моника (С). Такой этап осуществляется путем развертывания текущего состояния, т.е. применения функции определения преемника к текущему состоянию для формирования нового множества состояний. Таким образом, получены новые состояния (см. рис.5–6), которые также необходимо проверить на соответствие цели и аналогичным образом развернуть.

Рис.4. Дерево поиска. Проверка корневой вершины

Рис.5. Дерево поиска после развертывания вершины А

Рис.6. Дерево поиска после развертывания вершины С

В этом и состоит суть поиска — пока что проверить один вариант и отложить другие в сторону. Данный процесс продолжается до тех пор, пока не будет найдено целевое состояние. Порядок, в котором происходит развертывание дерева, называется стратегиейпоиска.

Необходимо различать понятия пространство состояний и дерево поиска. В нашем случае пространство состояний — это карта Калифорнии, оно имеет только 6 состояний (см. рис.3). Дерево поиска описывает все возможные переходы между состояниями путем развертывания узлов, и число его вершин может быть бесконечно.

Дата добавления: 2015-07-26; просмотров: 139; Нарушение авторских прав

Мы поможем в написании ваших работ!