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

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

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


prolog non-termination failure-slice
person Cu2S    schedule 22.03.2016    source источник
comment
has_bananas/1 генерирует списки, в которых есть один экземпляр grab, а остальные являются анонимными, неинстантированными переменными и неконкретным хвостом. Это то, что вы хотите, чтобы этот предикат делал?   -  person lurker    schedule 22.03.2016
comment
Вы находите решение с помощью N = 4, не так ли?   -  person false    schedule 23.03.2016

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

На самом деле вы находите план, но потом все зацикливается. Что касается количества выводов, у вас бесконечно много1.

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

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

?- 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.

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

Мое предложение состоит в том, чтобы вы изменили порядок двух целей в плане на:

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

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

person false    schedule 22.03.2016