Finden Pfad und seine Länge zwischen den Knoten in einem Diagramm

Question

Ich versuche, dieses Problem zu lösen, und ich habe bereits this Antwort gelesen, aber mein Problem ist mit Infinet-Schleife, auch wenn ich eine Liste der besuchten Knoten verwendet habe.

Lassen Sie uns meine zwei Versuche sehen:

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. 

Welche mir ähnliche Antworten geben, d.h .:

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

Und dann friert der Swi-Prolog IDE.

• Was sollte ich als Basisfall definieren?
• Warum ist die zweite Implementierung Schleife, wenn es der Fall ist, auch wenn ich die Liste der besuchten Knoten verwendet und die dif() um sicher zu sein, zu vermeiden, gehen Sie hin und her? Ich habe den Funktionsnamen falsch eingegeben.

Ich möchte die Länge/2 Verwendung loswerden. Danke.

Edit:

Also, habe ich herausgefunden dies der Reiniger Weg sein sollte, es zu tun, auch wenn ich etwas ähnlich die zweite Implementierung möchte die einfacher wäre, in einem kürzesten Weg Problem zu transformieren Solver, da es vom ersten Aufruf von path3/4 nur eine min {pathLengths} wäre.

% ---- 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, ?) 

---

Und dies ist die korrigierte Version der zweiten Implementierung path2:

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

Answer 1

Der Grund, warum beide path/4 und path2/4 ähnliches Verhalten nicht-Kündigung aussetzen, weil sowohl die gleiche Hilfs verwenden Prädikat path/5. Sie meinten wahrscheinlich path2/5 statt:

path2(A,B, Result, Length) :- 
    path(A, B, [], Result, Length). 
% ^^^^ replace by path2 

Vielleicht lassen Sie uns zuerst sehen, warum Ihre path/4 Definition Loops. Um dies zu sehen, werde ich Ziele false in Ihr Programm einfügen. Diese Ziele werden die Anzahl der Schlussfolgerungen reduzieren. Wenn das verbleibende Fragment noch schleift, können wir sicher sein, dass wir einen Teil sehen, der für die Nicht-Beendigung verantwortlich ist. Nach einigen Experimenten fand ich das folgende Fragment, eine so genannte failure-slice:

 
edge(1,2). 
edge(1,4) :- false. 
edge(1,3) :- false. 
edge(2,3) :- false. 
edge(2,5) :- false. 
edge(3,4) :- false. 
edge(3,5) :- false. 
edge(4,5) :- false. 

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

path(A, B, _, [e(A,B)], 1):- false, 
    edge(A,B). 
path(A, B, Visited, [e(A,X)|Path], Length):- 
    edge(A, X), 
    \+ member(X, Visited), 
    length(Path, L), false, 
    Length is L + 1, 
    path(X, B, [A|Visited], Path, _). 

So im Wesentlichen es die Verwendung des length/2 Prädikat ist. Solange die Länge des Pfades nicht festgelegt ist, wird dieses Fragment nicht beendet. Also für die Abfrage

?- path(1, 3, Path, N). 

Die Path ist in seiner Länge nicht begrenzt und somit length/2 wird unendlich viele Lösungen finden - und damit nicht beendet wird.

Aber warum wollen Sie die Länge trotzdem wissen? Das Pfadargument beschreibt es bereits implizit.path/4,5

Für Ihre Definition überlegen, was die Abfrage

?- path(1, X, Path, N). 

als Antwort produzieren sollte. Sollte Path = [1] auch eine Lösung sein? Es ist ein bisschen eine Frage der genauen Definition eines Weges. Ich denke es sollte.

Eine allgemeine Lösung finden Sie unter this answer. Mit ihm können Sie die Prädikate definieren, die Sie interessiert sind, in etwa so:

yourpath(A,B, Path, N) :- 
    path(edge, Path, A,B), 
    length(Path, N). 

Aber ich würde lieber nicht das zusätzliche Argument über die Länge des Weges hinzuzufügen. Sie können diese Informationen später jederzeit hinzufügen.