LAB6_1 (Лабораторные работы по Прологу (задания уточнять у преподавателя))

 ЛАБОРАТОРНАЯ РАБОТА 2.

 ПРОСТРАНСТВО СОСТОЯНИЙ.

ЦЕЛЬ. Знакомство с одной общей схемой для представления задач, называемой пространством состояний.

 Пространство состояний  - это ориентированный граф , вершины которого соответствуют ситуациям, встречающимся в задаче, дуги определяются разрешенным переходам из одной ситуации в другую, а решение задачи сводится к поиску пути в этом графе.

Рассмотрим задачу о трех сосудах. Имеется три сосуда емкостью 8, 5 и 3 литра. В первом сосуде содержится 8 литров вина. Требуется разделить вино поровну, пользуясь только этими тремя сосудами, т.е. алгоритм переливания.

Информацию об объемах сосудов представим фактом: объемы(8,5,3).

Правило переливания из одного сосуда в другой:

Чтобы перелить из одного сосуда в другой, надо, чтобы в сосуде "откуда" было какое-то количество вина, а в сосуде "куда"- свободное место. Если в сосуде "откуда" вина больше чем

свободного места в сосуде "куда", то переливается количество, равное свободному объему сосуда "куда", в противном случае из сосуда "откуда" выливается все вино, т.е. переливаемое количество равно минимуму из количества вина в сосуде "откуда" и свободного места в сосуде "куда". После переливания вина в сосуде "откуда" станет меньше на перелитое количество, а в сосуде "куда" увеличится на столько же. Количество вина в оставшемся третьем сосуде не

изменится. Затем надо повторить переливание из нового состояния так, чтобы после ряда переливаний получить в двух первых сосудах по 4 литра.

В этой задаче ситуацию можно описать следующим образом

состояние(Количество_вина_в_первом_сосуде, Количество_вина_во_втором_сосуде,

Количество_вина_в_третьем_сосуде).

дуги пространства состояний определяются разрешенным переходам из одной ситуации в другую, т.е. правилами переливаниями. Задача отыскания решения эквивалентна задаче построения пути между начальной ситуацией (8,0,0) и конечной ситуацией (4,0,0).

---------------------г=======¬

¦--------------------¦ 8,0,0 ¦----------------------¬

¦¦-------------------¦=T=T=TT---------------------¬ ¦

¦¦¦ ¦ ¦ ¦L----------------¬ ¦ ¦

¦¦¦ г=======¬ ¦ ¦ ¦ г=======¬ ¦ ¦ ¦

¦¦¦ ¦ 3,5,0 ¦----- ¦ L----¦ 5,0,3 ¦ ¦ ¦ ¦

¦¦¦ L=T====T- ¦ L=T=T=T=- ¦ ¦ ¦

¦¦¦ --- L-----¬ ¦ -------- ¦ L--¬ ¦ ¦ ¦

¦¦¦ г=====¦=¬ г=¦=¦=¦=¬ ¦ г=¦===¦=¬ ¦ ¦

¦¦¦ ¦ 3,2,3 ¦--------¦ 0,5,3 ¦---¬ ¦ ¦ 5,3,0 ¦ ¦ ¦

¦¦¦ L===T===- L=T===T=- ¦ ¦ L===T===- ¦ ¦

¦¦¦ ¦ ¦ ¦ ¦ L---¬ ¦ ¦ ¦

¦¦¦ г===¦===¬ ¦ ¦ ¦ г¦==¦===¬ ¦ ¦

¦¦L-¦ 6,2,0 ¦ ¦ ¦ L-----¦ 2,3,3 ¦ ¦ ¦

¦¦ L===T===- ¦ ¦ L===T===- ¦ ¦

¦¦ ¦ ¦ ¦ ¦ ¦ ¦

¦¦ г===¦===¬ ¦ ¦ г===¦===¬ ¦ ¦

¦L--¦ 6,0,2 ¦ ¦ ¦ ¦ 2,5,1 ¦ ¦ ¦

¦ L===T===- ¦ ¦ L===T===- ¦ ¦

¦ ¦ ¦ ¦ ¦ ¦ ¦

¦ г===¦===¬ ¦ ¦ г===¦===¬ ¦ ¦

¦ ¦ 1,5,2 ¦ ¦ ¦ ¦ 7,0,1 ¦--- ¦

¦ L===T===- ¦ ¦ L===T===- ¦

¦ ¦ ¦ ¦ ¦ ¦

¦ г===¦===¬ ¦ ¦ г===¦===¬ ¦

¦ ¦ 1,4,3 ¦----------- ¦ ¦ 7,1,0 ¦-----

¦ L===T===- ¦ L===T===-

¦ ¦ L-------------¬ ¦

¦ г===¦===¬ г=¦=¦===¬

L---¦ 4,4,0 ¦--------------------------¦ 4,1,3 ¦

L=======- L=======-

Чтобы не "зацикливаться" будем хранить все пройденные состояния в списке в виде структур сост(В_первом,Во_втором,В_третьем) и проверять каждое новое состояние на принадлежность этому списку.

Для трех сосудов возможно шесть вариантов переливаний и соответственно 6 правил

(1->2, 1->3, 2->1, 2->3, 3->1, 3->2).

Правило из 1 во 2:

перелить(В_первом,Во_втором,В_третьем,Пройденные):-

объемы(Объем1,Объем2,Объем3), В_первом>0,

Свободно is Объем2-Во_втором, Свободно>0,

минимум(В_первом,Свободно,Количество),

Стало_в_первом is В_первом - Количество,

Стало_во_втором is Во_втором + Количество,

Новое = сост(Стало_в_первом,Стало_во_втором,В_третьем),

не_принадлежит(Новое,Пройденные),

перелить(Стало_в_первом,Стало_во_втором,В_третьем,[Новое|Пройденные]).

Правило завершения переливаний:

перелить(4,4,0,Пройденные):- write(Пройденные).

Запрос: ?-перелить(8,0,0,[]).

 ЗАДАНИЕ 1. Построить граф пространства состояний для задачи переупорядочевания кубиков, поставленных друг на друга, как показано на рисунке.















  Начальная ситуация Конечная ситуация

На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только, если он лежит сверху. Кубик можно поставить либо на стол, либо на другой кубик. Напишите программу переупорядочивания кубиков.

 ЗАДАНИЕ 2. Напишите программу для решения задачи о переливании.

 ЗАДАНИЕ 3. Решите задачу о переливании для сосудов емкостью 10,7 и 3 л.

 ЗАДАНИЕ 4.("Волк, коза и капуста"). Перевозчику нужно переправить через реку волка, козу и мешок с капустой. Лодка так мала, что кроме перевозчика может взять только один из этих объектов. Кроме того, капусту нельзя оставлять вместе с козой, а козу с волком. Как можно осуществить переправу?

Напишите программу для решения задачи "Волк, коза и капуста".

 ВАРИАНТЫ САМОСТОЯТЕЛЬНЫХ ЗАДАНИЙ.

 ЗАДАНИЕ 1.("Миссионеры и каннибалы"). Три миссионера и три каннибала находятся на левом берегу реки. Здесь же - лодка, вмещающая не более двух человек. Все хотят перебраться на другой берег. Если на каком-либо берегу каннибалов окажется больше, чем миссионеров, то каннибалы съедят оставшихся в меньшинстве миссионеров. Найти последовательность ездок, гарантирующих безопасную переправу на правый берег.

Напишите программу для решения задачи "Миссионеры и каннибалы".

 ЗАДАНИЕ 2.  Решите задачу о "Миссионерах и каннибалах" для случая, когда только один миссионер и каннибал умеют грести.

ЗАДАНИЕ 3.("Ревнивые мужья"). Три ревнивых мужа и их жены должны переправиться через реку. имеется только одна маленькая лодка, которая может выдержать одновременно только двоих. Как могут переправиться все шестеро, если никакой муж не оставит жену в присутствии других мужчин.

Напишите программу для решения задачи "Ревнивые мужья".

ЗАДАНИЕ 4.  Модифицируйте программу для случая пяти супружеских пар и лодки, вмещающей 3 человека.

ЗАДАНИЕ 5. (Железнодорожная стрелка). Два поезда с n и m вагонами смогут разминуться с помощью изображенной здесь стрелки и продолжить движение дальше вперед паровозами. Небольшой боковой тупик достаточен для того, чтобы принять либо один паровоз, либо

один вагон.

 



















 ЗАДАНИЕ 6 .  (Солдаты в окопе). На рисунке изображены 8 солдат и сержант в окопе. Сержант хочет перебраться на другой конец окопа, но так чтобы при этом все остальные солдаты остались на своих местах. Окоп слишком узок и вдвоем в нем не разойтись.



і і





ЗАДАНИЕ 7 .(Черное и белое). На рисунке изображены 8 фишек двух цветов.

Надо переставлять по две соприкасающиеся фишки в один из концов так,

чтобы образовалась последовательность фишек, в которой сначала

идут все черные фишки, а затем все белые.









ЗАДАНИЕ 8 .(Анжелика).

----¬ ----¬ ----¬

А +-+ К +-+ И ¦

L-T-- L-T-- L-T--

--+-¬ --+-¬ --+-¬

¦ Л +-+ Е +-+ Ж ¦

L-T-- L-T-- L-T--

--+-¬ --+-¬ --+-¬

¦ Н +-+ А +-+ ¦

L---- L---- L----

 ш0

Передвигая фишки вдоль прямых на свободные места составить слово

АНЖЕЛИКА.

 ш1.0

----¬ ----¬ ----¬

¦ А +-+ Н +-+ Ж ¦

L-T-- L-T-- L-T--

--+-¬ --+-¬ --+-¬

¦ Е +-+ Л +-+ И ¦

L-T-- L-T-- L-T--

--+-¬ --+-¬ --+-¬

¦К +-+ А +-+ ¦

L---- L---- L----

 ш0

 2ЗАДАНИЕ 9 . 0(Поссорившиеся пары). Три супружеские пары должны

перебраться через реку в маленькой лодке, которая может выдержать

одновременно только двоих. Мистер С поссорился с двумя другими

джентельменами, а миссис С перестала разговаривать с остальными

леди. Как могут переправиться все шестеро, если ни одна из женщин

не умеет грести и никакие два человека, находящихся в ссоре, не

переправляются одновременно и даже не находятся одновременно на

одном берегу.

 2ЗАДАНИЕ 10. 0 На рисунке перед Вами знаменитая головоломка -

игра в 15, в которой требовалось, передвигая фишки в коробке,

расположить 14 и 15 в правильном порядке.

 ш1.0

-----T----T----T----¬

¦ 1 ¦ 2 ¦ 3 ¦ 4 ¦

+----+----+----+----+

¦ 5 ¦ 6 ¦ 7 ¦ 8 ¦

+----+----+----+----+

¦ 9 ¦ 10 ¦ 11 ¦ 12 ¦

+----+----+----+----+

¦ 13 ¦ 15 ¦ 14 ¦ ¦

L----+----+----+-----

 ш0

 2ЗАДАНИЕ 11. 0("Четные и нечетные фишки"). Стопка из 8 фишек по-

мещена в центральный квадрат, как показано на рисунке.

- 6 -

 ш1.0

---------------------------¬

¦ ----¬ ----¬ ¦

¦ ¦ ¦ A B ¦ ¦ ¦

¦ L---- L---- ¦

¦ нечет ----¬ чет ¦