Искусственный интеллект и экспертные системы

         

Основные методы поиска



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

Рис. 2.3. Пространство состояний. s -начальная

 вершина, f - целевая вершина

При поиске пути из начальной в целевую вершину нам необходимо:

·        использовать некоторую схему учета, позволяющую упорядоченным способом исследовать все возможные пути;



·        не допускать циклов.


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

Рис. 2.4. Преобразование графа в дерево

Заметим, что число ярусов в полученном дереве не превосходит числа вершин в графе.



Содержание раздела