Реализация сетевых моделей на Прологе.

В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро парой вершин [1]. Если каждая вершина графа соединена ребром еще, по крайней мере, с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку неявным образом содержится в списке ребер. Еще один способ представления графа - связать с каждой вершиной список смежных вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины плюс ее список смежности.

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

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

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

Рассмотрим подробнее понятие списка в Прологе.

Список - это в самом общем смысле, структура, которая либо

· пуста, либо

· состоит из головы и хвоста, причем хвост должен быть сам списком.

Список рассматривается в Прологе как специальный частный случай двоичного дерева [1]. Для повышения наглядности программ на Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде

 

[элемент1, элемент2, …]

или

[голова | хвост]

или

[элемент1, элемент2, …| остальные].

 

Списки можно применять для представления упорядоченных множеств, хотя и существует некоторое различие между этими понятиями: один и тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них

проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;

конкатенация (сцепления) двух списков, что соответствует объединению множеств;

добавление нового объекта в список или удаление некоторого объекта из него.

Реализация рассмотренных сетевых моделей на Прологе приведена ниже.

1) Программа на Прологе для задачи на нахождение гамильтонова цикла на заданном фрагменте сети:

 

Domains % Раздел определения типов данных

spisok=integer*

sp=symbol*

 

Predicates % Раздел описания заголовков предикатов

цепь (symbol, integer, sp, spisok, integer)

всп_цепь (symbol, integer, sp, sp, spisok, integer)

дуга (symbol, symbol, integer, integer)

ребро (symbol, symbol, integer, integer)

принадлежит (symbol, sp)

количество (spisok, integer, integer)

цикл (symbol, integer, sp, spisok)

итог (symbol, integer, sp, spisok)

минимум (spisok, integer)

последний (sp, symbol)

Goal % Раздел описания цели, в котором   располагается целевое утверждение итог (a, I, L,Y).

 

Clauses % Раздел описания фактов и правил

дуга(x,v1,1,2). % факты предиката дуга()

дуга(v1,v2,2,1).

дуга(v2,v3,3,1).

дуга(v2,v3,4,3).

дуга(v3,v4,5,1).

дуга(v1,v4,6,1).

дуга(v3,v4,7,1).

дуга(v4,y,7,1).

дуга(x,y,7,1).

дуга(x,y,7,4).

 

итог(X,D,L,P):-findall(K, цикл(_,K,_,_),U), минимум(U,D), цикл(X,D,L,P).

цикл(X,D,L,P):-findall(K, цепь(K,_,_,_,_,_),M), количество (M,R,_), цепь(X,D,L,P,R).

цепь (X,D,L,P,R):- всп_цепь (X,D,L,[],P,R).

всп_цепь (X,D,[X,Y],K,[N],1):-ребро (X,Y,N,D), последний(K,Y).

всп_цепь(X,D,[X|L],K,[N|P],R):- ребро(X,Z,N,D1), not(принадлежит(Z,K)), R1=R-1, всп_цепь (Z,D2,L,[X|K],P,R1), D=D1+D2.

ребро(P,T,H,N):-дуга(P,T,H,N).

ребро(P,T,H,N):-дуга(T,P,H,N).

принадлежит (X,[X|_]):-!.

принадлежит (X,[_|L]):- принадлежит (X,L). % определяет принадлежность элемента списку

минимум ([X],X). % возвращает минимальный элемент списка

минимум ([X|T],M):- минимум (T,M),M<=X,!.

минимум ([X|_],X).

последний ([X],X). % возвращает последний элемент в списке

последний ([_|T],X):- последний (T,X).

количество ([ ],0,0). % определяет количество элементов в списке

количество ([X|C],D,S):- количество (C,D1,S1),D=D1+1,S=S1+X.

 

2) Программа на Прологе для задачи на нахождение эйлерова цикла в заданном фрагменте сети:

 

Domains % Раздел определения типов данных

spisok=integer*

 

Predicates % Раздел описания заголовков предикатов

путь (symbol, symbol, spisok)

всп_путь (symbol, symbol, spisok, spisok)

дуга (symbol, symbol, integer)

ребро (symbol, symbol, integer)

принадлежит (integer, spisok)

длина (spisok, integer)

цикл (symbol, symbol, spisok)

 

Goal % Раздел описания цели, в котором   располагается целевое утверждение

цикл(a,a,P).

 

Clauses % Раздел описания фактов и правил

дуга (a,b,1). % факты предиката дуга()

дуга (b,c,2).

дуга (b,c,3).

дуга (d,e,4).

дуга (e,c,5).

дуга (e,b,6).

дуга (e,d,5).

дуга (a,e,6).

 

цикл(T,I,E):-findall(K,дуга(_,_,K),L),длина(L,R),путь(T,I,E),длина(E,R).

путь(X,Y,L):-всп_путь(X,Y,L,[]). % правила предиката путь()

всп_путь(X,Y,[N],P):-ребро(X,Y,N),not(принадлежит(N,P)).

всп_путь(X,Y,[N|R],P):-ребро(X,Z,N),not(принадлежит(N,P)),всп_путь(Z,Y,R,[N|P]).

 

ребро(P,T,H):-дуга(P,T,H). % правила предиката ребро()

ребро(P,T,H):-дуга(T,P,H).

 

принадлежит(X,[X|_]):-!. % определяет принадлежность элемента списку

принадлежит(X,[_|L]):-принадлежит(X,L).

длина([],0). % определяет количество элементов в списке

длина([_|B],K):-длина(B,K1),K=K1+1.