prolog - グラフ内のノード間のパスとその長さを見つける

Question

私はこの問題を解決しようとしており、すでにこの回答を読んでいますが、私の問題は、訪問したノードリストを使用した場合でも無限ループにあります。

私の2つの試みを見てみましょう：

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).


% ------ simple path finding in a directed graph

% -----  simple exploration

path0(A,B, Result) :-
    path0(A, B, [], Result).

path0(A, B, _, [e(A,B)]):- 
    edge(A,B).    
path0(A, B, Visited, [e(A,X)|Path]):-
    edge(A, X), dif(X, B),
    \+ member(X, Visited),
    path0(X, B, [A|Visited], Path ).    


%---- 1. exploration and length    

path(A, B, _, [e(A,B)], 1):- 
    edge(A,B).    
path(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),
    \+ member(X, Visited),
    length(Path, L),        % ERR: Path refers to a open list
    Length is L + 1,
    path(X, B, [A|Visited], Path, _).

% --- 2. not working

path2(A,B, Result, Length) :-
    path2(A, B, [], Result, Length).

path2(A, B, [], [e(A,B)], 1):- 
    edge(A,B).    
path2(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X), dif(X, B),
    \+ member(X, Visited),
    path2(X, B, [A|Visited], Path, Len),
    Length is Len + 1.

同様の答えが得られます。つまり、

 ?- path(1,3, Path, Length).
Path = [e(1, 3)],
Length = 1 ;
Path = [e(1, 2), e(2, 3)],
Length = 2 ;

そして、Swi-Prolog IDE がフリーズします。

• 基本ケースとして何を定義すればよいですか?
• 訪問したノードリストと dif() を使用して統合を確実に回避したとしても、2番目の実装がループするのはなぜですか? 関数名を間違えました。

length/2 の使用をなくしたいと思います。ありがとう。

編集：

したがって、最短経路の問題ソルバーで変換しやすい2番目の実装に似たものが必要な場合でも、これがよりクリーンな方法であることがわかりました。 path3/4 の最初の呼び出しから。

% ---- 3. working    
%   
min(A,B,A):- A =< B, !.       % for future use (shortest path)
min(_,B,B).

path3(From, To, Path, Len):-    
    path0(From, To, [], Path),
    length(Path, Len).
    %min(Len, MinLength, ?)

---

そして、これは 2 番目の実装パス 2 の修正版です。

% --- 2. 
% errors: 1. in base case I have to return Visited trough _, 
%             I can't pass a void list []
%         2. dif(X,B) is unuseful since base case it's the first clause

path2(A,B, Result, Length) :-
    path2(A, B, [], Result, Length).

path2(A, B, _, [e(A,B)], 1):-      % If an edge is found
    edge(A,B).    
path2(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),  
    %tab(1),write(A),write('-'),write(X),
    \+ member(X, Visited),
    %tab(1),write([A|Visited]),write(' visited'),nl,
    path2(X, B, [A|Visited], Path, Len),
    Length is Len + 1.