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


 

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

80828. PR И СМИ: ПРИНЦИПЫ РАБОТЫ, ОСНОВНЫЕ НАПРАВЛЕНИЯ ВЗАИМООТНОШЕНИЙ 47.1 KB
  Связи со СМИ одно из важнейших направлений PR. Именно поддержкой связей со СМИ mssmedi reltions в основном и занимаются большинство PRменеджеров компаний предприятий и организаций. Основные принципы работы со СМИ: представление СМИ одного голоса; сочетание плановости и гибкости; взаимодействие с представителями СМИ осуществляется как на формальном так и на не межличностном уровне Правила работы со СМИ: строить отношения на доверительной основе предоставляя информацию в полном объеме и оговаривать формы использования информации; 2.
80829. ИМИДЖ ОРГАНИЗАЦИИ: ОПРЕДЕЛЕНИЕ, ЗНАЧЕНИЕ, КЛАССИФИКАЦИЯ, ФИРМЕННЫЙ СТИЛЬ 51.62 KB
  Корпоративный имидж – целенаправленно создаваемый эмоционально окрашенный образ организации. Цель и задачи корпоративного имиджа – привлечение внимания и создание позитивного общественного мнения об организации. Коммерческой организации позитивный имидж помогает увеличить конкурентоспособность на рынке.
80830. КАЧЕСТВО И ЭФФЕКТИВНОСТЬ УПРАВЛЕНЧЕСКОГО РЕШЕНИЯ 45.22 KB
  Две модификации управленческого решения: Теоретически найденное решение; т. понятие качества управленческого решения. эффективность решения.
80831. ОСОБЕННОСТИ И МЕТОДЫ РАЗРАБОТКИ И ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ В ОРГАНАХ ГОСУДАРСТВЕННОЙ ВЛАСТИ И МЕСТНОГО САМОУПРАВЛЕНИЯ 44.64 KB
  На основе анализа ситуации и определения критериев разрабатывается как можно большее количество возможных вариантов решений из которых составляется база данных. Методы принятия решений: 1 индивидуальный решения принимаются непосредственно ответственным лицом руководителем; 2 коллективный решения принимаются в процессе делового совещания мозгового штурма или руководитель сформулировав проблему в письменном виде дает приказание специалистам способным привнести существенный вклад в ее разрешение внести свои предложения. Для этого...
80832. УПРАВЛЯЕМЫЕ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЕ И ПОЛИТИЧЕСКИЕ ПРОЦЕССЫ, ИХ СВЯЗИ И ОСОБЕННОСТИ, КЛАССИФИКАЦИЯ 44.67 KB
  В социальноэкономических и политических процессах особый интерес представляют управляемые процессы т. Социальные управляемые процессы включают в себя: деятельность направленную на сохранение жизни и здоровья человека его физическое развитие организацию дошкольного и специального трудового воспитания на создание жилищных коммунальных торговых и бытовых условий обеспечение коммуникациями и поддержание других важных составляющих в которых выражаются эти процессы воспроизводства и общения человека. Экономические управляемые процессы...
80833. ОБЩЕНАУЧНЫЕ И КОНКРЕТНО-ПРЕДМЕТНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ И ПОЛИТИЧЕСКИХ ПРОЦЕССОВ 49.34 KB
  Общенаучные методы исследования можно разделить на две большие группы: эмпирические и мыслительнологические методы.мыслительнологические методы: формализация исследование объектов когда их содержание познается с помощью выявленных элементов его формы; аналогия сходство предметов в каких либо свойствах или признаках причем в целом эти предметы различны; абстрагирование процесс мысленного выделения определенных свойств признаков и отношений некоторых объектов явлений и процессов; доказательство процесс установления истинности...
80834. ПРОГРАММА И ОРГАНИЗАЦИЯ ИССЛЕДОВАНИЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ И ПОЛИТИЧЕСКИХ ПРОЦЕССОВ 46.59 KB
  Программа исследования – комплекс основных положений определяющих проведение исслед. актуальность исследования цели и задачи объект и предмет рабочая гипотеза научный подход методы исслед. ресурсное обеспечение предполагаемый результат и ожидаемая эффективность исслед.
80835. ПРИНЦИПЫ ФОРМИРОВАНИЯ И ХАРАКТЕРИСТИКА ЗВЕНЬЕВ ФИНАНСОВО-КРЕДИТНОЙ СИСТЕМЫ ГОСУДАРСТВА 46.87 KB
  В бюджетную систему России входят бюджеты трех уровней являясь ее самостоятельными частями. К ним относятся государственные бюджеты двух уровней: а Федеральный бюджет; б Бюджеты субъектов Федерации – республиканские бюджеты республик в составе РФ; краевые областные бюджеты краев и областей городские бюджеты городов Москвы и СанктПетербурга областной бюджет автономной области и окружные бюджеты автономных округов. Третий уровень – местные бюджеты к которым относятся бюджеты муниципальных образований бюджеты районов городов и других...
80836. ФИНАНСОВЫЙ БАЛАНС МУНИЦИПАЛЬНОГО ОБРАЗОВАНИЯ 46.41 KB
  Баланс финансовых ресурсов составляется в соответствии с БК РФ и используется при составлении проекта бюджета. Показатели баланса фин ресурсов формируются на основе прогноза социальноэкономического развития и отчетного баланса фин ресурсов за предыдущий год. Баланс финресурсов позволяет выявить действительный объем и движение всех финансовых ресурсов отразить последовательно и во взаимосвязи их движение включая образование финресурсов передачу в централизованные фонды государства федеральный и региональный уровни получение ресурсов...