搜索图的所有路径和最短路径 - Prolog [英] search all paths and the shortest path for a graph - Prolog

问题描述

我在turbo prolog的代码中遇到问题，它在2个节点之间的图中搜索所有路径和最短路径。
我遇到的问题是测试节点是否在列表中（正好在成员的子句中）

  1 ---- b ---- 3 
 --- | --- 
 --- | ----- 
 a | 5 d 
 --- | ----- 
 --- | --- 
 2 --- | --- 4 
  -  c  -  
 
例如我们有b ---> c 
（[b，c]，5），（[b ，a，c]，3）和（[b，d，c]，7）：可能的路径。 
（[b，a，c]，3）：最短路径。 
  

这是我的代码：

<$ p









$ path $（符号，符号，列表，整数）
路径（符号，符号，列表，列表，整数）
距离（符号，列表，整数）
成员（符号，列表）
最短（符号，符号，列表） ，整数）

CLAUSES
距离（a，b，1）。
距离（a，c，2）。
距离（b，d，3）。
距离（c，d，4）。
距离（b，c，5）。
距离（b，a，1）。
距离（c，a，2）。
距离（d，b，3）。
距离（d，c，4）。
距离（c，b，5）。

成员（X，[X | T]）。
成员（X，[Y | T]）： - 成员（X，T）。

缺席（X，L）： -
会员（X，L），
！，
失败。
缺席（_，_）。
$ b $ *找到所有路径* /
path1（X，Y，L，C）： - 路径（X，Y，L，I，C）。
path（X，X，[X]，I，C）： - 缺席（X，I）。
path（X，Y，[X | R]，I，C）： -
distance（X，Z，A），
absent（Z，I），
路径（Z，Y，R，[X | I]，C1），
C = C1 + A
。
$ b $ *找出最短路径* /
最短（X，Y，L，C）： -
路径（X，Y，L，C），
路径（X，Y，L1，C1），
C< C1。

解决方案

这显示最短路径和重量： p>

  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）。 
 
路径（X，Y，M，[Y]）： - 边（X，Y，M）。 
 path（X，Y，P，[Z | T]）： - 边（X，Z，M），路径（Z，Y，N，T），
 P是M + N。 
 
 pravilo（X，Y，Z）：assert（min（100）），assert（minpath（[]）），！，
 path（X，Y，K，PATH1 ），
（min（Z），K  retract（min（Z））; assert（min（K））），
 minpath（Q），retract（minpath Q）），
 assert（minpath（[X | PATH1]）），
失败。 
 
？ -  pravilo（a，h，X）; 
 write（Minimal Path：），
 minpath（PATH），
 write（PATH），
 nl，
 write（Path weight：） 
分钟（Z），
写入（Z）。 
  

I have a problem in my code with turbo prolog which searches all paths and the shortest path in a graph between 2 nodes. The problem that i have is to test if the node is in the list or not (exactly in the clause of member)

           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.

and this is my 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.

解决方案

This shows the shortest path and it's weight:

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).

这篇关于搜索图的所有路径和最短路径 - Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！