На рис. 9.20 программа показана полностью. Здесь принадлежит
— отношение принадлежности элемента списку. Отношение
смеж( X, Y, G)
означает, что в графе G существует дуга, ведущая из X в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)
G = граф( Верш, Реб)
то
смеж( X, Y, граф( Верш, Реб) ) :-
принадлежит( p( X, Y), Реб);
принадлежит( p( Y, X), Реб).
Классическая задача на графах — поиск Гамильтонова цикла, т.е. ациклического пути, проходящего через все вершины графа. Используя отношение путь
, эту задачу можно решить так:
гамильтон( Граф, Путь) :-
путь( _, _, Граф, Путь),
всевершины( Путь, Граф).
всевершины( Путь, Граф) :-
not (вершина( В, Граф),
not принадлежит( В, Путь) ).
Здесь вершина( В, Граф)
означает: В
— вершина графа Граф
.
Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.
Для того, чтобы наши отношения путь
и путь1
могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:
путь( А, Z, G, P, С)
путь1( A, P1, C1, G, P, С)
Здесь С — стоимость пути P, a C1 — стоимость пути P1. В отношении смеж
также появится дополнительный аргумент, стоимость дуги. На рис. 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.
путь( А, Z, Граф, Путь, Ст) :-
путь1( A, [Z], 0, Граф, Путь, Ст).
путь1( А, [А | Путь1], Ст1, Граф, [А | Путь1], Ст).
путь1( А, [Y | Путь1], Ст1, Граф, Путь, Ст) :-
смеж( X, Y, СтXY, Граф),
not принадлежит( X, Путь1),
Ст2 is Ст1 + СтXY,
путь1( А, [ X, Y | Путь1], Ст2, Граф, Путь, Ст).
Рис. 9.21. Поиск пути в графе: Путь
— путь между А и Z в графе Граф
стоимостью Ст.
Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами Верш1
, Верш2
графа Граф
, задав цели
путь( Bepш1, Верш2, Граф, МинПуть, МинСт),
not( путь( Верш1, Верш2, Граф, _, Ст), Ст<МинСт )
Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели
путь( _, _, Граф, МаксПуть, МаксСт),
not( путь( _, _, Граф, _, Ст), Ст > МаксСт)
Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.
9.5.3. Построение остовного дерева
Граф называется
(1) T — связный граф,
(2) в T нет циклов.
Выполнение этих двух условий гарантирует то, что T — дерево. Для графа, изображенного в левой части рис. 9.18, существует три остовных дерева, соответствующих следующим трем спискам ребер:
Дер1 = [а-b, b-c, c-d]
Дер2 = [а-b, b-d, d-с]
Дер3 = [а-b, b-d, b-c]
Здесь каждый терм вида X-Y обозначает ребро, соединяющее вершины X и Y. В качестве корня можно взять любую из вершин, указанных в списке. Остовные деревья представляют интерес, например в задачах проектирования сетей связи, поскольку они позволяют, имея минимальное число линий, установить связь между любыми двумя узлами, соответствующими вершинам графа.
Определим процедуру
остдерево( G, T)