search - block 世界问题搜索用完堆栈空间

Question

我有以下代码:

move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)).
move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))).

move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)).
move(state(X, on(Y, NewY), OldZ), state(X, NewY, on(Y, OldZ))).

move(state(OldX, Y, on(Z, NewZ)), state(on(Z, OldX), Y, NewZ)).
move(state(X, OldY, on(Z, NewZ)), state(X, on(Z, OldY), NewZ)).

path(X,X,[]).
path(X,Y,[Z|ZS]) :- 
    move(X,Z),
    path(Z,Y,ZS).

move 为我们提供了您可以使用的可能移动方式，而 path 为我们提供了您必须从 X 到 Y 的路径。

问题是谓词 path 没有按我想要的那样工作，即，如果我键入 path(state(on(c,on(b,on(a,void ))), void, void), state(void, void, on(c,on(a,on(b,void)))), X). 我得到错误:超出本地堆栈，但是我希望 X 是

X=[state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)].

那我做错了什么？

Answer 1

对于第一次测试，无需重写您的代码。自 1972 年夏天以来就没有了¹。相反，您可以谨慎地重新表述您的查询。

与其向您的 Prolog 系统要求相当多的独创性，不如要求一个具体的答案，让我们将您的答案表述为一个查询!我尝试了一下，发现其中有一些讨厌的语法错误，之后，查询失败了..

但还有更便宜的方法!我们只限制列表的长度，让 Prolog 填充其余部分。这份 list 应该有多长？我们不知道(也就是说，我不知道)。好的，让我们尝试任何长度!这也是 Prolog 喜欢的东西。很简单:

?- length(X,N),  % new
   path(  state(on(c,on(b,on(a,void))), void, void),
          state(void, void, on(c,on(a,on(b,void)))),
          X).
   X = [ state(on(b,on(a,void)),on(c,void),void),
         state(on(a,void),on(c,void),on(b,void)),
         state(void,on(c,void),on(a,on(b,void))),
         state(void,void,on(c,on(a,on(b,void)))) ],
   N = 4
;  ... .

看到我做了什么吗？我只是在前面加了length(X, N)。突然之间，Prolog 的回答比您预期的更短!

现在，这真的是最好的提问方式吗？毕竟，许多答案可能都是简单的循环，将一个方 block 放在一个地方然后再放回去……真的有循环吗？让我们先问一下:

... --> [] | [_], ... .?- length(X,N),   path( state(on(c,on(b,on(a,void))), void, void),         state(void, void, on(c,on(a,on(b,void)))),         X),   phrase((...,[E],...,[E],...), X).   X = ...   N = 6,   E = state(void,on(c,void),on(a,on(b,void)));  ... .

哦，是的，有!现在排除这些路径确实有意义。这是一个干净的方法:

alldifferent([]).alldifferent([X|Xs]) :-   maplist(dif(X), Xs),   alldifferent(Xs).?- alldifferent(X),   length(X,N),   path( state(on(c,on(b,on(a,void))), void, void),         state(void, void, on(c,on(a,on(b,void)))),         X).

你能用这个公式走多远？目前，我找到了一条长度为 48 ... 55 ... 的路径，它不应该是有限的吗？并且:是否有可能为这种微不足道的问题排除如此长的路径？任何蹒跚学步的 child 都可以保持较小的搜索空间……这些都是基本问题，但它们独立于编程问题本身。

或者，从另一个角度来看:X 的解决方案集非常大。那么如果我们要探索这个集合，我们应该从哪里开始呢？成为最佳解决方案意味着什么？上传到 Utube 上获得最多赞成票的那个？所以我们在这里所做的完全是不知情的搜索。您需要告知程序您有什么样的偏好。它无法合理地猜测它。好的，一种启发式方法是解决方案的术语大小。 length/2 做到了。

请注意，我不敢碰你干净的代码。是的，我可以稍微改进一下，比如使用 path/4 ，但不多。而是坚持你高度干净的风格，而是做更多的查询!这就是 Prolog 擅长的地方!

其他改进:使用列表来表示堆栈，这使状态更具吸引力。

---

<子>1 那是 Prolog 被发现/构思/交付的那一年。