时间戳

首页 > 解决方案 > 如何回答这个关于路径的序言问题？

prolog - 如何回答这个关于路径的序言问题？

问题描述

https://i.ibb.co/q0zXPGv/qe.jpg

在 Prolog 中，我们可以引入一个关于边方向的谓词来表示上图：

edge(s,a).
edge(a,b).

我们进一步介绍一个关于节点连通性的谓词：

connected(X,Y) :- edge(X,Y).
connected(X,Y) :- edge(X,Z), connected(Z,Y).

现在，我们想用一个谓词进一步扩展我们的程序，该谓词path(X,Y,P)将使用变量P来保存节点列表，这些节点构成从节点X到节点的有效路径Y。

实现路径谓词并将 Prolog 系统的答案写入以下查询：
1. ?- path(s,f,P)。
2. ?- 路径(d,c,P)。
3. ?- 路径(s,g,P)。
4. ?- 路径(s,e,P)。
路径图像

标签： prolog

解决方案

让我们检查一下我对问题的解决方案：

edge(s,a).
edge(s,f).
edge(s,e).
edge(f,e).
edge(a,b).
edge(e,d).
edge(d,a).
edge(d,c).
edge(b,c).
edge(c,g).

connected(X,Y):- edge(X,Y).
connected(X,Y):- edge(X,Z), connected(Z,Y).

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

如果路径是从节点到节点本身，则结果必须是节点。否则，如果我们可以通过某个节点 Z 从 X 到 Y，则节点 X 应该在路径中。

我真的不喜欢connected的实现，因为它迫使你不得不削减解决方案。

希望能帮助到你！以下是上述问题的答案：

?- path(s,f,P).
P = [s, f].

?- path(d,c,P).
P = [d, a, b, c].

?- path(s,g,P).
P = [s, a, b, c, g].

?- path(s,e,P).
P = [s, f, e].

推荐阅读