在递归中使用Prolog列表

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

我试图递归解决这个（没有看到任何其他方式），但有一个恼人的问题：

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无尽的时代。一个人不应该在路上超过一次。

我试图解决这个问题，我添加了一个列表。如果一个人已经在列表中，他们不能再次添加：

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

它有点工作，但造成一吨的随机误差，重复一些人多次，有的只有一次，然后失败。这种方法看起来不错吗？我完全使用列表错误吗？

谢谢。

来源

2012-11-02 Mike

我想我从来没有完全清楚就够了，但我结束了这个解决我自己。我把下面的代码。

真正重要的是一个有效的notchain谓词，然后确保我正确地添加了附件。我还创建了一个不同的谓词来替换不是（A = B）。代码如下。大部分答案都是确保在列表中附加了什么。如果没有正确的[]附加内容会导致错误。

notchain（X，L）： - ！

成员（X，L），失败。

notchain（X，L）。

然后：

链（A，B，L）： -

相关（A，B），附加（L，[A]，Q），追加（Q，[B]，Z）， write（final），writeln（Z）。

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

这在相关的使用：

notsame（A，B）： -
（A = B），失败。（A，B）。

来源

2012-11-03 20:39:03 Mike

第一次改进。你在寻找所有的关系链吗？还是你想要检查是否有一个关系链？在第一种情况下添加一个剪辑。

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

在第二种情况下，Prolog的不正是它的要求做的，就是找到所有可能链。

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

来源

2012-11-02 16:40:06 NotAUser

所有的链都是优选的。真正的问题是，一个连锁店可以多次拥有同一个人，需要有一种方法来防止这种情况发生。稍后我会在家时发布样本输出。我知道如何在Java，C，C＃等中轻松完成这个任务，但是prolog正在抛出一个循环。 – Mike

这是一种替代方法，可能效率较低，但相当普遍，基于定点计算。

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

我们必须调用连接（发现，连接）与排序列表，它一直循环到集不能扩展。例如，对于本次测试数据

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获取Identity，即

?- directly(X,Y). 
X = anna, 
Y = [anna, bob] ; 
... 
X = dan, 
Y = [dan].

来源

2012-11-02 23:38:07 CapelliC

在递归中使用Prolog列表

回答

相关问题