prolog - Prolog - 给定关系的路径查找和长度

Question

我刚开始学习 Prolog，我想更好地理解 Pathfinding。我有一些关系的例子，但是，当关系是周期性的时，我不知道如何找到关系的路径和长度。我一直在尝试创建一个记录访问过的节点的列表，但我一直收到错误消息。

下面是一些示例，以及我尝试在给定关系、源、目标、路径列表和长度的情况下查找路径）：

is_a(parallelogram, quadrilateral).
is_a(trapezoid, quadrilateral).
is_a(rhombus, parallelogram).
is_a(rectangle, parallelogram).
is_a(square, rhombus).
is_a(square, rectangle).

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

friend(alice, bob).
friend(bob, carol).
friend(carol, daniel).
friend(carol, eve).

friends(A,B) :- 
    friend(A,B); 
    friend(B,A).

transit(Rel, S, T) :- 
    call(Rel, S, X), 
    (X = T; transit(Rel, X, T)).

path_(Rel,Source,Target,Path,Len) :-
    path_(Rel,Source,Target,Path,Len,[]).

path_(Rel,Source,Target,Path,Len,Visited) :-
    transit(Rel,Source,Target),
    transit(Rel,Source,Mid),
    Mid == Target, !,
    append(Visited,[Source,Target],Path),
    length(Path,L),
    Len is L+1.

path_(Rel,Source,Target,Path,Len,Visited) :-
    transit(Rel,Source,Target),
    transit(Rel,Source,Mid),
    not(member(Mid,Visited)),
    path_(Rel,Mid,Target,Path,Len,[Source|Visited]).

以上是我的第二次尝试，但我收到所有错误。我的第一次尝试仅适用于非循环路径，例如 is_a 关系，如下所述：

path0(Rel,From,To,[From,To],2) :-
    transit(Rel,From,To),
    call(Rel, From, To).

path0(Rel,From,To,[From|Xs],Len) :-
    transit(Rel,From,X),
    call(Rel,From,X),
    path0(Rel,X,To,Xs,_),
    length(Xs, L),
    Len is L+1.

标签： prologpath-finding