Найти путь и его длину между узлами в графе

Question

Я пытаюсь решить эту проблему, и я уже прочитал ответ this, но моя проблема связана с циклом infinte, даже если я использовал список посещенных узлов.

Давайте посмотрим, мои две попытки:

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 замерзает.

• Что я должен определить как базовый корпус?
• Почему второй цикл реализации, если это так, даже если я использовал список посещенных узлов и diff(), чтобы избежать объединения, возвращайтесь туда и обратно? Я ошибочно назвал имя функции.

Я хотел бы избавиться от длины/2 использования. Спасибо.

Edit:

Итак, я понял, что это должно быть уборщик способом сделать это, даже если бы я хотел что-то более похожее на второй вариант осуществления, который будет легче преобразовать в кратчайших проблемах пути решатель, так как это будет всего лишь min {pathLengths} от первого вызова 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. 
% 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

Причина, как path/4 и path2/4 выставить подобное поведение не-терминации происходит потому, что оба используют тот же самый вспомогательный предикат path/5. Вы, вероятно, имел в виду path2/5 вместо:

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

Может быть, во-первых, давайте посмотрим, почему ваши path/4 петли определения. Чтобы увидеть это, я введу цели false в вашу программу. Эти цели уменьшат количество выводов. Когда оставшийся фрагмент все еще петли, мы можем быть уверены, что видим часть, которая несет ответственность за неисполнение. После некоторых экспериментов я нашел следующий фрагмент, называемый 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, _). 

Поэтому в основном это использование length/2 предиката. Пока длина пути не фиксирована, этот фрагмент не заканчивается. Таким образом, для запроса

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

Path не ограничен по длине и, таким образом, length/2 найти бесконечное множество решений - и при этом не прекращается.

Но, в конце концов, почему вы все равно хотите знать длину? Аргумент path описывает это уже неявно.

Для вашего определения path/4,5 считают, что запрос

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

следует производить в ответ. Должно ли Path = [1] быть решением? Это вопрос о точном определении пути/ходьбы. Думаю, так и должно быть.

Для получения общего решения обратитесь к this answer. С его помощью можно определить предикаты, которые вас интересуют, как так:

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

Но я не хотел бы добавить дополнительный аргумент о длине пути. Вы можете добавить эту информацию позже в любое время.