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

31 чел.

Лабораторная работа 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. Выполните программу в пошаговом режиме, проанализируйте и объясните ход процесса поиска решения. В отчете необходимо привести трассу поиска решения.


 

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

39407. Статистика Методические указания по выполнению курсовой работы 2 MB
  Цель работы – закрепление и углубление теоретических знаний полученных в ходе изучения курса Статистика формирование у студентов – будущих специалистов обучающихся по специальности Государственное и муниципальное управление теоретических знаний и практических навыков по сбору обработке и анализу статистической информации выявление эффективных вариантов принимаемых управленческих решений развитие у студентов творческой инициативы и навыков исследовательской деятельности. Примерные темы курсовых работ Статистикоэкономический...
39408. Проектирование цифрового частотомера 840.51 KB
  В роли источника питания может выстапать гальванический элемент или аккумулятор напряжением 15 В. С помощью преобразователя напряжения это значение повышают до 5 В напряжение необходимое для стабильной работы устройства. Вход Рисунок 2 – Функциональная схема В состав блока формирователя импульсного напряжения входит: входное гнездо XS1 на которе подают импульсное или переменное напряжение частоту которого нужно измерить; резисторы R1 ограничивает входной ток R2 R3 устанавливает нижний предел напряжения входного сигнала R4;...
39409. Проект полігонометрії 4 класу 192 KB
  Розграфлення – система поділу топографічних карт на частини з метою одержання листів карт більш крупного масштабу. Основою для створення всіх крупно масштабних карт є карта масштабу 1:1000000. Для того щоб отримати карту масштабу 1:1000000 вся поверхня земної кулі умовно поділяється на колони через 6˚ по довготі від меридіана 180˚ та паралелями на пояси через 4˚ по широті на північ та на південь від лінії екватора. Утворення карти масштабу 1:1000000 Правило подальшого розграфлення листів топографічних карт полягає в постійному поділі листа...
39410. Геодезія, картографія та кадастр 349.5 KB
  070908 Геоінформаційні системи і технології€ ВСТУП Поряд з теоретичною підготовкою з курсу Організація планування і управління топографогеодезичним виробництвом і інших спеціальних дисциплін в лабораторних і індивідуальних заняттях складається курсовий проект для надбання студентами практичних навиків в плануванні і організації геодезичних робіт. Зміст технічних проектів на виконання робіт регламентується Положенням про складання технічних проектів і програм на виконання загальнодержавних топографогеодезичних і картографічних робіт€ та...
39411. Знімальні мережі 345.5 KB
  Мензульне і тахеометричне знімання При мензуальному або тахеометричному зніманні пункти планової знімальної мережі є одночасно пунктами висотної знімальної мережі і служать безпосередньо для встановлення на них мензули з кіпрегелем або теодоліта якими здійснюється набір пікетів для створення контурної частини плану і рельєфу місцевості. В цьому випадку пункти знімальної основи закріплюють на місцевості центрами тривалого збереження з таким розрахунком щоб на кожному планшеті було не менше трьох точок при зніманні в масштабі 1:2000...
39412. Проект робіт при оновленні топографічних карт масштабу 1:10000 515 KB
  Київський Державний Університет Будівництва та Архітектури КУРСОВИЙ ПРОЕКТ з дисципліни Організації управління і планування топографогеодезичного виробництва на тему: Проект робіт при оновленні топографічних карт масштабу 1:10000€ Виконала:...
39413. Реализация и исследование быстрого алгоритма двумерного вещественного ДПФ по основанию 4 представлением данных в гиперкомплексной алгебре 294.73 KB
  Заданный алгоритм был реализован программно с помощью технологии Microsoft. NET Framework на языке программирования C++. Написанное приложение состоит из двух сборок: библиотеки классов FFT, содержащей все необходимое для вычисления ДПФ по формуле и БПФ.
39414. Реализация и исследование быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания с представлением данных в алгебре кватернионов 308.5 KB
  ЗАДАНИЕ Реализация и исследование быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания с представлением данных в алгебре кватернионов. Текст программы 1 Постановка задачи Нахождение спектра квадратной матрицы размера с помощью быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания с представлением данных в алгебре кватернионов. Тестирование полученной реализации алгоритма ее исследование и сравнение с обычным алгоритмом двумерного ДПФ. Рассмотрим...
39415. РАСЧЕТ И КОНСТРУИРОВАНИЕ ОДНОСТУПЕНЧАТОГО ЗУБЧАТОГО РЕДУКТОРА 4.1 MB
  Проектный расчёт закрытой цилиндрической зубчатой передачи . Геометрический расчет закрытой цилиндрической передачи.5 Проверочный расчет закрытой цилиндрической передачи . Расчет открытой цилиндрической зубчатой передачи .