Правила форума
Внимание!
Требуется построить остовное дерево минимальной стоимости..
(Остовное дерево графа G = (V,E) - это связный граф T = (V,E1) без циклов,в котором E1 - подмножество E)
Просто остовное дерево - это есть..а вот с минимальной стоимостью - проблема..
Основная идея построения остовного дерева:
Остовное дерево можно строить так: 1) начать с произвольного реб-ра графа G; 2) добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы; 3) продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку лю-бое новое ребро порождает цикл. Отсутствие цикла обеспечивается так: ребро присоединяется к дереву лишь в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него.
Это и реализовано ниже
Код
arca(a,b). arca(b,c). arca(c,d). arca(b,d). %задаём граф
member(X,[X|_]). % правило проверяет входит ли элемент в список
member(X,[_|Tail]):-member(X,Tail).
%osttree - основное отношение
osttree(arca(A,B),Tree) :- expand([arca(A,B)],Tree).
%expand - производит добавление ребра, если это возможно
expand(Tree1,Tree) :- ap_arca(Tree1,Tree2), expand(Tree2,Tree).
expand(Tree,Tree) :-not(ap_arca(Tree,_)).
ap_arca(Tree,[arca(A,B)|Tree]) :- arca(A,B), node(A,Tree), not(node(B,Tree));
arca(A,B),node(B,Tree), not(node(A,Tree)).
node(A,Tree) :- member(arca(A,_),Tree); member(arca(_,A),Tree).
результаты такие:
?- osttree(arca(a,b),Tree). %arca(a,b) - начинаем формирование дерева с указанного ребра
Tree = [arca(c, d), arca(b, c), arca(a, b)] ,
Tree = [arca(b, d), arca(b, c), arca(a, b)] ,
Tree = [arca(b, d), arca(b, c), arca(a, b)] ,
Tree = [arca(b, c), arca(b, d), arca(a, b)] ,
Tree = [arca(b, c), arca(b, d), arca(a, b)] ,
Tree = [arca(c, d), arca(b, d), arca(a, b)] ,
no
?-
попробовала описать взвешенный граф и добавить поиск дерева минимальной стоимости..
Код
arca(a,b,1). arca(b,c,3). arca(c,d,1). arca(b,d,7).
member(X,[X|_]).
member(X,[_|Tail]):-member(X,Tail).
osttree(arca(A,B,C),Tree,C) :- expand([arca(A,B,C)],0,Tree,C).
expand(Tree1,C1,Tree,C) :- ap_arca(Tree1,Tree2,CXY),C2=C1+CXY, expand(Tree2,C2,Tree,C).
expand(Tree,C,Tree,C) :-not(ap_arca(Tree,_,C)).
ap_arca(Tree,[arca(A,B,C)|Tree],C) :- arca(A,B,C), node(A,Tree), not(node(B,Tree));
arca(A,B,C),node(B,Tree), not(node(A,Tree)).
node(A,Tree) :- member(arca(A,_,_),Tree); member(arca(_,A,_),Tree).
db0(X,Y):-osttree(arca(X,Y,C),P,C),assert(db_path(X,Y,P,C)).
db(X,Y):-db_path(X,Y,P,C), osttree(arca(X,Y),MP,MC), MC<C,!,
retract(db_path(X,Y,P,C)), assert(db_path(X,Y,MP,MC)), db(X,Y).
db(_,_).
результаты какие-то странные..
?- db0(a,b),db(a,b),db_path(a,b,MP,MC).
MP = [arca(c, d, 1), arca(b, c, 3), arca(a, b, 0 + 3 + 1)]
MC = 0 + 3 + 1 .
yes
?-
Скажите, это вообще правильно??
Сообщение отредактировано: 18192123 -
