0

我一直在尝试解决 Prolog 中的寻路问题。谓词在哪里

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


edge(X,Y) :- edge(X,Z), edge(Z,Y).
然后是我编译并运行查询时 的规则| ?- edge(a,X)。它显示 Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ) 然后我搜索了解决方案，发现在我们的规则中包含atom(x).,atom(y).可以解决堆栈溢出问题。即新规则是

edge(X,Y) :- atom(X), atom(Y), edge(X,,Z), edge(Z,Y).是的，它确实解决了堆栈溢出问题。但是，我想知道这个 (atom/1) 谓词究竟是如何解决我的问题的？它对我们的变量有什么作用X,Y来解决 StackOverflow 问题？我是 Prolog 的新手，任何帮助将不胜感激，谢谢。:)

4

1 回答 1

2

首先在命名上，edge/2名称并不能很好地描述您的谓词。您可能真的想要path/2由一个或多个边缘组成。

atom/1真的能解决你的问题吗？换句话说，edge(X, Y)现在真的为查询提供了所有正确的解决方案吗？所做atom/1的只是确保它的参数是一个原子，所以它不能是一个未绑定的变量。所以edge(X, Y)没有提供所有正确的解决方案。它只产生那些你有直接事实的解决方案，因为edge(X, Y)当前定义的谓词总是失败，要么X或未Y绑定。

| ?- edge(a, Y).

Y = b ? ;

Y = c ? ;

no

Y = d例如，解决方案在哪里？edge(X, Y)仅选择您的edge/2事实中给出的解决方案，但没有包含多个连接边的解决方案。

您最初的问题是由于无限递归，这是edge/2不必要地调用自身的结果。命名在这里实际上很重要，因为它使逻辑更加精确和正确。我们可以说这edge(X, Y)意味着X和Y形成一条边（X和Y直接相连）。我们可以说这path(X, Y)意味着有一条路径from Xto Yvia one or more edges。换句话说，从 x 到 y 的路径可以是从 x 到 y 的边，也可以是从 x 到 z 的边和从z 到 y的路径。

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

现在我们得到：

| ?- path(a, X).

X = b ? a

X = c

X = d

X = e

X = f

X = g

X = d

X = e

X = f

X = g

(1 ms) no
| ?-

有重复，因为可能有多种方式从a到e例如。如果您包含一个显示遍历路径的参数，这将变得很明显。

然而，这个解决方案并不是故事的结局。您当前的事实是没有“迂回”路径（如果遵循最终会重新访问同一节点的路径）。为了处理这个问题，您需要一个谓词参数来跟踪您已经遍历了哪些节点/边并避免再次遍历它们。

于 2017-10-10T10:59:35.060 回答