2

所以我试图使用递归方法来找到两个人之间的路径。这是快速背景：我定义了一些事实in(X,Y)。那个节目谁是相关的，即。in(person1,project1), , in(person2,project1), 等等。现在任何两个人如果他们在同一个项目中，或者他们之间有一个人的链接路径，他们就是相关的。例如 p1 在 A 上工作 p2 在 A 和 B 上工作，p3 在 B 上工作，因此有一条从 p1 到 p3 通过 p2 的路径。这些路径可以是任意长度。

我正在尝试以递归方式解决这个问题（看不到任何其他方式），但是有一个烦人的问题：

related(A,B) :-
        in(A,X),
        in(B,X),
        not(A=B).

chain(A,B) :-
        related(A,B).
chain(A,B) :-
        related(A,Y),       
        chain(Y,B).

问题是路径可以重演。它可以从 p1 到 p2 无限次返回 p1。一个人在路径上的次数不应超过 1 次。

我试图用我添加的列表来解决这个问题。如果某人已在列表中，则无法再次添加：

related(A,B,L) :-
        in(A,X),
        in(B,X),not(A=B).

chain(A,B,L) :-
        related(A,B,L).
chain(A,B,L) :-
        related(A,Y,L),
        not(member(Y,L)),
        append(L,[Y],Q),
        chain(Y,B,Q).

它有点工作，但导致了大量随机错误，重复一些人多次，有些人只重复一次，然后失败。这种方法看起来对吗？我完全使用列表错误吗？

谢谢你。

4

3 回答 3

0

第一次改进。您是在寻找所有关系链还是要检查是否存在一个关系链？在第一种情况下，添加一个切口。

chain(A,B) :-
        related(A,B), !.
chain(A,B) :-
        related(A,Y),       
        chain(Y,B).

在第二种情况下，Prolog 完全按照它的要求去做，那就是找到所有可能的链。

请发布导致问题的查询，以便我们可以共同推理并改进解决方案。

于 2012-11-02T16:40:06.023 回答
0

这是基于固定点计算的另一种方法，可能效率较低但相当通用。

connected(Found, Connected) :-
    collect(Found, [], Ext),
    (   Ext == Found
    ->  Connected = Found
    ;   connected(Ext, Connected)
    ).

collect([], Set, Set).
collect([E|Es], Set, Fix) :-
    extend(E, Set, Ext),
    collect(Es, Ext, Fix).

extend(E, Set, Ext) :-
    directly(E, DirectConn),
    ord_union(DirectConn, Set, Ext).

directly(A, DirectConn) :-
    setof(B, P^(in(A, P), in(B, P)), DirectConn).

我们必须用一个排序列表调用 connected(Found, Connected) ，它会循环直到集合不能被扩展。例如，有了这个测试数据

in(anna,  project1).
in(bob,   project1).
in(bob,   project2).
in(chris, project2).
in(dan,   project3).

?- connected([bob],L).
L = [anna, bob, chris].

?- connected([dan],L).
L = [dan].

我故意允许直接/2 获得身份，即

?- directly(X,Y).
X = anna,
Y = [anna, bob] ;
...
X = dan,
Y = [dan].
于 2012-11-02T23:38:07.470 回答
0

我想我从来都不够清楚，但我最终自己解决了这个问题。我把代码放在下面。

真正重要的是一个有效的 notchain 谓词，然后确保我正确地执行了附加。我还创建了一个 notsame 谓词来替换 not(A=B)。代码如下。大多数答案是确保在列表中附加的内容周围有 []。在附加的内容周围没有正确的 [] 会导致错误。

非链（X，L）：-

成员（X，L），！，失败。

非链（X，L）。

进而：

链（A，B，L）：-

相关（A，B），追加（L，[A]，Q），追加（Q，[B]，Z），写入（最终），writeln（Z）。

链（A，B，L）：- notchain（A，L），附加（L，[A]，Q），相关（A，Y），链（Y，B，Q）。

这用于相关：

不一样（A，B）：-（
A = B），！，失败。

不相同（A，B）。

于 2012-11-03T20:39:03.973 回答