如何检查两个顶点是否连接在prolog中？

Question

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

我的知识库是，

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),!.

Answer 1

哇哦，那里。这是很大的削减。在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中的逗号意味着，而不仅仅是。子句的其余部分没有意义，因为这两个条件都不可能都是真的。也许你想说的是这样的:如果从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)，实际上对所有内容进行了两次检查。

房间里的大象是，即使你成功地把它转变成一个合乎逻辑的解决问题的方法，它也将是极其低效的。有一些算法可以用来确定两件事是否有关联，这样可以跟踪已经看到的和没有看到的东西，我认为实现其中的一种会更好。