在递归中使用Prolog列表 [英] Using Prolog Lists in Recursion

问题描述

因此，我尝试使用递归方法在两个人之间找到一条路径.快速背景如下: 我定义了一些事实in(X,Y).那表明谁是相关的，即. in(person1,project1)，in(person2,project1)等.现在，如果两个人彼此在同一个项目中，或者它们之间存在人与人之间的链接路径，则它们是相关的.例如，p1在A上工作p2在A和B上工作，而p3在B上工作，因此存在从p1到p3到p2的路径.这些路径可以是任意长度.

So I am trying to use a recursive method to find a path between two people. Here is the quick background: I define some facts in(X,Y). That show who is related, ie. in(person1,project1), in(person2,project1), etc etc. Now any two people are related if they were in the same project as each other, or there is a linking path of people between them. For example p1 worked on A p2 worked on A and B and p3 worked on B therefore there is a path from p1 to p3 through p2. These paths can be any length.

我正在尝试递归解决此问题(没有其他方法)，但是有一个烦人的问题:

I am trying to solve this recursively (don't see any other way), but there is an annoying problem:

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

The issue is that the path can repeat itself. It can go from p1 to p2 back to p1 endless times. A person should not be in the path more than 1 time.

我尝试使用添加到的列表来解决此问题.如果某个人已经在列表中，则无法再次添加他们:

I tried to fix this with a list that I add to. If a person is already in the list, they can't be added again:

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

虽然可以正常工作，但是却造成了许多随机错误，多次重复某些人，有些仅重复一次，然后失败.这种方法看起来正确吗?我完全使用列表错误吗?

And it sort of worked, but caused a ton of random errors, repeating some people multiple times, some only once, and then failing. Does this approach look right? Am I totally using lists wrong?

谢谢.

推荐答案

我认为我从来都不够清楚，但最终还是自己解决了这个问题.我将代码放在下面.

I think I was never perfectly clear enough, but I ended up solving this myself. I put the code below.

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

What really mattered was an effective notchain predicate and then making sure I did the appends correctly. I also created a notsame predicate to replace the not(A=B). The code is below. Most of the answer was making sure that there were [] around what was being appended to the list. Not having the correct [] around what was being appended caused errors.

notchain(X，L):-

notchain(X,L) :-

成员(X，L)，！，失败.

member(X,L),!,fail.

notchain(X，L)

notchain(X,L).

然后:

链条(A，B，L):-

chain(A,B,L) :-

related(A，B)， append(L，[A]，Q)， append(Q，[B]，Z)， write(final)，writeln(Z).

related(A,B), append(L,[A],Q), append(Q,[B],Z), write(final),writeln(Z).

链(A，B，L):- notchain(A，L)， append(L，[A]，Q)， 相关(A，Y)， 链(Y，B，Q).

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

这已用于相关内容:

notsame(A，B):-
(A = B)，！，失败.

notsame(A,B) :-
(A=B),!,fail.

notsame(A，B).

notsame(A,B).

这篇关于在递归中使用Prolog列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！