Программирование на языке Пролог для искусственного интеллекта




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



    (а)     Граф.    (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]]

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

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

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

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

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

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

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

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

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

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

line();

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

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

line();

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

        путь1( А, Р1, G, Р)

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

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









Начало  Назад  Вперед