4

我正在阅读Thinking as Computation一书，并将代码编写为第 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指的是Lin的长度plan(L)（例如Nquery 时为 4 plan([M1, M2, M3, M4])）但它不起作用。

有什么解决办法吗？

4

1 回答 1

3

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

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

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

实际上，您找到了一个计划，但随后一切都陷入了循环。就推论的数量而言，您有无限多个1。

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

这就是我想出的：

?- 长度（L，4），平面（L）。

计划（左）：-
   初始状态（I），
   目标状态（G），假，
   可达（I，L，G）。

初始状态（[]）。

目标状态（S）：-
   has_bananas(S)，假。

has_bananas([grab | S]) :- false。
has_bananas([_ | S]) :-
   has_bananas(S)，假。

程序的这个片段（称为）单独负责不终止。如果您对它不满意，您将不得不修改剩余可见部分中的某些内容。如果不是，则没有希望删除不终止。

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

计划（左）：-
   初始状态（I），
   可达（I，L，G），
   目标状态（G）。

1）与无限相比，这是所有人的理想化，很快就会化为乌有。

于 2016-03-22T22:59:52.843 回答