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

Question

Я пытаюсь решить эту проблему, и я уже прочитал этот ответ, но моя проблема с циклом 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 зависает.

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

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

Редактировать:

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

ребро (1,2).
край (1,4):- неверно.
край (1,3):- неверно.
край (2,3):- неверно.
край (2,5):- неверно.
край (3,4):- неверно.
край (3,5):- неверно.
край (4,5):- неверно.

путь (A,B, Результат, Длина): -
    путь (A,B, [], Result, Length), false.

путь (A, B, _, [e(A,B)], 1):- неверно,
    край (A, B).
путь (A,B, Посещенный, [e(A,X)| Путь], Длина): -
    край (A, X),
    \+ участник (X, посетил),
    длина (путь, L), ложь,
    Длина L + 1,
    путь (X, B, [A| Посещенный], Путь, _).

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

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

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

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

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

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

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

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

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

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