Suche alle Pfade und den kürzesten Pfad für eine Grafik - Prolog

Ich habe ein problem in meinem code mit turbo-prolog, die durchsucht alle Pfade und den kürzesten Weg in einem Graphen zwischen 2 Knoten.
Das problem, das ich habe, ist zu testen, ob der Knoten in der Liste ist oder nicht (genau in der Klausel Mitglied)

           1    ---- b ----   3
           ---       |        ---
        ---          |             -----
      a              |5                  d
        ---          |             -----
            ---      |         ---
             2  ---  |     ---   4
                  -- c  --

for example we have for b--->c 
([b,c],5) , ([b,a,c],3) and ([b,d,c],7) : possible paths.
([b,a,c],3) : the shortest path.

und das ist mein code :

DOMAINS
    list=Symbol *

PREDICATES
    distance(Symbol, Symbol)
    path1(Symbol, Symbol, list, integer)
    path(Symbol, Symbol,list, list, integer)
    distance(Symbol, list, integer)
    member(Symbol, list)
    shortest(Symbol, Symbol, list, integer)

CLAUSES
    distance(a, b, 1).
    distance(a, c, 2).
    distance(b, d, 3).
    distance(c, d, 4).
    distance(b, c, 5).
    distance(b, a, 1).
    distance(c, a, 2).
    distance(d, b, 3).
    distance(d, c, 4).
    distance(c, b, 5).

    member(X, [X|T]).
    member(X, [Y|T]) :- member(X, T).

    absent(X, L) :-
        member(X, L),
        !,
        fail.
    absent(_, _).

    /* find all paths */
    path1(X, Y, L, C) :- path(X, Y, L, I, C).
    path(X, X, [X], I, C) :- absent(X, I).
    path(X, Y, [X|R], I, C) :-
        distance(X, Z, A),
        absent(Z, I),
        path(Z, Y, R, [X|I], C1),
        C = C1 + A
        .

    /* to find the shortest path */
    shortest(X, Y, L, C) :-
        path(X, Y, L, C),
        path(X, Y, L1, C1),
        C < C1.
Sie nicht sagen, was Ihre Frage ist.

InformationsquelleAutor | 2010-04-01

  1. 1

    Dieser zeigt den kürzesten Weg und das Gewicht:

    edge(a,b,6).
edge(a,c,1).
edge(b,d,5).
edge(c,e,4).
edge(c,f,1).
edge(d,h,3).
edge(e,h,7).
edge(f,g,2).
edge(g,h,1).

path(X,Y,M,[Y]) :- edge(X,Y,M).
path(X,Y,P,[Z|T]) :- edge(X,Z,M),path(Z,Y,N,T),
            P is M+N.

pravilo(X,Y,Z) :-  assert(min(100)),assert(minpath([])),!,
                path(X,Y,K,PATH1),
                (min(Z),K<Z,
                retract(min(Z));assert(min(K))),
                minpath(Q),retract(minpath(Q)),
                assert(minpath([X|PATH1])),
                fail.

?- pravilo(a,h,X);
    write("Minimal Path:"),
    minpath(PATH),
    write(PATH),
    nl,
    write("Path weight:"),
    min(Z),
    write(Z).

    InformationsquelleAutor mireca i fori i julkata

  2. 0

    Ohne zu wissen, was das eigentliche problem ist, kann ich zumindest empfehlen, die vielleicht kürzeste() und Pfad() sollte eine maximum-length-parameter, die Kurzschlüsse der Suche.

    Auch, kürzeste() nicht den kürzesten Weg zu finden. So findet Sie für jedes mögliche paar von Pfaden, die die kürzeste von jedem paar.

    ok, ich sehe, könnten Sie vorschlagen, eine Lösung für dieses problem bitte, danke ! weil ich versuche, aber keine Lösung!!!!!

    InformationsquelleAutor Marcelo Cantos

Schreibe einen Kommentar