Пролог: Удалить круг из графоподобной задачи

Question

У меня есть следующая пролог-программа, в которой я хочу перейти из положения a в положение d.Мы можем сделать это, следуя пути: a-> b-> c-> d.Другой путь: a-> b-> c-> b-> c-> d и т. Д. Как убрать этот «кружащий» путь?Я пытался удалить его, используя «not (member (from_to (X, _), Z))», но, похоже, это не сработало.

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

move(X,Y,Z) :- from_to(X,Y), X \= Y, 
               Z = [from_to(X,Y)].      
move(X,Y,Z) :- from_to(X,K), K \= Y, move(K,Y,Z1), 
               Z = [from_to(X,K)|Z1],   
               not(member(from_to(X,_),Z)).

(если вы удалите строку 'not (member (from_to (X, _), Z)) 'программа работает нормально, но выводит обходные пути)

Answer 1

Здесь лучше использовать аккумулятор : переменная, которую вы обновляете посредством рекурсивных вызовов и, таким образом, содержат своего рода «память». Здесь аккумулятор может хранить список узлов, которые мы посетили. Чтобы перейти к новому узлу, этот узел должен , а не быть в списке.

Итак, мы определяем предикат move/4 вместо move/3, с:

move(X,Y,Z) :-
    move(X, Y, Z, [X]).

Теперь мы можем определить предикат move(S, D, Path, Visited), используя два правила:

1. в случае, если S и D совпадают, мы закончили, независимо от того, что является Visited, мы объединяем Path с [D]; и
2. в противном случае мы «дойдем» до другого узла N через предикат from_to/2, убедитесь, что он не является членом Visited, затем мы сделаем рекурсивный вызов, где мы добавляем S к N посещенным узлам. Мы добавляем X к результату рекурсии Z.

Как например:

move(S, S, [S], _).
move(S, D, [S|Z], Visited) :-
    from_to(S, N),
    \+ member(N, Visited),
    move(N, D, Z, [N|Visited]).

Для вашего примера графика:

затем генерирует:

?- move(a, d, Z).
Z = [a, b, c, d] ;
false.

?- move(a, D, Z).
D = a,
Z = [a] ;
D = b,
Z = [a, b] ;
D = c,
Z = [a, b, c] ;
D = d,
Z = [a, b, c, d] ;
false.

?- move(A, d, Z).
A = d,
Z = [d] ;
A = a,
Z = [a, b, c, d] ;
A = b,
Z = [b, c, d] ;
A = c,
Z = [c, d] ;
false.

?- move(A, D, Z).
A = D,
Z = [D] ;
A = a,
D = b,
Z = [a, b] ;
A = a,
D = c,
Z = [a, b, c] ;
A = a,
D = d,
Z = [a, b, c, d] ;
A = b,
D = c,
Z = [b, c] ;
A = b,
D = d,
Z = [b, c, d] ;
A = c,
D = d,
Z = [c, d] ;
A = d,
D = c,
Z = [d, c] ;
A = d,
D = b,
Z = [d, c, b] ;
A = c,
D = b,
Z = [c, b] ;
false.

Если узел не «связан с собой», как, например, у нас нет пути от a до a, например, мы можем реализовать move как:

move(S, D, [S|Z], V) :-
    from_to(S, N),
    \+ member(N, V),
    move2(N, D, Z, [N|V]).

move2(S, S, [S], _).
move2(N, D, [S|Z], V) :-
    move(N, D, Z, V).