猴子和香蕉在思考作为计算

Question

我正在阅读《Thinking as Computing》一书，并将代码写成第9.4章：

plan(L) :-
   initial_state(I),
   goal_state(G),
   reachable(I, L, G).
initial_state([]).
legal_move(S, A, [A | S]) :-
    poss(A, S).
goal_state(S) :-
    has_bananas(S).
reachable(S, [], S).
reachable(S1, [M | L], S3) :-
    legal_move(S1, M, S2),
    reachable(S2, L, S3).
location(box, loc3, []).
location(box, L, [push(L) | _]).
location(box, L, [A | S]) :-
    + A = push(L),
    location(box, L, S).
location(bananas, loc1, _).
location(monkey, loc2, []).
location(monkey, L, [push(L) | _]).
location(monkey, L, [go(L) | _]).
location(monkey, L, [climb_off | S]) :-
    location(monkey, L, S).
location(monkey, L, [A | S]) :-
    + A = push(_), + A = go(_), location(monkey, L, S).
on_box([climb_on | _]).
on_box([A | S]) :- + A = climb_off, on_box(S).
has_bananas([grab | S]) .
has_bananas([_ | S]) :- has_bananas(S).
poss(climb_off, S) :- on_box(S).
poss(go(_), S) :- + on_box(S).
poss(grab, S) :-
    on_box(S), location(box, L, S), location(bananas, L, S).
poss(push(_), S) :- poss(climb_on, S).
poss(climb_on, S) :-
    + on_box(S), location(box, L, S), location(monkey, L, S).

但我发现该程序从未停止过...打印堆栈信息后，我发现goal_state生成无限长度的列表。我试图限制列表的长度has_banana

has_bananas([grab | S], N) :- length(S, NS), NS is N - 1.
has_bananas([_ | S], N) :- + N = 0, has_bananas(S, N - 1).

N是指plan(L)中L的长度（例如 N查询时为 4 plan([M1, M2, M3, M4]) ） 但它不起作用。

有什么解决办法吗？

Answer 1

在Prolog中，非终止是一项非常棘手的业务，特别是如果你习惯了不同的更面向命令的编程语言。尝试逐步了解问题非常诱人。但很多时候，这在Prolog中无处可去。

相反，请考虑修改程序。只是一点点。并且以一种易于预测修改效果的方式。例如，将false目标添加到您的计划中。它们的影响会是什么？好吧，不多：这些目标将减少推论的数量。也许，它们也会减少找到的解决方案集。但就目前而言，让我们坚持推论的数量。您遇到过以下情况，其中程序不会因以下情况而终止：

?- length(L, 4), plan(L).

事实上，你找到了一个计划，但随后一切都进入了一个循环。就推论的数量而言，你有无限多个¹。

为了本地化负责部分，让我们在您的程序中添加一些false目标。将它们相加，使得推理的数量仍然是无限的。

这就是我想出的：

？- 长度（L， 4）， 平面图（L）.计划（L） ：-   initial_state（I），   goal_state（G）， 假，   可到达（I、L、G）。initial_state（[]）。goal_state（S） ：-   has_bananas（S），假。has_bananas（[抓取 |S]） ：- 假。has_bananas（[_ |S]) :-   has_bananas（S），假。

程序的这个片段（称为故障片）单独负责不终止。如果您对此不满意，则必须修改剩余可见部分中的某些内容。否则，就没有希望取消不终止。

我的建议是将计划中两个目标的顺序更改为：

计划（L） ：-   initial_state（I），   可到达（I， L， G），   goal_state（G）.

---

1）这是一个理想化，因为与无限相比，所有人都会在短时间内崩溃成尘土。