모든 경로와 그래프의 최단 경로 검색 - 프롤로그

Question

터보 프롤로그에서 모든 경로를 검색하고 두 노드 사이의 그래프에서 최단 경로를 검색하는 데 문제가 있습니다. 내가 가지고있는 문제는 노드가 목록에 아닌지

  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. 

(정확히 멤버의 절에서) 테스트하는 것입니다 이것은 내 코드입니다 : 모른 채

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. 

Answer 1

무엇 실제 문제는 적어도 shortest() 및 path()가 검색을 단락시키는 최대 길이 매개 변수를 취해야한다고 제안 할 수 있습니다.

또한 shortest()는 최단 경로를 찾지 못합니다. 가능한 모든 경로 쌍에 대해 각 쌍 중 가장 짧은 경로를 찾습니다.

Answer 2

이 가장 짧은 경로를 보여주고 그 무게입니다 :

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