Методы поиска в пространствах состояний

Пример 5.

Имеется фрагмент базы данных из двух правил:

П1. Если «отдых — летом» и «человек — активный», то «ехать в горы».

П2. Если «любит солнце», то «отдых летом».

Предположим, в систему поступили факты — «человек активный» и «любит солнце».

ПРЯМОЙ ВЫВОД — исходя из фактических данных, получить рекомендацию.

1-й проход.

Шаг 1. Пробуем П1, не работает (не хватает данных «отдых — летом»).

Шаг 2. Пробуем П2, работает, в базу поступает факт «отдых — летом».

2-й проход.

Шаг 3. Пробуем П1, работает, активируется цель «ехать в горы», которая и выступает как совет, который дает ЭС.

ОБРАТНЫЙ ВЫВОД — подтвердить выбранную цель при помощи имеющихся правил и данных.

1-й проход.

Шаг 1. Цель — «ехать в горы»: пробуем П1 — данных «отдых — летом» нет, они становятся новой целью и ищется правило, где цель в левой части.

Шаг 2. Цель «отдых — летом»: правило П2 подтверждает цель и активирует ее.

2-й проход.

Шаг 3. Пробуем П1, подтверждается искомая цель.

В системах, база знаний которых насчитывает сотни правил, желательным является использование стратегии управления выводом, позволяющей минимизировать время поиска решения и тем самым повысить эффективность вывода. К числу таких стратегий относится: поиск в глубину, поиск в ширину, разбиение на подзадачи и альфа-бета алгоритм [Таунсенд, Фохт, 1991; Уэно, Исидзука, 1989; Справочник по ИИ, 1990].

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

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

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

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