Студопедия — Решение задачи о волке, козе и капусте
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






 

В заключение приведем пример решения на Прологе известной задачи о волке, козе и капусте. Данная задача была подробно описана в главе 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. ВВЕДЕНИЕ В ЯЗЫК ЛИСП

 

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

 







Дата добавления: 2015-10-19; просмотров: 910. Нарушение авторских прав; Мы поможем в написании вашей работы!



Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Тема 2: Анатомо-топографическое строение полостей зубов верхней и нижней челюстей. Полость зуба — это сложная система разветвлений, имеющая разнообразную конфигурацию...

Виды и жанры театрализованных представлений   Проживание бронируется и оплачивается слушателями самостоятельно...

Что происходит при встрече с близнецовым пламенем   Если встреча с родственной душой может произойти достаточно спокойно – то встреча с близнецовым пламенем всегда подобна вспышке...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Краткая психологическая характеристика возрастных периодов.Первый критический период развития ребенка — период новорожденности Психоаналитики говорят, что это первая травма, которую переживает ребенок, и она настолько сильна, что вся последую­щая жизнь проходит под знаком этой травмы...

РЕВМАТИЧЕСКИЕ БОЛЕЗНИ Ревматические болезни(или диффузные болезни соединительно ткани(ДБСТ))— это группа заболеваний, характеризующихся первичным системным поражением соединительной ткани в связи с нарушением иммунного гомеостаза...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия