23669

Задача о миссионерах и каннибалах

Лабораторная работа

Информатика, кибернетика и программирование

Каждое состояние в пространстве состояний данной задачи определяется числом миссионеров и каннибалов на каждом берегу shore1miss shore1cann shore2miss и shore2cann и местоположением лодки boatlocation на одном из берегов shore1 или shore2. Для представления вершин дерева поиска можно использовать неупорядоченный факт определяемый следующим шаблоном: deftemplate MAIN::status slot shore1miss type INTEGER range 0 VARIABLE slot shore1cann type INTEGER range 0 VARIABLE slot shore2miss type INTEGER...

Русский

2013-08-05

48.5 KB

38 чел.

Лабораторная работа 5 

Тема: Задача о миссионерах и каннибалах

Цель занятия: Закрепить понимание методов поиска решений в пространстве состояний.

Общие сведения.

Задача о миссионерах и каннибалах является классической задачей ИИ: трем миссионерам и трем каннибалам необходимо переправится на противоположный берег реки с помощью двуместной лодки. При этом число каннибалов на любом берегу не должно превышать числа миссионеров (иначе первые съедят вторых).

Представление состояний и параметров задачи. Каждое состояние в пространстве состояний данной задачи определяется числом миссионеров и каннибалов на каждом берегу (shore-1-miss, shore-1-cann, shore-2-miss и shore-2-cann) и местоположением лодки (boat-location) на одном из берегов shore-1 или shore-2. Аналогично предыдущей работе, состояние можно представить неупорядоченным фактом, содержащим слоты для указания числа миссионеров и каннибалов на каждом берегу, а также местоположением лодки. Кроме того, каждая вершина ДП должна содержать глубину вершины, ссылку на родительскую вершину и последнее перемещение. Для представления вершин дерева поиска можно использовать неупорядоченный факт, определяемый следующим шаблоном:

(deftemplate MAIN::status

  (slot shore-1-miss (type INTEGER) (range 0 ?VARIABLE))

  (slot shore-1-cann (type INTEGER) (range 0 ?VARIABLE))

  (slot shore-2-miss (type INTEGER) (range 0 ?VARIABLE))

  (slot shore-2-cann (type INTEGER) (range 0 ?VARIABLE))

  (slot boat-location (type SYMBOL) (allowed-values shore-1 shore-2))

  (slot search-depth (type INTEGER) (range 1 ?VARIABLE))

  (slot parent (type FACT-ADDRESS SYMBOL) (allowed-symbols no-parent))

  (slot last-move (type STRING)))

Для повышения гибкости программы можно явно задать число миссионеров и каннибалов, определив их как глобальные переменные:

(defglobal MAIN ?*initial-missionaries* = 3

  ?*initial-cannibals* = 3)

Кроме того, следует явно задать вместимость лодки с помощью факта:

(deffacts MAIN::boat-information

  (boat-can-hold 2))

Это позволяет легко менять значения этих параметров и анализировать процесс поиска.

Исходное состояние задается фактом initial-positions на основе шаблона status. В этом факте необходимо задать глубину поиска равной 1, родительская вершина – отсутствует, число миссионеров и каннибалов на первом берегу равно соответственно initial-miss и initial-cann, число тех и других на втором берегу – 0, лодка – на первом берегу и последнее перемещение –  "No move".

Для трассировки процесса поиска решения можно использовать специальную функцию move-string, реализующую вывод сообщения о выполненном (возможном) перемещении (операторе в пространстве состояний). Этой функции необходимо передать три параметра: число миссионеров (?miss) и число каннибалов (?cann) в лодке и берег (?shore), на который они переправляются. Функцию следует определить в основном модуле (где определены правила перехода). Код функции представлен ниже:

(deffunction MAIN::move-string (?miss ?cann ?shore)

 (switch ?miss

   (case 0 then        ; число миссионеров = 0

      (if (eq ?cann 1)  

         then (format nil "Move 1 cannibal to %s.%n" ?shore)   ; число каннибалов = 1

         else (format nil "Move %d cannibals to %s.%n" ?cann ?shore)))  ; число каннибалов 1

   (case 1 then        ; число миссионеров = 1

      (switch ?cann  

        (case 0 then   

           (format nil "Move 1 missionary to %s.%n" ?shore))   ; число каннибалов = 0

        (case 1 then

           (format nil "Move 1 missionary and 1 cannibal to %s.%n" ?shore)) ; число каннибалов = 1

        (default then

           (format nil "Move 1 missionary and %d cannibals to %s.%n"  ; число каннибалов  1

                             ?cann ?shore))))

   (default         ; число миссионеров  1

     (switch ?cann

        (case 0 then

           (format nil "Move %d missionaries to %s.%n" ?miss ?shore)) ; число каннибалов = 0

        (case 1 then

           (format nil "Move %d missionaries and 1 cannibal to %s.%n"  ; число каннибалов = 1

                              ?miss ?shore))

        (default then        ; число каннибалов  1

           (format nil "Move %d missionary and %d cannibals to %s.%n"

                              ?miss ?cann ?shore))))))     

Функция должна выполняться при каждой активации правил, соответствующих операторам в пространстве состояний. Ее вызов должен быть помещен в правую часть этих правил.

Собственно поиск путей из исходного состояния в целевое выполняется правилами генерации пути. В данной задаче предлагается использовать два правила – по одному для перемещения с каждого берега (первого и второго). Для рассматриваемой вершины правило генерирует множество ее вершин-потомков. Это удобно сделать путем дублирования текущей вершины с изменением соответствующих ее параметров (слотов).

Рассмотрим действие правила shore-1-move при перемещении с первого берега. Первый условный элемент в антецеденте правила должен сопоставляться с фактом на основе шаблона status, у которого значением местоположения лодки является shore-1. Адрес соответствующей вершины необходимо сохранить в переменной ?node. Кроме того, при сопоставлении факта необходимо получить («связать») значения ?num глубины текущей вершины, а также числа миссионеров и каннибалов на обоих берегах (?s1m, ?s1c, ?s2m и ?s1c) в текущем состоянии.

Второй условный элемент в антецеденте правила должен фиксировать значение вместимости лодки, связывая значение соответствующей переменной с фактом boat-can-hold:

(boat-can-hold ?limit)

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

(bind ?max-miss (min ?s1m ?limit))

Функция bind используется в CLIPS для присваивания значений переменным.

Цикл по возможному числу миссионеров в лодке организуется оператором:

(loop-for-count (?miss 0 ?max-miss)

Затем необходимо определить минимально и максимально возможное число каннибалов в лодке:

(bind ?min-cann (max 0 (- 1 ?miss)))

(bind ?max-cann (min ?s1c (- ?limit ?miss)))

После этого организуется цикл по числу каннибалов от ?min-cann до ?max-cann.

В теле цикла должна создаваться новая вершина путем дублирования текущей, для чего используется оператор (duplicate ?node . . . ). У вновь созданной вершины должны устанавливаться следующие значения параметров:

(search-depth =(+ 1 ?num))

  •  глубина поиска – инкрементированная глубина текущей вершины;
  •  родительская вершина – адрес текущей вершины (?node);
  •  число миссионеров на первом берегу – значение этого параметра в родительской вершине уменьшенное на число миссионеров в лодке;
  •  число миссионеров на втором берегу – значение этого параметра в родительской вершине увеличенное на число миссионеров в лодке;
  •  число каннибалов на первом и втором берегах – аналогично;
  •  местоположение лодки – второй берег;
  •  последнее перемещение – должно устанавливаться значение, возвращаемое функцией move-string.

Правило перемещения со второго берега полностью аналогично.

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

  •  количество каннибалов на берегу не должно превышать количество миссионеров;
  •  поиск не должен зацикливаться, т. е. должны исключаться вершины, которые уже есть в дереве поиска на более высоких ярусах.

Эти правила следует сгруппировать в модуле CONSTRAINTS, который импортирует шаблон состояния status. Оба правила должны иметь объявление автофокусировки.

Первое правило должно активироваться состоянием, в котором число каннибалов на некотором берегу превышает количество миссионеров. Адрес соответствующей вершины сохраняется в переменной ?node и в конскеквенте правила эта вершина удаляется.

 Правило, исключающее повторные вершины, проверяет наличие двух вершин (фактов status), отличающихся только глубиной поиска. При обнаружении пары таких вершин, вершина с большей глубиной поиска удаляется. Структура данного правила аналогична использованной в предыдущей лаб. работе 4.

Конструкции, связанные с формированием и выводом на экран решения сгруппированы в модуле SOLUTION. Этот модуль должен импортировать шаблон status и глобальные переменные initial-miss и initial-cann.

Шаблон решения moves (последовательности перемещений переводящих исходное состояние в целевое) включает два слота: слот id для хранения адреса вершины-предка и мультислот для представления последовательности перемещений. Структура шаблона аналогична использованной в предыдущей лаб. работе 4.

Правило распознавания целевого состояния (goal-test) должно срабатывать при наличии вершины-состояния, в которой все миссионеры и каннибалы находятся на втором берегу (shore-2). Правая часть правила должна удалять эту вершину и добавлять в базу данных факт, представляющий путь в соответствии с шаблоном moves. В этом факте слот идентификатора вершины должен указывать на вершину-предка целевой вершины, а мультислот moves-list содержать перемещение из этой вершины-предка в целевую вершину. Правило должно содержать объявление автофокусировки.  Структура данного правила аналогична использованной в предыдущей лаб. работе 4.

Правило построения решения (build-solution) должно активироваться при наличии факта moves, у которого слот id указывает на некоторую существующую вершину status. Каждое срабатывание правила должно выполнять «подъем» в родительскую вершину и добавление в список перемещений (мульитислот moves-list) соответствующего перемещения. Данное правило может быть записано следующим образом.

(defrule SOLUTION:: build-solution

 ?node <- (status (parent ?parent)  ; ?node – вершина-состояние, являющаяся родителем

     (last-move ?move)) ; ее адрес указан в идентификаторе решения moves

 ?mv <- (moves (id ?node) (moves-list $?rest)) ; ?mv – адрес решения moves

=>

 (modify ?mv (id ?parent) (moves-list ?move ?rest))) ; решение (факт moves) модифицируется

  ; путем добавления к мультислоту moves-list

  ; значения ?move последнего перемещения

Правило вывода решения на экран (print-solution) выполняется после завершения построения пути-решения. Оно должно сработать, когда обнаружится факт moves, не имеющий родительской вершины (корневая вершина ДП). Правило вывода решения на экран может быть задано так:

(defrule SOLUTION::print-solution

 ?mv <- (moves (id no-parent) (moves-list "No move." $?m))

=>

(retract ?mv)

(printout t t  "Solution found: " t t)

(progn$ (?move ?m) (printout t ?move)))

Функция progn$  в CLIPS выполняет множество действий для каждого поля значений мультислота.

Порядок выполнения работы.

1. Построить для данной задачи полное дерево поиска.

2. Разработать программу решения задачи, используя среду CLIPS. Программа должна содержать три модуля: основной (MAIN), контроля ограничений (CONSTRAINTS) и вывода решения (SOLUTION).

2.1. Модуль MAIN должен содержать следующие конструкции:

  •  объявление модуля MAIN, включая  объявления экспорта шаблона состояния (status) и глобальных переменных числа миссионеров (initial-miss) и каннибалов (initial-cann);
  •  определение шаблона факта-состояния (status);
  •  определение глобальных переменных initial-miss и initial-cann (задание их значений);
  •  определение факта исходного состояния initial-positions;
  •  определение факта вместимости лодки;
  •  определение функции вывода сообщения move-string;
  •  определение правил генерации пути в пространстве состояний.

2.2. Модуль CONSTRAINTS должен содержать:

  •  объявление модуля CONSTRAINTS,  включая импорт из модуля MAIN шаблона status;
  •  определение правила, срабатывающего на запрещенные состояния, когда каннибалы могут съесть миссионеров;
  •  определение правила, срабатывающего в ситуации зацикливания процесса поиска (circular-path).

2.3. Модуль вывода решения SOLUTION должен содержать:

  •  объявление модуля SOLUTION, включая импорт из модуля MAIN шаблона status и глобальных переменных initial-miss и  initial-cann;
  •  определение шаблона решения – последовательности перемещений (moves);
  •  определение правила распознавания целевого состояния (goal-test);
  •  определение правила построения решения (build-solution);
  •  определение правила вывода решения на экран (print-solution).

3. Выполните программу в пошаговом режиме, проанализируйте и объясните ход процесса поиска решения. В отчете необходимо привести трассу поиска решения.


 

А также другие работы, которые могут Вас заинтересовать

38759. Экономика и управление на предприятии ОАО «Новосибирская макаронная фабрика» 126.5 KB
  Королева Отчет по преддипломной практике по предприятию ОАО Новосибирская макаронная фабрика по специальности Экономика и управление на предприятие Выполнила: Детюченко В. Данную работу можно разделить на несколько разделов: 1 Уставные характеристики организации 2 История предприятия ОАО Новосибирская макаронная фабрика 3 Приоритетные направления деятельности ОАО Новосибирская макаронная фабрика 4 Анализ структуры предприятия 5 Анализ системы закупок Заключение Список использованной литературы Содержание...
38760. Социальная психология и психотерапия 456.5 KB
  психика это системное качво мозга которое реализуется чз функциональные сисмы мозга кторые формируются у Ч в прцессе жизни и овладения им истор сложившихся форм Дти и опыта человва чз собственную активную Дть. Фрейд определял генезис психического как одну из важных детерминант полноценного функционирования взрослого человека Принцип субъекта предполагает рассматривать человека как автономную инициативную личность способную в определенных пределах изменять себя и окружающий мир. Формы взаимодействия чел в миром. Выполняя...
38761. Ответы по географии для 9 класса 251 KB
  Географические различия в хозяйственной деятельности населения России привести конкретные примеры. Культурноисторические особенности народов России. Особенности природы населения и хозяйства отдельных территорий России привести примеры. Часовые пояса на территории России.
38763. Коммуникативная концепция права: Проблемы генезиса и теоретико-правового обоснования 294 KB
  Задачей диссертационного исследования является исследование и обоснование узловых аспектов коммуникативной теории права как одного из возможных вариантов интегрального правопонимания. Согласно такому целостному подходу право, как интерсубъективная правовая реальность, рассматривается в коммуникативно-деятельном, ценностном, семиотическом и психологическом аспектах и соответственно онтологически интерпретируется и феноменологически....
38764. Изучение городского пространства Исследование Витебского вокзала по заданному алгоритму 6.42 MB
  Список группы: Белова Елена Витальевна Веснина Мария Воробьёва Марина Евгеньевна Гайдукова Екатерина Владимировна Гусейнова Дина Денисова Ирина Михайловна Иванова Людмила Валентиновна Иванова Светлана Ильинична Киселёва Татьяна Станиславовна Группа за работой в музее Задание №1 Изучение городского пространства Исследование Витебского вокзала по заданному алгоритму. Задание №2 Исследование картин. Кроме работы на курсах было дано задание провести фасилитированное обсуждение...
38765. Юриспруденция. Методические указания 919 KB
  Изложенные материалы предназначены для оказания практической помощи студентам специальности 021100 030501 Юриспруденция при выборе темы дипломной работы ее написания оформления и защиты. Иркутский государственный технический университет Кафедра государственноправовых дисциплин ИрГТУ ОГЛАВЛЕНИЕ [1] ОГЛАВЛЕНИЕ [2] ВВЕДЕНИЕ [3] ВЫБОР И УТВЕРЖДЕНИЕ ТЕМЫ ДИПЛОМНОГО СОЧИНЕНИЯ [4] ВЫДАЧА ЗАДАНИЯ СОСТАВЛЕНИЕ КАЛЕНДАРНОГО ГРАФИКА РАБОТЫ И ПЛАНА ДИПЛОМНОГО СОЧИНЕНИЯ [5] ТРЕБОВАНИЯ К ОГЛАВЛЕНИЮ ДИПЛОМНОЙ РАБОТЫ [6] СБОР АНАЛИЗ И...
38766. Рынок чистой монополии 146.5 KB
  Для формирующегося рынка России характерна высокомонополизированная структура поддерживаемая созданием в последние годы различного рода концернов ассоциаций и других объединений одной из целей которых является поддержание высоких цен и обеспечение себе спокойного существования . Например для открытия коммерческого банка в России помимо установленного минимального размера уставного фонда требуется специальное разрешение Центрального банка РФ получить которое достаточно сложно. Развитие системы государственного регулирования естественных...
38767. Обследование хирургического больного 1.74 MB
  Следует также выяснить функцию различных систем организма в течение заболевания: сердечнососудистой боли в области сердца одышка сердцебиение отеки дыхательной кашель мокротаколичество запах цвет примеськрови пищеварительной тошнота отрыжка рвота стул нервной сон раздражительность головные боли мочевыделительной частота боль при мочеиспускании примесь крови. Усиленный рост волос на теле гипертрихоз наблюдается при расстройстве функций некоторых желез внутренней секреции в частности надпочечников а также...