Найти все пути для отношения, не зная узлов Пролог

Question

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

• Rel - отношение,
• S - исходный узел (первый),
• T - целевой узел (последний),
• [S | Cons] - путь,
• N - длина

    graph(Rel, S, T, [S|Cons], N) :-
       call(Rel, S, X),
       (X = T; graph(Rel, X, T, [X|Cons], N)).

Когда я проверяю его с помощью...

graph(myRelation, _, _, _, _), false.

Это просто бесконечные петли.Я предполагаю, что это потому, что у меня нет никаких переменных терминов, кроме отношения, но я думал, что когда я использую call, он назначит X, чтобы я мог заполнить пути ([S | Cons]) таким образом.

Answer 1

Вы здесь определили предикат, который будет вызываться каждый раз сам (если не произойдет сбой call(Rel, S, X), но даже тогда нет способа «получить» результат), вам необходимо условие для остановки.

Это условие, когда источник S и цель T совпадают, в этом случае мы возвращаем в качестве пути список, содержащий S, а также N=0:

graph(_, S, S, [S], 0).

Кроме того, в рекурсивном случае мы должны правильно вести бухгалтерию с помощью N и «пути»:

graph(Rel, S, T, [S|Rest], N) :-
    call(Rel, S, X),
    N1 #= N-1,
    graph(Rel, X, T, Rest, N1).

, так что в полном объеме получаем:

:- use_module(library(clpfd)).

graph(_, S, S, [S], 0).
graph(Rel, S, T, [S|Rest], N) :-
    N #> 0,
    call(Rel, S, X),
    N1 #= N-1,
    graph(Rel, X, T, Rest, N1).