Поиск как основа функционирования СОЗ
СОЗ, в том числе и экспертные системы, имеют специфическую организацию. Суть которой заключается в том, что они осуществляют поиск некоторой цели (т.е. конечного состояния) на основе некоторых исходных посылок и набора фактов (т.е. начального состояния) (рис. 8.1).
Рис. 8.1. Поиск в СОЗ
Причем поиск конечного состояния выполняется автоматически на основе реализованной в СОЗ стратегии поиска, которая:
- реализует возможность выбора;
- позволяет выполнять шаги от начального состояния к новым состояниям, более или менее близким к цели.
Таким образом, реализованные в СОЗ стратегии поиска отыскивают цель, «шагая» от одного состояния системы к другому. При этом они обеспечивают распознавание ситуации, когда они находят цель или попадают в тупик.
Как правило, на промежуточных стадиях вычисляется некоторое число (критерий), посредством которого программа поиска оценивает свой ход и определяет дальнейшее направление поиска требуемого конечного состояния. При этом цель может быть одна или же может иметься некоторый набор приемлемых целей (конечных состояний).
Большинство СОЗ работают по этой модели.
Рассмотрим процесс поиска на конкретном примере. Пусть имеем карту дорог (рис. 8.2), по которой мы хотим изучить маршрут движения из одного конкретного города в другой.
Система, построенная на основе знаний об этой карте дорог, должна поработать с картой и спланировать наше путешествие, например из города «А» в город «F».
При решении представленной задачи компьютер преобразует исходную карту и представит ее в виде дерева поиска, которое без учета циклов будет иметь вид рис. 8.3.
Рис. 8.2. Карта дорог
Дерево поиска показывает все возможные варианты выбора при движении из «А» (начальное состояние), а также и все варианты выбора в каждом из промежуточных пунктов (состояний).
Место, откуда начинается поиск, находится в вершине дерева поиска.
Все дороги, начинаясь в «А», либо приводят в тупик, либо заканчиваются в «F».
Рис. 8.3. Дерево поиска
Задача компьютера состоит в том, чтобы найти подходящую дорогу из вершины дерева к конечному состоянию (цели) в его нижней части.
Человек при взгляде на дерево поиска сразу же выберет подходящую дорогу, но компьютер на это не способен. Какую стратегию поиска применит компьютер?
Рассмотрим пример, который заставит нас думать как компьютер.
Мы находимся в темной комнате, на стене которой дерево поиска, а у нас фонарик, который освещает всего два соседних пункта.
Нам известно, где расположена вершина дерева, откуда надо начать поиск. Как наиболее эффективно перемещать луч фонарика, чтобы найти маршрут до «F»?
При отсутствии какой-либо дополнительной информации компьютер для поиска использует стратегию «грубой силы». При этом программа поиска осуществляет поиск цели, идя от состояния к состоянию, и систематически исследуя все возможные пути.
Для определения каждого последующего шага применяется некая простая механическая стратегия, которая имеет две разновидности: поиск в глубину и поиск в ширину.