Affe und Banane in Denken als Computation

Question

Ich lese das Buch Denken als Computation und schrieb den Code als Kapitel 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). 

Aber ich fand, dass das Programm hört nie auf ... Nach dem Drucken des Stapels Info, ich habe festgestellt, dassListen von unendlicher Länge erzeugt. Ich habe versucht, die Länge der Listen in 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). 

die N bezieht sich auf die Länge von L in plan(L) (z N 4 ist, wenn Abfrage plan([M1, M2, M3, M4])) zu beschränken, aber es funktioniert nicht.

Gibt es eine Lösung?

Answer 1

Nicht-Terminierung ist ein sehr schwieriges Geschäft in Prolog, insbesondere wenn Sie an andere Kommando-orientierte Programmiersprachen gewöhnt sind. Es ist sehr verlockend zu versuchen, das Problem Schritt für Schritt zu verstehen. Aber sehr oft führt das in Prolog zu nichts.

Betrachten Sie stattdessen ändern Sie Ihr Programm. Nur ein bisschen. Und auf eine Weise, dass es einfach ist, vorherzusagen, was die Wirkung Ihrer Modifikationen sein wird. Fügen Sie beispielsweise false Ziele in Ihr Programm ein. Was wird ihre Wirkung sein? Nun, nicht viel: Diese Ziele werden die Anzahl der Schlussfolgerungen reduzieren. Und vielleicht werden sie auch die Menge der gefundenen Lösungen reduzieren. Aber im Moment bleiben wir bei der Anzahl der Schlussfolgerungen. Sie haben einen Fall auf, wo Ihr Programm für nicht beenden:

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

In der Tat, Sie einen Plan finden, aber dann geht alles in eine Schleife. In Bezug auf die Anzahl der Inferenzen haben Sie unendlich viele .

Um den zuständigen Teil zu lokalisieren, fügen wir einige false Ziele in Ihr Programm ein. Fügen Sie sie so hinzu, dass die Anzahl der Inferenzen immer noch unendlich ist.

Dies ist, was ich kam mit:

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

plan(L) :- 
    initial_state(I), 
    goal_state(G), false, 
    reachable(I, L, G). 

initial_state([]). 

goal_state(S) :- 
    has_bananas(S), false. 

has_bananas([grab | S]) :- false. 
has_bananas([_ | S]) :- 
    has_bananas(S), false. 

Dieses Fragment des Programms (eine so genannte failure-slice) allein ist verantwortlich für die Nicht-Kündigung. Wenn Sie damit unzufrieden sind, müssen Sie etwas im verbleibenden sichtbaren Teil ändern. Wenn nicht, gibt es keine Hoffnung, die Nicht-Beendigung zu beseitigen.

Mein Vorschlag ist, dass Sie die Reihenfolge der beiden Ziele in Plan ändern:

 
plan(L) :- 
    initial_state(I), 
    reachable(I, L, G), 
    goal_state(G). 

---

1) Das ist eine Idealisierung für alle zu Staub in kürzester Zeit ins Unendliche verglichen bröckeln wird.