1

我正在编写一个谓词来查找 A* 迭代的所有可能的后继状态,并将它们放在像 [(cost, state), ...] 这样的列表中,目前该列表如下:

addSuccessors(L, [], _).
addSuccessors(L, [X|T], OrigList) :- memb(OrigList, Index, X),
                                     add((X, Index), L, List2),
                                     addSuccessors(List2, T, OrigList).
addSuccessors(L, [X|[]], OrigList) :- memb(OrigList, Index, X),
                                     add((X, Index), L, L2),
                                     addSuccessors(L2, [], OrigList).

Add 将某些内容添加到列表的末尾, memb 获取列表的第(索引)个元素。我知道它们有效,当我查看底部谓词中的 L2 时,我会得到这样的结果

?- addSuccessors(X, [1500, 3670], [0, 0, 0, 1500, 3670]).
X = [] ;
[ (1500, 3), (3670, 4)]
X = [] ;
X = [_G1175] ;
[_G1175, (1500, 3), (3670, 4)]
X = [_G1175] ;
X = [_G1175, _G1181] ;
[_G1175, _G1181, (1500, 3), (3670, 4)]
X = [_G1175, _G1181] ;
...

这非常令人沮丧,因为 [(1500, 3), (3670, 4)] 列表是我在调用它之后希望 X 成为的列表​​,所以它看起来正在做我想做的事情,而不是......我想要的地方。

请问,我该如何解决这个问题?

4

2 回答 2

1

自从我在 Prolog 中编程以来已经有一段时间了,但我认为您需要将您正在构建的列表与您返回的列表分开(即添加另一个参数)。您的 [X|[]] 规则应该绑定输出变量而不是递归。

于 2010-02-01T21:19:12.750 回答
1

想想 L 实际上是如何得到它的初始值的。好吧,事实并非如此。您要做的是从头开始构建一个列表,因此您需要从一个空列表开始,而不是一个未绑定的变量。解决此问题的一种方法是编写一个包装谓词,它允许您当前的谓词充当累加器谓词。

这可能看起来像这样,其中addSuccessors_acc将包含您已经定义的子句。

addSuccessors(L, X, Y) :-
    addSuccessors_acc(L,[],X,Y).

这个想法是addSuccessors_acc谓词的第二个参数充当您的累加器,这是每个递归调用构建的列表。然后在累加器谓词的基本情况下,您只需要将累加器变量与第一个参数统一起来,即可传递最终列表。例如:

 addSuccessors_acc(L,L,_,_).

此外,正如 ergosys 指出的那样,您的第三个子句实际上可以是基本情况。由于您正在处理列表中的最后一个元素,因此无需递归 - 所做的只是将基本情况延迟一个额外的调用。

于 2010-02-03T00:38:44.483 回答