Остовное дерево минимальной стоимости, Prolog Опции

[18192123]

Здравствуйте!
Требуется построить остовное дерево минимальной стоимости..
(Остовное дерево графа 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 - 26.04.2009 19:22