3

这里我的问题是我想检查两个节点是否连接。

我的知识库是，

edge(a,b):-!.
edge(b,a):-!.
edge(a,e):-!.
edge(e,a):-!.
edge(b,c):-!.
edge(c,b):-!.
edge(b,d):-!.
edge(d,b):-!.
edge(c,e):-!.
edge(e,c):-!.
edge(d,e):-!.
edge(e,d):-!.
edge(a,f):-!.
edge(f,a):-!.

isConnected(X,X):-!.
isConnected(X,Y):-edge(X,Y),!.
isConnected(X,Z):-not(edge(X,Y)),edge(X,Y),isConnected(Y,Z),!.
isConnected(X,Z):not(edge(X,Y)),edge(X,Z),not(isConnected(Y,Z)),isConnected(Z,Y),!.
4

1 回答 1

2

哇那里。这是很多削减。剪切有时在 Prolog 中有助于修剪不必要的答案，但是当你有这样的事实时：

edge(a, b).

把它写成这样绝对没有任何收获：

edge(a, b) :- !.

毕竟，那里没有选择点，因为那里没有变量，也没有替代解决方案。所以首先，让我们通过删除所有这些削减来修正你的事实。

接下来让我们看看 isConnected 是怎么说的。让我们用英语大声朗读它，看看它是否有意义。

  1. X 连接到 X。
  2. 如果从 X 到 Y 有一条边，则 X 连接到 Y。
  3. 如果从 X 到 Y 没有边，则 X 连接到 Z，但是从 X 到 Y 有边并且 Y 连接到 Z。 (???)
  4. 如果从 X 到 Y 没有边，则 X 连接到 Z，但从 X 到 Z 有边，并且 Y 不连接到 Z 但 Z 连接到 Y。（？？？）

前两个似乎很合理。第三个似乎马上就自相矛盾了。怎么可能not(edge(X, Y))同时为真edge(X, Y)？请记住，Prolog 中的逗号表示and，而不仅仅是then。该子句的其余部分没有意义，因为这两个条件不可能同时为真。可能你的意思是这样的：如果从 X 到 Y 有一条边并且 Y 连接到 Z，则 X 连接到 Z。在 Prolog 中看起来像这样：

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

从逻辑上讲，这当然是正确的，但是对于任何类型的复杂图来说，计算起来都会非常昂贵，因为检查 X 是否连接到 Z 可能意味着检查所有相同节点的 Y 是否连接到 Z。

您的第四个子句有一个错字，:应该是:-. 更重要的是，您似乎正试图在此处补偿边缘的方向性。一个更好的地方是在第 2 步附近，提供两种情况：

isConnected(X, Y) :- edge(X, Y) ; edge(Y, X).

根据您的事实数据库，我不确定您是否真的是这个意思；您已经复制了所有事实以说明两个方向。如果事实数据库表示有向图，这可能是必要的，并且规则不应尝试反转节点。如果它代表一个无向图，那么您的谓词应该只使用这样的规则来考虑它，检查双方，并且您应该只列出每条边一次。两种方式都这样做，你是在告诉 Prolog 做一堆不必要的工作，因为它首先检查edge(a, b)，然后规则将其反转为edge(b, a)，然后移动到下一个事实edge(b, a)，然后规则将其反转为edge(a, b)，实际上检查了所有内容两次.

房间里的大象是，即使你成功地把它变成了问题的合乎逻辑的解决方案，它的效率也会低得可怕。有一些算法可以确定两件事情是否相关，这些算法可以跟踪已经看到的和没有看到的，我认为你最好实现其中之一。

于 2013-01-22T16:36:28.600 回答