prolog - 如何使用列表记录从 A 到 B 的路径？

Question

如果我有一个节点为 1,2,...,n 的地图，我想知道是否可以从n1到n2，我可以使用以下代码：

path(1,2).
path(3,5).
.....

get_to(A,B) :- path(A,B).
get_to(A,B) :- path(A,C),get_to(C,B).

但是如何记录从A到的路径B并显示它呢？

Answer 1

首先，让我们正确理解术语：节点（通常称为顶点）之间的直接连接称为边。整个路径称为路径。这是第一次尝试：

path(A,B,[A,B]) :- edge(A,B).
path(A,C,[A,B|Vs]) :- edge(A,B), path(B,C,[B|Vs]).

请注意，该列表现在可用于确定所有固定长度的路径。

?-length(P, 10), path(A,B, P).

甚至所有路径，按长度排序：

?- length(P, N), path(A,B, P).

这种普遍性的代价是最后一个查询不会终止。有一些方法可以解决这个问题，但它们不是直截了当的。

Answer 2

那么你可以使用一个累加器：

get_to(A,B,L) :-
    get_to(A,B,[A],L).

get_to(A,B,L,L2) :-
    path(A,B),
    append(L,[B],L2).
get_to(A,B,L,L3) :-
    path(A,C),
    append(L,[C],L2),
    get_to(C,B,L2,L3).

whereL是存储路径中节点的数组。

如果图表如下所示：

path(1,2).
path(1,3).
path(3,4).
path(4,6).
path(6,5).
path(5,7).

这将导致：

?- get_to(1,7,L).
L = [1, 3, 4, 6, 5, 7]

然而，这种方法的一个问题是该append操作需要线性时间，从而导致显着的开销。但是，您可以尝试反向构建路径...

get_to(A,B,L) :-
    get_to(A,B,[B],L).

get_to(A,B,L,[A|L]) :-
    path(A,B).
get_to(A,B,L,L2) :-
    path(C,B),
    get_to(A,C,[C|L],L2).

结果 - 显然 - 在同一条路径上，但要快得多......

?- get_to(1,7,L).
L = [1, 3, 4, 6, 5, 7] .