Основные методы поиска
 |
Существует много различных подходов к проблеме поиска решающего пути для задач сформулированных в терминах пространства состояний. В качестве примера графа, представляющего пространство состояний некоторой задачи, мы будем использовать граф на рис. 2.3. Поскольку мы считаем, что по любому ребру мы можем двигаться в обоих направлениях, то стрелки на ребрах не указаны.
Рис. 2.3. Пространство состояний. s -начальная
вершина, f - целевая вершина
При поиске пути из начальной в целевую вершину нам необходимо:
· использовать некоторую схему учета, позволяющую упорядоченным способом исследовать все возможные пути;
· не допускать циклов.
 |
Для лучшего представления множества путей в графе полезно будет преобразовать граф в дерево (рис. 2.4), при этом корнем дерева является начальная вершина, а листья дерева - это целевые или тупиковые вершины (тупики возникают в связи с нашим требованием не допускать циклов).
Рис. 2.4. Преобразование графа в дерево
Заметим, что число ярусов в полученном дереве не превосходит числа вершин в графе.
