Между

и имеется следующее соотношение:

На рис. 9.19 показана идея рекурсивного определения отношения

. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути P. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что

(1) Y — вершина, смежная с X,

(2) X не содержится в P1 и

(3) для P выполняется отношение

.

Рис. 9.20. Поиск в графе

ациклического пути из А в Z.

На рис. 9.20 программа показана полностью. Здесь

 — отношение принадлежности элемента списку. Отношение

означает, что в графе G существует дуга, ведущая из X в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)

то

Классическая задача на графах — поиск Гамильтонова цикла, т.е. ациклического пути, проходящего через все вершины графа. Используя отношение

, эту задачу можно решить так:

Здесь

означает:  — вершина графа .

Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.

Для того, чтобы наши отношения

и могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:

Здесь С — стоимость пути P, a C1 — стоимость пути P1. В отношении

также появится дополнительный аргумент, стоимость дуги. На рис. 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.

Рис. 9.21. Поиск пути в графе:

 — путь между А и Z в графе стоимостью Ст.

Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами

, графа , задав цели

Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели

Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.