Найти кратчайший путь между двумя узлами в графе в Prolog

Question

Я хочу найти кратчайший путь между двумя узлами в Prolog. я понял, как найти все пути между двумя узлами, но, к сожалению, следующий код попадет в петлю:

arc(a,b). 
arc(b,a). 
arc(b,c). 
arc(c,b). 
arc(c,d). 
arc(d,c). 

path(X,Y,[arc(X,Y)]) :- 
    arc(X,Y). 
path(X,Y,[arc(X,Z)|P]) :- 
    arc(X,Z), 
    path(Z,Y,P). 

Код ПУСК:

?- path(a,c,R). 
R = [arc(a, b), arc(b, c)] ; 
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, c)] ; 
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, a), arc(a, b), arc(b, c)] 
.... 

Итак, мой вопрос: Как получить все пути без цикла бесконечно?

в конце дня, я получу длину списка и найду минимум.

Пожалуйста, если возможно, дайте решения, которые являются ISO Prolog.

Примечание: здесь обновленный код, по-прежнему у меня проблема. По-видимому, предикат-член не работает при проверке факта, а не атома.

xxx([]). 

path(X,Y,[arc(X,Y)]) :- 
    arc(X,Y). 
path(X,Y,[arc(X,Z)|P]) :- 
     arc(X,Z) 
     ,xxx(L) 
     ,member(arc(X,Z),L)-> 
      !; 
      (member(arc(Z,X),L)-> 
       !; 
       (append(L,[arc(X,Z)],R),retract(xxx(_)),assert(xxx(R)),path(Z,Y,P))). 

и мой член сказуемое:

member(X,[X|T]). 
member(X,[H|T]) :- member(X,T). 

Спасибо.

Answer 1

Вы можете посмотреть оператор вырезания «!», Когда вам нужно только одно решение.

Чтобы избежать попадания в бесконечные циклы, вы должны использовать список аккумуляторов, в котором хранятся уже посещенные узлы.

Answer 2

Мы используем meta-predicatepath/4 в сочетании с определением arc/2, что вы дали:

?- path(arc,Path,From,To). 
    From = To  , Path = [To] 
; From = a, To = b, Path = [a,b] 
; From = a, To = c, Path = [a,b,c] 
; From = a, To = d, Path = [a,b,c,d] 
; From = b, To = a, Path = [b,a] 
; From = b, To = c, Path = [b,c] 
; From = b, To = d, Path = [b,c,d] 
; From = c, To = b, Path = [c,b] 
; From = c, To = a, Path = [c,b,a] 
; From = c, To = d, Path = [c,d] 
; From = d, To = c, Path = [d,c] 
; From = d, To = b, Path = [d,c,b] 
; From = d, To = a, Path = [d,c,b,a] 
; false. 

Определение path/4 исключает все циклы.

Чтобы найти самые короткие дорожки мы необходимо посмотреть все решения!

Чтобы показать это на самом деле так, давайте расширить определение arc/2 так:

arc(a,b). 
arc(b,a). 
arc(b,c). 
arc(a,c).    % (new) 
arc(b,d).    % (new) 
arc(c,b). 
arc(c,d). 
arc(d,c). 

Допустим, мы хотим, чтобы «получить все кратчайшие пути от a до d», поэтому мы делаем запрос:

?- path(arc,Path,a,d). 
    Path = [a,b,c,d] 
; Path = [a,b,d]  % shortest path #1 
; Path = [a,c,b,d] 
; Path = [a,c,d]  % shortest path #2 
; false. 

В вышеуказанном запросе две различные Самые короткие маршруты от a до d.

Для получения обоих мы должны смотреть на все пути --- или использовать умнее meta-predicate (слева как домашнее задание).