Обезьяна и банан в мышлении как вычисление

Question

Я читаю книгу " Мышление как вычисление" и написал код в главе 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 относится к длине L в plan(L) (например N 4, когда запрос plan([M1, M2, M3, M4])) Но это не работает.

Есть ли решение?

Answer 1

Непрерывание - это очень сложный бизнес в Прологе, особенно если вы привыкли к другим, более ориентированным на командные языки программирования. Очень заманчиво попытаться понять проблему шаг за шагом. Но очень часто это ни к чему не приводит в Прологе.

Вместо этого рассмотрите возможность изменения вашей программы. Только немного. И таким образом, что легко предсказать, каков будет эффект ваших модификаций. Например, добавить false цели в вашу программу. Каким будет их эффект? Ну, не очень: эти цели уменьшат количество выводов. И, возможно, они также уменьшат набор найденных решений. Но на данный момент давайте придерживаться количества выводов. Вы столкнулись со случаем, когда ваша программа не завершает работу для:

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

На самом деле, вы найдете план, но затем все это зацикливается. С точки зрения количества выводов, у вас бесконечно много ¹.

Чтобы локализовать ответственную часть, давайте добавим false цели в вашу программу. Добавьте их так, чтобы число выводов оставалось бесконечным.

Вот что я придумал:

? - длина (L, 4), план (L). план (L):- начальное состояние (I), целевое состояние (G), ложное, достижимое (I, L, G). начальное состояние([]). цель_состояния (S):-
   has_bananas(S), ложь. has_bananas ([grab | S]): - неверно. has_bananas ([_ | S]): - has_bananas (S), false. 

Этот фрагмент вашей программы (называемый срез-срез) сам по себе отвечает за прекращение. Если вы недовольны этим, вам придется что-то изменить в оставшейся видимой части. Если нет, то нет надежды убрать не прекращение.

Я предлагаю вам изменить порядок двух целей в плане:

план (L):-
   initial_state(I)
   достижимый (I, L, G),
   goal_state (G).

---

1) Это идеализация для всех, которые быстро рассыпаются в прах по сравнению с бесконечностью.