Решение задачи о волке, козе и капусте

 

В заключение приведем пример решения на Прологе известной задачи о волке, козе и капусте. Данная задача была подробно описана в главе 3, посвященной продукционным моделям. Для того чтобы решить задачу на Прологе, ее следует фактически представить на языке ЛППП. Тогда получим задачу на запрос класса C. При решении используется поиск в пространстве состояний, но преимущество Пролога в том, что поиск берет на себя Turbo Prolog, а нам остается только задать правила, факты и цель.

Состояние представляется тройкой wgc(B, L, R), где В – местонахождение лодки (левый или правый берег), L – список находящихся на левом берегу, R – список находящихся на правом берегу. Начальным и конечным состояниями являются:

w – волк, g – коза, c – капуста,

B – местонахождение лодки (лево или право),

L – список находящихся на левом берегу,

R – список находящихся на правом берегу.

Первоначальное состояние: Wgc (left(wolf, goat, cаbbage), []).

Конечное состояние: Wgc (right, [], (wolf, goat, cabbage)).

Использование двух списков упрощает описание переходов. Для проверки зацикливания удобно сохранять списки обитателей в отсортированном виде: волк всегда будет в списке перед козой и оба перед капустой. Переходы между состояниями – это перевозка предметов с одного берега на другой, и их можно определить с указанием кого везем. Того, кого везем, будем называть грузом (Cargo). Ситуация, когда фермер едет в лодке один, определяется грузом Alone.

Все возможные переходы классифицируются в три предложения:

· перевозки слева направо,

· перевозки справа налево,

· одиночное плавание в любом направлении.

Для каждого из указанных переходов определим предикат или процедуру:

Update_bоat – изменяет положение лодки,

Update_banks – изменяет состав предметов на берегах.

Предикат select дает описание процедур перемещения, предикат Update_banks поддерживает список обитателей в упорядоченном виде и облегчает проверку на зацикливание. Проверка допустимости переходов делается двумя предикатами:

Legal – легальный,

Illegal – нелегальный.

Существуют ограничения: волк и коза, также как коза и капуста, не могут в отсутствие фермера находится на одном берегу.

Программа, вычисляющая последовательность необходимых перевозок выглядит следующим образом:

domains

str=string

lst=string*

state=wgc(str, lst, lst)

history=state*

moves=string*

predicates

solve_dfs(state, history, moves)

initial_state(state)

final_state(state)

move(state, string)

member(string, lst)

member1(state, history)

update(state, string, state)

update_boat(string, string)

update_bank(string, string, lst, lst, lst, lst)

select(string, lst, lst)

insert(string, lst, lst)

precedes(string, string)

legal(state)

illegal(lst)

test

clauses

test:-

initial_state(State),

solve_dfs(State, [State], Moves), write(Moves).

solve_dfs(State, History, []):–final_state(State).

solve_dfs(State, History, [Move|Moves]):–move(State, Move), update(State, Move, State1), legal(State1), not (member1(State1, History)), solve_dfs(State1, [State1|History], Moves).

initial_state(wgc(left, [wolf, goat, cabbage], [])).

final_state(wgc(right, [], [wolf, goat, cabbage])).

move(wgc(left, L, R), Cargo):–member(Cargo, L).

move(wgc(right, L, R), Cargo): –member(Cargo, R).

move(wgc(B, L, R), alone).

update(wgc(B, L, R), Cargo, wgc(B1, L1, R1)): – update_boat(B, B1), update_bank(Cargo, B, L, R, L1, R1).

update_boat(left, right).

update_boat(right, left).

update_bank(alone, B, L, R, L, R).

update_bank(Cargo, left, L, R, L1, R1): –select(Cargo, L, L1), insert(Cargo, R, R1).

update_bank(Cargo, right, L, R, L1, R1): –select(Cargo, R, R1), insert(Cargo, L, L1).

insert(X, [Y|Ys], [X,Y|Ys]): –precedes(X, Y).

insert(X, [Y|Ys], [Y|Zs]): –precedes(Y, X), insert(X, Ys, Zs).

insert(X, [], [X]).

precedes(wolf, X).

precedes(X, cabbage).

legal(wgc(left, L, R)): –not(illegal(R)).

legal(wgc(right, L, R)): –not(illegal(L)).

illegal(L): –member(wolf, L), member(goat, L).

illegal(L): –member(goat, L), member(cabbage, L).

select(X, [X|Xs], Xs).

select(X, [Y|Ys], [Y|Zs]): –select(X, Ys, Zs).

member(X, [X|Xs]).

member(X, [Y|Ys]): –member(X, Ys).

member1(X, [X|Xs]).

member1(X, [Y|Ys]): –member1(X, Ys).

 

Глава 8. ВВЕДЕНИЕ В ЯЗЫК ЛИСП

 

В данной главе излагаются основные особенности функционального программирования и языка Лисп. Материал данной главы подготовлен на основе [].