Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 49

дуга( s, t, 3).

дуга( t, v, 1).

дуга( u, t, 2).

...

Другой способ — весь граф представлять как один объект. В этом случае графу соответствует пара множеств — множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро — парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра — функтор p. Тогда (ненаправленный) граф рис. 9.18 примет вид:

G1 = граф( [a, b, c, d],

 [p( а, b), p( b, d), p( b, с), p( c, d)] )

Рис. 9.18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.

Для представления направленного графа (рис. 9.18), применив функторы диграф и д (для дуг), получим

G2 = диграф( [s, t, u, v],

 [д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),

  д( v, u, 2) ] )

Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер.

Еще один способ представления графа — связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (рис. 9.18), например, можно представить как

G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]

G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]

Здесь символы '->' и '/' — инфиксные операторы.

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

• найти путь между двумя заданными вершинами;

• найти подграф, обладающий некоторыми заданными свойствами.

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

9.5.2. Поиск пути в графе

Пусть G — граф, а А и Z — две его вершины. Определим отношение

путь( А, Z, G, P)

где P — ациклический путь между А и Z в графе G. Если G — граф, показанный в левой части рис. 9.18, то верно:

путь( a, d, G, [a, b, d] )

путь( а, d, G, [a, b, c, d] )

Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:

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

Если А = Z , то положить P = [А], иначе найти ациклический путь P1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из P1.

В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае P1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:

путь1( А, P1, G, P)

Аргументы в соответствии с рис. 9.19 имеют следующий смысл:

• А — некоторая вершина,

• G — граф,

• P1 — путь в G,

• P — ациклический путь в G, идущий из А в начальную вершину пути P1, а затем — вдоль пути P1 вплоть до его конца.

Pис. 9.19. Отношение путь1: Путь — это путь между А и Z, в своей заключительной части он перекрывается с Путь1.

Между путь и путь1 имеется следующее соотношение:

путь( А, Z, G, P) :- путь1( А, [Z], G, P).

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

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

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

(3) для P выполняется отношение путь1( А, [X | P1], G, P).

путь( A, Z, Граф, Путь) :-

 путь1( А, [Z], Граф, Путь).

путь1( А, [А | Путь1, _, [А | Путь1] ).

путь1( А, [Y | Путь1], Граф, Путь) :-

 смеж( X, Y, Граф),

 принадлежит( X, Путь1), % Условие отсутствия цикла

 путь1( А, [ X, Y | Путь1], Граф, Путь).

Рис. 9.20. Поиск в графе Граф ациклического пути Путь из А в Z.

На рис. 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. Построение остовного дерева

Граф называется связным, если между любыми двумя его вершинами существует путь. Пусть G = (V, E) — связный граф с множеством вершин V и множеством ребep E. Остовное дерево графа G — это связный граф T = ( V,  E'), где E' — подмножество E такое, что

(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)

где T — остовное дерево графа G. Будем предполагать, что G — связный граф. Можно представить себе алгоритмический процесс построения остовного дерева следующим образом. Начать с пустого множества ребер и постепенно добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы. Продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку любое новое ребро порождает цикл. Полученное множество ребер будет остовным деревом. Отсутствие циклов можно обеспечить, если придерживаться следующего простого правила: ребро присоединяется к дереву только в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него. Программа, реализующая эту идею, показана на рис. 9.22. Основное отношение, используемое в этой программе, — это