А.А. Вахтин, В.В. Гаршина ЛАБОРАТОРНЫЙ ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ НА ЯЗЫКЕ CLIPS ДЛЯ КУРСА ПРЕДСТАВЛЕНИЕ ЗНАНИЙ ФКН ВГУ 2012

Скачать pdf+word версии этой методички можно здесь.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
А.А. Вахтин, В.В. Гаршина
ЛАБОРАТОРНЫЙ ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ НА ЯЗЫКЕ CLIPS ДЛЯ КУРСА «ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ»
Учебно-методическое пособие для вузов
Издательско-полиграфический центр Воронежского государственного университета 2010
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
А.А. Бахтин, В.В. Гаршина
ЛАБОРАТОРНЫЙ ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ НА ЯЗЫКЕ CLIPS ДЛЯ КУРСА «ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ»
Учебно-методическое пособие для вузов
Издательско-полиграфический центр Воронежского государственного университета 2010
(1) сопоставление фактов и правил;
(2) выбор правила, подлежащего активизации;
(3) выполнение действий, предписанных правилом.
Такой трехшаговый циклический процесс иногда называют "цикло распознавание-действие".
Принципиальным отличием данной системы от аналогов является то, чтс она полностью реализована на языке С. Причем исходные тексты ее програм опубликованы в Internet.
В CLIPS используется оригинальный LISP - подобный язь программирования, ориентированный на разработку экспертных систем (ЭС CLIPS поддерживает две парадигмы программирования: объекты ориентированную и процедурную.
1.1. Основные элементы программирования в CLIPS
CLIPS предоставляет три основных элемента для написания программ:
Простые типы данных;
Конструкции для пополнения базы знаний;
Функции для манипулирования данными.
1.1.1. Простые типы данных
Для представления информации в CLIPS предусмотрено восемь прость типов данных: Float, integer, symbol, string, external-address, fact-addres instance-name, instance-address.
При записи числа используются цифры (0-9), десятичная точка (.), знак .+). (е).
Любое число, состоящее только из цифр, перед которыми стоит зна сохраняется как целое (В CLIPS - integer, в С - long integer). Все остальны числа сохраняются как Float (в С - double Float). Symbol - последовательност символов кода ASCII, причем как только в этой последовательност
встречается символ-разделитель, symbol заканчивается. Символы-разделители: пробел, табуляция, двойные кавычки, (,), &, |, , ;.
String - последовательность символов, заключенных в двойные кавычки ("a and b"). Причем, если внутри строки встречаются двойные кавычки, то перед ними надо поместить символ (\) ("a and \'Ъ").
1.1.2. Работа с базой знаний в CLIPS. Факты
Факт представляет собой основную единицу данных, используемую правилами. Факты помещаются в текущий список фактов fact-list. Количество фактов с списке и объем информации, содержащейся в факте ограничивается только размером памяти компьютера.
Факт может описываться индексом или адресом. Всякий раз, когда факт добавляется (изменяется) ему присваивается уникальный целочисленный индекс. Индексы в fact-list начинаются с нуля.
Идентификатор факта - это короткая запись факта, которая состоит из символа факта - f и индекса факта (f-10). Например: f-0 (today is Sunday) f-1 (weather is warm)
Факты представимы в двух форматах: позиционные и непозиционные. Позиционные факты - состоят из выражения символьного типа, за которым следует последовательность (возможно, пустая) из полей, разделенных пробелами. Вся запись заключается в скобки. Для того чтобы обратиться к информации, содержащейся в позиционном факте, пользователь должен знать какие данные содержаться в факте и в каком поле они хранятся. Пример:
(altitude is 10000 feet) (grocery list bread milk eggs) (today is Sunday)
(weather is warm)
Поля в позиционных фактах могут быть любого простого типа, исключением первого поля, которое всегда должно быть типа symbol.
В тексте программы факты можно включать в базу не по одиночке, целым массивом. Для этого в CLIPS имеется команда deffacts. (deffacts today (today is Sunday) (weather is warm) )
Выражение начинается с команды deffacts, затем приводится имя спис фактов, который программист собирается определить (в нашем примере today), а за ним следуют элементы списка, причем их количество ограничивается.
В CLIPS существуют следующие зарезервированные слова, которые могут использоваться как первое поле любого факта: test, and, or, not, decla logical, object, exists, forall.
Непозиционные факты (шаблонные факты) - реализуются че конструкцию, подобную структуре или записи в языках С и Паск Шаблонные факты позволяют задавать имена каждому из полей факта.
Для задания шаблона, который затем может использоваться при доступ полям по именам, используется конструкция (deftemplate ) (slot-1) (slot-2)
(slot-N)
где - имя шаблона, (slot-N) - именованное поле (или слот). Сло могут быть ограничены по типу, значению, числовому диапазону, могут содержать значение по умолчанию. Порядок следования слотов значения не
имеет.
Пример:
(deftemplate student
"a student record"
(slot name (type STRING))
(slot age (type NUMBER) (default 18))
)
Каждое определение шаблона состоит из произвольного имени шаблона, необязательного комментария и некоторого количества определений слотов (начинаются с ключевого слова slot или field). Слот включает поле данных, например паше, и тип данных, например STRING. Можно указать и значение по умолчанию, как в приведенном выше примере, где возраст студента по умолчанию равен 18.
Если в программу включено приведенное выше определение шаблона, то выражение
(deffacts students (student (name "fred")) (student (name "jack") (age 19)) )
приведет к тому, что в базу фактов после выполнения команды reset будет Добавлено
(student (name "fred") (age 18)) (student (name "jack") (age 19))
i-1.3. Операции над фактами
Факты можно добавлять к списку фактов (assert), удалять из списка
фактов (retract), изменять (modify), дублировать (duplicate)
Рассмотрим работу с базой фактов в CLIPS на практике. Сразу после , запуска CLIPS-приложения (clipswin.exe) на выполнение на экране появится сообщение, извещающее пользователя, что он работает с интерпретатором. CLIPS>
В режиме интерпретатора пользователь может использовать множество команд, гак можно включить в базу фактов прямо из командной строки с помощью assert, например:
CLIPS> (assert (today is Sunday))
CLIPS> (assert (weather is warm))
Для вывода списка фактов, имеющихся в базе, используется команда facts: CLIPS> (facts) f-0 (today is Sunday) f-1 (weather is warm)
Для удаления фактов из базы используется команда retract.
CLIPS> (retract 1)
CLIPS> (facts)
f-0 (today is Sunday)
Эти же команды, assert и retract, используются в выполняемой част правила (заключении правила) и с их помощью выполняется программно изменение базы фактов.
Часто приходится пользоваться и другой командой интерпретатора, clear, которая очищает базу фактов (как правило, эта команда доступна в одном из выпадающих меню). CLIPS> (clear)
CLIPS> (facts)
Массив фактов можно удалить из базы командой undeffacts. Например, если в программе был введен массив фактов с именем today: (deffacts today (today is Sunday) (weather is warm) )
который необходимо удалить, то в командной строке необходимо ввести следующую команду:
CLIPS> (undeffacts today)
Выражение deffacts можно вводить и в командную строку интерпретатора, но лучше записать его в текстовый файл с помощью редактора CLIPS или любого другого текстового редактора (файлы имеют расширение .clp). Загрузить этот файл в дальнейшем можно с помощью команды в меню File либо из командной строки. CLIPS> (load "my file")
Однако после загрузки файла факты не передаются сразу же в базу фактов CLIPS. Команда deffacts просто указывает интерпретатору, что существует массив today, который содержит множество фактов. Собственно загрузка выполняется командой reset. CLIPS> (reset)
Команда reset сначала очищает базу фактов, а затем включает в нее факты из всех ранее загруженных массивов. Она также добавляет в базу единственный определенный системой факт: f-0 (initial-fact)
Это делается по умолчанию, поскольку иногда имеет смысл включить в программу правило start rule, которое может быть сопоставлено с этим фактом и позволит выполнить какие-либо инициализирующие операции.
Можно проследить, как выполняется команда reset, если пере выполнением приведенных выше команд установить режим слежения сред" разработки. Для этого нужно вызвать команду Watch из меню Execution установить в ней флажок Facts.
1.1.4. Работа с базой правил. Правила
В языке CLIPS правила имеют следующий формат: (defrule




=>

)
Например: (defrule chores "Things to do on Sunday" (declare (salience 10)) (today is Sunday)
(weather is warm)
=>
(assert (wash car)) (assert (chop wood))
В этом примере Chores - произвольно выбранное имя правила. Предпосылки условной части правила - это: (today is Sunday) (weather is warm)
сопоставляются затем интерпретатором с базой фактов, а действия, перечисленные в выполняемой части правила (она начинается после пары символов =>), вставят в базу два факта: (wash car) (chop wood)
в случае, если правило будет активизировано. Приведенный в тексте правила комментарий "Things to do on Sunday" (Что сделать в воскресенье) поможет в дальнейшем вспомнить, чего ради это правило включено в программу. Выражение
(declare (salience 10)) указывает на степень важности правила. Пусть, например, в программе имеется другое правило (defrule fun
"Better things to do on Sunday" (salience 100) (today is Sunday)
(weather is warm)
=>
(assert (drink beer)) (assert (play guitar)) )
Поскольку предпосылки обоих правил одинаковы, то при выполнении оговоренных условий они будут «конкурировать» за внимание интерпретатора,
Предпочтение будет отдано правилу, у которого параметр salience имеет более высокое значение, в данном случае - правилу fun. Параметру salience может быть присвоено любое целочисленное значение в диапазоне (-10 ООО, 10 000J. Если параметр salience в определении правила опущен, ему по умолчанию присваивается значение 0.
Обычно в определении правила присутствуют и переменные (они начинаются с символа ?). Если, например, правило (defrule pick-a-chore "Allocating chores to days" (today is ?day)
(chore is ?job)
=>
(assert (do ?job on ?day)) )
будет сопоставлено с фактами (today is Sunday) (chore is carwash) то в случае активизации оно включит в базу новый факт (do carwash on Sunday)
Аналогично, правило (defrule drop-a-chore "Allocating chores to days" (today is ?day)
?chore =>
(retract ?chore) )
отменит выполнение работ по дому (?chore). Обратите внимание на то, что оба экземпляра переменной ?day должны получить одно и то же значение.
Переменная '.'chore в результате сопоставления должна получить ссылку на факт (это делает оператор содержатся
(today is Sunday) (do carwash on Sunday) то при активизации правила из базы будет удален факт (do carwash on Sunday)
Отметим, что факт: (do carwash on Sunday) будет сопоставлен с любым из представленных ниже образцов (do ? ? Sunday) (do ? on ?) (do ? on ?when)
Если за префиксом ? не следует имя переменной, он рассматриваются как универсальный символ подстановки, которому может быть сопоставлен любой элемент.
При написании правил в части посылок иногда требуются некоторые логические операции, например, необходимо указать факты, что «сегодня суббота или воскресенье», «цветок не синий», «шар большой и зеленый». Это реализуется специальными логическими операторами: «ИЛИ», «НЕ», «И», которые обозначаются как |, & соответственно. Таким образом указанные выше факты запишутся следующим образом: (today is Saturday|Sunday) (flower is -blue) (ball is big&green)
1.1.5. Функции для манипулирования данными. Определение функций
Существует несколько типов функций: пользовательские и системные. Системные определены внутри среды CLIPS изначально, пользовательские - фрагменты кода, написанные пользователями на CLIPS или С.
Хотя CLIPS не ориентирован на численные вычисления, в нем предусмотрены стандартные математические и арифметические функции: +, *, /, ** (возведение в степень), Abs, Sqrt, Mod, Min, Max. Пример 1: (+ 2 5 8)
Конструкция deffunction позволяет пользователю определять новые функции непосредственно в среде CLIPS.
(deffunction ( ... )


)
Пример 2:
(deffunction hypotenuse (?а ?b) (sqrt (+ (* ?а ?а) (* ?b ?b))) )
Аргументы-переменные должны иметь префикс ?, как это показано в приведенном примере.
Вызовы функций в CLIPS имеют префиксную форму: аргументы стоят после ее названия. Вызов функции производится в скобках: (hypotenuse 7 4)
После открывающейся скобки следует имя функции, затем идут аргументы, каждый из которых отделен одним или несколькими пробелами.
Аргументами функции могут быть данные простых типов, переменные или вызовы других функций.
функция возвращает результат последнего выражения в списке. Иногда выполнение функции имеет побочные эффекты, как в приведенном ниже
примере.
(deffunction init (?day) (reset)
(assert (today is ?day)) )
В результате после запуска функции на выполнение командой CLIPS> (init Sunday)
будет выполнена команда reset и, следовательно, очищена база фактов, а затем в нее будет включен новый факт (today is Sunday).
А в результате запуска функции hypotenuse на выполнение командой CLIPS> (hypotenuse 3 4)
будет выдан известный ответ CLIPS> 5.0
Пример 3 .
(deffunction between(?lb ?value ?ub)
(or (> ?lb ?value) (> '.'value ?ub)))
Эта функция определяет, попало ли заданное целочисленное значение в Диапазон между нижним и верхним пределами.
В некоторых задачах бывает полезным оператор присвоения bind. Например, переменной ?а присваивается значение 4: (bind ?а 4)
закрытия CLIPS будут потеряны. Поэтому текст программы необходимо сохранить в файле. В CLIPS имеется встроенный редактор.
Для загрузки содержимого файла в базу знаний CLIPS, нужно воспользоваться пунктом Load Constructs меню File.
Для того чтобы CLIPS активизировал начальный факт (initial-fact идентификатором F-0) необходимо выбрать Executtion->Reset . Данная команда удаляет существующие факты из списка фактов, включает в списо фактов исходный факт (initial-fact), включает в список фактов все факты описанные в конструкциях (deffacts).
Затем, по команде Executtion->Run CLIPS начнет выполнение всех прави программы. Для сохранения протокола работы программы, а также получен ответа в текстовом файле необходимо сразу после запуска CLIPS выполнит команду File -> TurnDribbleOn и в диалоговом окне ввести имя файла, который будет сохраняться содержимого главного окна CLIPS. Поел окончания работы программы выполнить TumDribbleOff, по этой команд файл для вывода будет закрыт.
2 Лабораторная работа №1. Решение задач на планирование
Цель работы: ознакомление с основными принципами программирования на языке CLIPS, получение навыков работы в оболочке CLIPS, разработка программы на составление планов действий технической системой в заданной
предметной области.
Технические средства: персональный компьютер с операционной системой
Windows 9x/Me/NT/2000/XP.
Программные средства: текстовый редактор (Блокнот, WordPad и т.п.), оболочка языка CLIPS версии 6.2 и выше.
2.1. Задачи на планирование действий
Задачи планировщика - определить последовательность действий модуля решения, например системы управления. Традиционное планирование основано на знаниях, поскольку создание плана требует организации частей знаний и частичных планов в процедуру решения. Планирование используется в экспертных системах при рассуждении о событиях, происходящих во времени. Планирование находит применение в производстве, управлении, робототехнике, в задачах понимания естественного языка.
Планы создаются путем поиска в пространстве возможных действий до тех пор, пока не будет найдена последовательность, необходимая для решения задачи. Это пространство представляет состояния мира, котрые изменяются при выполнении каждого действия. Поиск заканчивается, когда достигается Целевое состояние (описание мира).
2.2. Пример программы по планированию действий робота - "Робот и ящик"
Имеются 2 комнаты - А и В, в комнате А находится робот, в комнате В - "Шик; задача - вытолкнуть ящик в комнату А.
Решим эту задачу с помощью шаблонных фактов. Введем шаблон определяющий местоположение предмета:
(deftemplate in
(slot object (type SYMBOL))
(slot location (type SYMBOL))
)
Слот Object будет задавать название предмета или робота, location название места, где этот предмет или робот находится.
Чтобы задать роботу конкретную цель действий зададим шаблон goal:
(deftemplate goal (slot object (type SYMBOL)) (slot from (type SYMBOL)) (slot to (type SYMBOL)) )
слот object - определяет название объекта, который необходи переместить, слоты from и to определяют откуда и куда.
На основе шаблонов in и goal запишем начальные факты:
(deffacts world
(in (object robot) (location RoomA)) (in (object box) (location RoomB))
(goal (action push) (object box) (from RoomB) (to RoomA))
)
Первый факт соответствует тому, что робот находится в комнате второй, что ящик в комнате В, третий - перетащить ящик из комнаты В в А. Заключительным этапом создания данной программы является создан
правил. В данной задаче необходимо реализовать три правила, которые осуществляли бы следующие действия робота:
1) перемещение робота в комнату, где находится объект;
2) перемещение робота с объектом в комнату, указанную в цели;
3) останов программы если цель достигнута.
Реализуем первое действие:
(defrule move
(goal (object ?X) (from ?Y))
(in (object ?X) (location ?Y))
?robot-position =>
(modify ?robot-position (location ?Y))
)
В данном правиле имеются три предпосылки. В первой предпосылке, использующей шаблон goal задаются значения переменных ?Х и ?Y. Во второй определяется наличие объекта ?Х в комнате ?Y. В третьей предпосылке проверяется, что местоположение робота не соответствует ?Y и запоминается ссылка на данный факт в переменной ?robot-position. Если все предпосылки данного правила истинны, то с помощью оператора modify меняется значение слота location на значение переменной ?Y факта ?robot-position, т. е. робот перемещается в комнату, в которой находится объект, который необходимо переместить.
Аналогично реализуется правило перемещения робота с ящиком, в комнату, указанную в цели:
(defrule push
(goal (object ?X) (from ?Y) (to ?Z))
^object-position '.'robot-position =>
(modify ?robot-position (location ?Z)) (modify ?object-position (location ?Z)) )
В данном случае изменяются два факта, ссылки на которые задаются в переменных ?object-position и ?robot-position: значение слота location меняется на значение переменной ?Z, соответствующей значению куда необходимо переместить предмет роботом.
Останов выполнения программы в CLIPS осуществляется с помощью команды (halt). Условием останова является наличие факта, что предмет, указанный в цели (слот object) находится в комнате, указанной в слоте to:
(defrule stop
(goal (object ?X) (to ?Y))
(in (object ?X) (location ?Y))
=>
(halt) )
Полный текст программы представлен в листинге 1.
Листинг 1. Программа «робот и ящик» ;; ШАБЛОНЫ ;; Шаблон «цель» (deftemplate goal (slot action (type SYMBOL)) (slot object (type SYMBOL)) (slot from (type SYMBOL))
(slot to (type SYMBOL)) )
;; Шаблон "В" (deftemplate in
(slot object (type SYMBOL)) (slot location (type SYMBOL)) )
;; ФАКТЫ
;; Робот в комнате А, ;; ящик в комнате В, ;; цель - вытолкнуть ящик в комнату А. (deffacts world
(in (object robot) (location RoomA)) (in (object box) (location RoomB))
(goal (action push) (object box) (from RoomB) (to RoomA)) )
;;ПРАВИЛА
;; Прекратить процесс, когда цель будет достигнута, (defrule stop
(goal (object ?X) (to ?Y))
(in (object ?X) (location ?Y)) =>
(halt) )
;; Если робот отсутствует в том месте, где находится объект, ;; который нужно передвинуть, ;; переместить туда робот, (defrule move
(goal (object ?X) (from ?Y)) (in (object ?X) (location ?Y))
?robot-position =>
(modify ?robot-position (location ?Y)) )
;; Если робот и объект не в том помещении, ;; которое указано в цели, ;; переместить туда робот и объект, (defrule push
(goal (object ?X) (from ?Y) (to ?Z)) ?object-position ?robot-position =>
(modify ?robot-position (location ?Z)) (modify ?object-position (location ?Z)) )
Чтобы запустить программу в CLIPS необходимо:
1) скопировать текст программы в любой текстовый редактор (редакт CLIPS, Notepad) и сохранить его с расширением clp, например, robot.clp;
2) загрузить этот файл в среду CLIPS с помощью меню File\Load. (Ctrl+L);
3) выполнить команду reset. Для этого либо введите эту команду командной строке интерпретатора:
CLIPS> (reset)
либо выберите в меню команду Execution->Reset (CTRL+U);
4) в меню Execution->Watch установите флажок Rules, чтобы наблюда результат трассировки процесса выполнения;
5) затем запустите интерпретатор. Для этого либо введите эту команду г в командную строку интерпретатора:
CLIPS> (run)
либо выберите в меню команду Execution->Reset (CTRL+R).
2.3. Порядок выполнения работы. Задания
1 Изучение интерфейса оболочки языка CLIPS.
2. Знакомство с основами программирования на языке CLIPS и выполнение примеров из части I данного руководства .
3. Выполнение в режиме отладки (включить просмотр правил и фактов) программы "Робот и ящик" (предварительно набрать исходный текст программы из листинга 1 в текстовом редакторе и сохранить под именем robot.clp, затем загрузить в CLIPS).
4. Модифицировать программу "Робот и ящик" таким образом, чтобы ящик необходимо было передвинуть в комнату С. Выполнить в режиме отладки.
5. Разработать программу на планирование действий технического объекта согласно варианту задания, выданного преподавателем.
Варианты заданий.
В каждой задаче необходимо вводить в базу фактов несколько заданий для робота или процесса, которые должны выполняться последовательно.
1. Авиаперевозки. Организовать перевозку с помощью воздушного грузового транспорта. Следует предусмотреть ситуации загрузки и разгрузки грузов в самолет, взлет, перелет из одного аэропорта в другой в другой, посадку, учет веса груза и грузоподъемность самолета.
2. Шиномонтажная мастерская. Робот должен проводить диагностику и смену колеса с пробитой покрышкой. Для каждой марки автомашины определен свой класс колес. Колес ограниченное количество, если какие-либо колеса отсутствуют, программа должна известить об этом.
3- Планирование действий по построению пирамиды из блоков(А,В,С,....) разного размера и разной формы по заранее определенным правилам Установки, которые задаются в базе фактов.
4. Робот и ящик. Существуют 4 комнаты, выходящие дверями в корид
Робот, который может перемещаться из комнат в коридор и обратно, дви
ящики.
5. Разработать предметную область, связанную с управлением грузов лифтом. Лифт может перемещаться между этажами, согласно вызовам перевозить грузы, учитывая их вес.
6. Автомат по продаже воды. Автомат имеет конечное количе газированной воды и несколько видов сиропа. Выдача воды с сиропом и сиропа выдается в соответствии с номиналом монеты и запросом ( сиропа, с вишневым сиропом, лимонным и т. п.).
7. Музыкальный автомат. Имеется определенное количество пласти" автомат должен по требованию, заданному в базе фактов устанавли нужную пластинку, если такой не имеется в базе, сообщить об э Предусмотреть счетчик времени (каждый шаг выполнения программ окончание определенного количества времени), по окончании врем проигрывания пластинки она должна автоматически убираться.
8. Автомат разлива воды в бутылки. Имеется определенное количество во бутылки заданной емкости. Необходимо разлить воду в бутылки. Авто должен сообщать, что вода закончилась или не хватает емкости, наполнять емкость, если воды меньше, чем объем заданной емкости.
9. Закачка файлов. Имеется список файлов в очереди закачки и их размер, каждый шаг программы закачивается определенное количество байт (квс Если количество байт оставшееся для полного скачивания файла мен чем квота, то остаток должен передаваться другому файлу.
10. Гирлянда. Имеются лампочки различных цветов, формы и т. Необходимо в базе правил задать правила включения и выключе определенных лампочек в момент времени. Под моментом времени счи один шаг программы.
11. Кофе-машина. В кофе-машину загружаются зерна кофе. Машина б определенную порцию зерен, перемалывает, варит кофе и подает
Предусмотреть возможность ввода нескольких сортов кофе, добавление сливок и сахара по запросу. Количество ресурсов (кофе, сахара, сливок, воды) должно быть ограничено, если какое-либо кофе получить не возможно, автомат должен сообщить об этом.
12. Процесс сборки изделия. Имеются детали, которые участвуют в сборке деталей. Каждая деталь должна использоваться в определенной последовательности. Когда изделии собрано, автомат должен переходить к сборке нового изделия. Процесс прекращается только тогда, когда сборка не возможна (закончились или не хватает какой-либо детали).
13. Продажа билетов. Имеется определенное количество билетов на различные мероприятия. Необходимо по запросу и заданному количеству монет выдавать билеты. Автомат должен выдавать сдачу и оповещать, если билеты на запрашиваемое мероприятие закончилось.
14. Библиотека. Необходимо выдавать книги из заданной базы абонентам по запросу. Книга может отсутствовать в библиотеке или быть на руках у другого абонента.
15. Комплексный обед. Имеется меню с ценами. По предъявленным запросам (перечень блюд, закусок и напитков и их количество) составить комплексные обеды и предъявить цену.
Лабораторная работа №2. Решение задач из логики высказываний на CLIPS
3.1. Элементы математической логики. Логика высказываний
При решении логических задач с помощью экспертных систем быв полезным применение аппарата алгебры высказываний, позволяюще представлять факты и правила в виде логических выражений.
Под высказыванием р мы будем понимать всякое утвердительн предложение, относительно которого можно сделать заключение, истинно о или нет. Содержением высказывания не интересуются, интерес представля лишь истинность или ложность высказывания. Будем считать высказывай истинным, если оно равно 1, ложным - если оно равно 0. Над высказывания можно производить логические операции.
3.1.1. Основные операции над высказываниями
Для высказываний X и Y можно определить следующие основы логические операции.
1. Отрицание (—tX) - высказывание, которое истинно тогда и толь тогда, когда X ложно. В разговорной речи высказыванию -X соответству фразы: "не Х\ "неверно, чтоХ\
2. Конъюнщия (XaY) - логическим умножение. Высказывани которое истинно тогда и только тогда, когда истинны оба высказывания, разговорной речи ей соответствует союз "и" (X л Y- "Хк Y').
3. Дизъюнкция (X v К) - логическим сложение. Высказывание, кото ложно тогда и только тогда, когда ложны оба высказывания. В разговори речи ей соответствует союз "или" (X v Y - "Хшп Y").
4. Импликация (X -+Y ) - логическое следование. Высказывай которое ложно тогда и только тогда, когда X - истинно, a Y - ложно, разговорной речи импликации соответствуют следующие высказывания:
только тогда, когда У", "из ^следует Y\ "если А"то Y'. При этом Х-посылка, а
заключение.
5. Эквиваленция (X Таблицей истинности логических операций называется таблица, в которой отражены результаты операций на всех возможных наборах значений высказываний.
Таблица 1. Таблица истинности для логических операций
А в -А Ал В Aw В А-+ В А В
И И л л И И И и
И л л и Л И Л Л
Л и и л Л И и л
л л и и л л и и

При помощи операций возможно создавать комбинации из высказываний. Для сложных высказываний, можно создавать комбинации, построенные из нескольких исходных высказываний посредством применения логических операций —,, л, v, —Их называют формулами алгебры высказываний.
При вычислении по формуле учитывается приоритет логической операции. Перечисленные выше логические операции расположены в порядке убывания приоритета. Изменить порядок логических вычислений можно с помощью расстановки скобок.
Исходные высказывания могут быть постоянными, то есть иметь определенные значения "истина" или "ложь". Если элементарное высказывание не имеет определенного значения, то это переменное высказывание. Например: 1) А: = 'Джек лает ", В: = "Джеклюбит кости "
А л В (Джек лает и любит кости) - это постоянное высказывание 2> А(Х):= "Собака (X) лает ", В(Х):- "Собака (X) любит кости "
С(Х): = А(Х) л В(Х) (Собака с именем X лает и любит кости) - эт переменное высказывание.
Пропозициональной формулой (ПФ) называется логическое выражени содержащее переменные соответствующие логическим высказываниям, 0, 1 константы и логические операции v, v, -», , называем-
пропозициональными связками, скобки (, ) используемые для определе приоритета операций. ПФ определяется индуктивно следующим образом: 1.Отдельно взятая переменная (высказывание) и константа (0, 1) - это П*" 2. Если А и В, составленные из допустимых символов - ПФ, то и -гА, А л В, Av В, А->В, ЛВ - тоже ПФ.
Никаких других ПФ, кроме образованных по правилу 2, нет. Пример
pvq л г -> р - пропозициональная формула р v с/ л г —> v р - не пропозициональная формула
Таблицей истинности для ПФ является перечень значений данной при всех возможных значениях входящих в нее переменных.
Пропозициональная формула называется тавтологией, если на вс значениях входящих в нее переменных она равна 1. Обозначение: |= А пропозициональная формула А есть тавтология.
Приведем ряд тавтологий, могущих оказаться полезными преобразовании высказываний:
Закон двойного отрицания: ]= —.—¦/? р (1) Закон исключенного третьего: |= р v -,р (2) Идемпотентность операций дизъюнкции и конъюнкции: |= р л р р (3) |= р v р р (4)
р из конъюнкции: |= р л q -» р (5) р из дизъюнкции: |= р -> р v q (6)
Коммутативность операций дизъюнкции и конъюнкции: |= р л q • q л р (7) |= р v q q v р (8)
Ассоциативность операций дизъюнкции и конъюнкции: |= (р л q) л р л (q л г) (9) |=(pv?)vro/>v{9vr) (10) Разложение операций дизъюнкции и конъюнкции: |= р v (q л г) (р v q) А (р v г) (11) |= р A (q v г) (р A q) v (р А г) (12) Правила де Моргана: ->(л р) -,р v ~,q (13) |= (v р ) -iр A —,q (14) Закон контрапозиции: |=-> р р -,q (15)
Транзитивность импликации: |= (р —> q) A {q -> г) р —> г (16) Закон косвенного доказательства: |= (-.р —> q) А (—*р -> —iq) —> р (17) Закон разбора случаев: |= (р v q) А (р -> г) A (g -> г) -» г (18) Транзитивность эквиваленции: |= (/? А (д г) -> (/> г) (19) Закон противоположности: |= (/>р->р (22) Представление нуля: (23)
1=0*->-п(р->р) (24)
Представление импликации через дизъюнкцию и отрицание: t=(p-+q)*+(-npvq) (25) Представление эквиваленции:
|= {р о q) и (-Тр vq) л (р v -1 q) (27)
1= iPq)(p/\q)v (-^р л -л) (28) Представление конъюнкции: |= р д q -к/) (29) Представление дизъюнкции: |= р v q (-.р -> q) (30)
3.2. Примеры программ логического доказательства
Рассмотрим задачу 1. Кто из учеников А, В, С и D играет, а кто не играет шахматы, если известно, что:
1) Если А или В играет, то С не играет.
2) Если В не играет, то играют С и D.
3) С играет.
Пусть высказывание Р истинно, если ученик Р играет в шахматы Условия 1-3 истинны, т.е. значения этих выражений равны единице. В это случае мы приходим к системе логических уравнений: AV В —> —IC = 1 (1) -iB -> С л ?> = 1 (2) С = 1 (3)
Составим таблицу истинности для этих двух выражений:
Таблица 2. Неполная таблица истинности для задачи 1
A В С D AV В —> —IC —IB AD
1 1 1 1 0 1
1 1 1 0 0 1
1 0 1 1 0 1
I 0 1 0 0 0
0 1 1 1 0 1
0 1 1 0 0 1
0 0 1 1 1 1
0 0 1 0 1 0

Так как из условия известно, что ученик С играет, то в данном случае достаточно рассмотреть неполную таблицу истинности, а именно только те случаи когда С = 1. Из таблицы мы можем увидеть единственное решение нашей задачи, когда условия (1) и (2) одновременно истинны - А= 0, В = 0,
Также пользуясь результатами таблицы истинности можно, можно написать небольшую программу на CLIPS, которая представляет наши вычисления в виде манипуляций фактами по определенным правилам.
В начале программы у нас всего один факт - ученик С играет в шахматы: (deffacts situation (С is playing chess) )
Из табилцы истинности видно, что если С = 1, то уравнение (1) истинно тогда и только тогда, когда А и В одновременно ложны. Можно написать следующее правило: (defrule rulel
(С is playing chess)
=>
(assert (A isn't playing chess)) (assert (B isn't playing chess)) )
Из таблицы истинности и уравнения (2) видно, что если В ложь, то истинны С и D, если С или D ложно, то В истинно. При других вариантах значений А, В, С выражение либо ложно, либо вызывает неопределенность, например, из фактов, что С и D истинны не возможно определить истинно В или ложно. Выпишем два соответствующих правила: (defrule rule_2_B_is_false (В
isn't playing chess) (assert (D is playing chess))
(defrule rule_2_D_is_false
(D isn't playing chess)
=>
(assert (B is playing chess)) )
Конечно, правило rule_2_D_is_false никогда не выполнится, так ка программе нет правил, которые порождали бы факт, соответствую продукции данного правила, но оно приведено в данном примере для полн решения поставленной задачи в CLIPS.
Программа останавливается, когда про всех учеников что-ниб выяснено:
(defrule stop (А ? playing chess) (В ? playing chess) (С ? playing chess)
(D ? playing chess)
=>
(halt) )
Полный текст программы представлен в листинге 2.
Листинг 2. Программа задачи 1. «кто играет в шахматы?» ;;из условия известно, что С - играет (deffacts situation (С is playing chess) )
;;из первого высказывания и факта, что С - играет выясняем,
•что А и В не играют (defrule rulej
(С is playing chess)
=>
(assert (A isn't playing chess)) (assert (B isn't playing chess))
)
;;из второго высказывания и факта, что В не играет выяснаем, ;;что D играет (С - играет, известно из условия) (defrule rule_2_B_is_false
(В isn't playing chess)
=>
(assert (D is playing chess)) )
;;из второго высказывания и факта, что D не играет выяснаем, ; ;что В играет (С - играет, известно из условия) ;;данное правило выполняться не будет никогда!!!! (defrule rule_2_D_is_false
(D isn't playing chess) =>
(assert (B is playing chess)) )
^останавливаемся после того, когда все про всех выясним
(defrule stop
(А ? playing chess)
(В ? playing chess)
(С ? playing chess)
(D ? playing chess)
=>
(halt) )
Рассмотрим задачу 2. Угон машины. Следователь допрашивает 4-х гангстеров по делу о похищении автомобиля.
Джек: Если Том не угонял автомобиль, то его угнал Боб Боб: Если Джек не угонял, то его угнал Том Фред: Если Том не угонял, то его угнал Джек Том: Если Боб не угонял, то его угнал я
Выяснилось, что Боб солгал, а Том сказал правду. Правдивы ли показан Джека и Фреда? Кто угнал машину?
Представим данные высказывания в виде логических выражений, где D, F, Т- Джек, Боб, Фред и Том соответственно: Джек: Т —> В Боб: -,D-»7* Фред: -,Г->?) Том: -iB-+T
Используя представление импликации через дизъюнкцию и отрицание (2 (см. п. 3.1.1) можно убедиться, что показания Джека и Тома, Боба и Фре эквивалентны:
Джек: —1Г-> 5 = —>(—iJ)vS = JvS Том: —,В —> Г = —i(-iS) v 7" = В v Г
Боб: -vD -» Г = -,(-,?>) v Т = D v Т Фред: -,r->D = -,(-1r)vD = rvD Воспользуемся этим при написании программы на CLIPS. Для решения данной задачи создадим шаблон: (deftemplate gangster
(slot name (type SYMBOL))
(slot guilty (type SYMBOL) (default Unk))
(slot truthful (type SYMBOL) (default Unk))
)
В слоте name будет хранится имя подозреваемого, guilty будет определять виновен или нет (соответствие истинным или ложным значениям простого высказывания), truthful - определяет правдиво или ложно показание. Слоты guilty и truthful по умолчанию определяется как Unk, что означает неопределенность. В дальнейшем это будет использовано, чтобы исключить повторное выполнение правил, если значение соответствующего слота уже было определено (Yes или No).
Используя полученный шаблон составим базу фактов в соответствии с условием задачи:
(deffacts content (gangster (name Jack)) (gangster (name Bob)(truthfuI No)) (gangster (name Fred)(guilty No)) (gangster (name Tom)(truthful Yes))
)
Во всех четырех высказывания фигурируют только имена Тома, Джека и Боба. Следовательно, без нарушения условия задачи можно установить, что Фред не виновен - (gangster (name Fred)(guilty No)).
Так как показания Джека и Тома эквивалентны, то рассмотрим их вместе. Если Джек или Том говорит правду и Том невиновен, то виновен Боб, если не виновен Боб, то виновен - Том. Соответствующие правила будут следующие:
(defrule Jack_Tom_truthful_Tom_not_guiIty (gangster (name Jack|Tom) (truthful Yes)) (gangster (name Tom) (guilty No)) ?Bob (modify ?Bob(guilty Yes))
(defrule Jack_Tom_truthful_Bob_not_guilty (gangster (name Jack|Tom) (truthful Yes)) (gangster (name Bob) (guilty No))
?Tom =>
(modify ?Tom(guilty Yes))
)
Обратите внимание, что в первой предпосылке данных правил в с name используется связка |, что означает истинность предпосылки если в будет факт у которого значение слота name будет иметь значение Jack или и truthful - Yes.
Если Том или Джек сказали не правду, то Том и Боб не виновны: (defrule Jack_Tom_not_truthful (gangster (name Jack|Tom) (truthfiil No))
?X =>
(modify ?X(guilty No))
)
В данном правиле также используется связка | в обоих предпосы Данное правило применимо как для Боба, так и Тома, если значение с guilty равно Unk у соответствующих фактов.
Других правил на основании высказываний Джека и Тома и изв фактов о виновности или невиновности Тома и Боба построить не возмо так как они несут неопределенность. Например, Если известно, что Джек Том сказали правду и Том виновен, Боб может быть как виновен, невиновен, и наоборот: если Боб виновен, то виновность Тома из показ Джека и Тома определить не возможно.
Аналогично выводятся правила относительно показаний Боба и Фреда: (defrule Bob_Fred_tmthful_Jack_not_guilty (gangster (name Bob|Fred) (truthful Yes)) (gangster (name Jack) (guilty No))
?Tom =>
(modify ?Tom(guilty Yes))
)
(defrule Bob_Fred_truthful_Tom_not_guilty (gangster (name Bob|Fred) (truthful Yes)) (gangster (name Tom) (guilty No))
?Jack =>
(modify ?Jack(guilty Yes))
)
(defrule Bob_Fred_not_truthful (gangster (name Bob|Fred) (truthful No))
?X =>
(modify ?X(guilty No))
)
Все предыдущие правила основывались на том, что истинность или ложность высказываний известна, но в задаче есть высказывания, истинность или ложность которых необходимо установить. Для этого составим соответствующие правила: (defrule Jack_Tom_isJruthful ?X (modify ?X(truthful Yes))
)
(defrule JackTom_isnottruthfi.il ?X (gangster(name Bob) (guilty No))
=>
(modify ?X(truthful No))
)
(defrule Bob_Fred_is_truthful ?X (gangster(name Tom|Jack) (guilty Yes))
=>
(modify ?X(truthful Yes))
)
(defrule Bob_Fred_is_not_truthful ?X (gangster(name Jack) (guilty No))
=>
(modify ?X(truthful No))
)
Данные правила построены в соответствии с логическими выражения построенными на высказываниях из условия задачи. Например, показания То" и Джека истины, если виновен Том или Боб, а если Тим и Боб не виновны, Том и Джек сказали неправду.
Если про всех все известно, то программа прекращает работу: (defrule stop
(gangster (name Jack) (guilty -Unk) (truthful -Unk)) (gangster (name Bob) (guilty -Unk) (truthful -Unk)) (gangster (name Fred) (guilty -Unk) (truthful -Unk))
(gangster (name Tom) (guilty -Unk) (truthful -Unk))
=>
(halt)
)
Полный текст программы приведен в листинге 3.
Листинг 3. Программа решения задачи 2. «Кто угнал автомобиль?» ;;шаблон
(deftemplate gangster (slot name (type SYMBOL)); ;имя (slot guilty (type SYMBOL) (default Шк));;виновность (slot truthful (type SYMBOL) (default Шк));;истинно ли высказывание
)
; вводятся факты в соответствии с условием задачи (deffacts content (gangster (name Jack)) (gangster (name Bob)(truthful No)) (gangster (name Fred)(guilty №));;Фред не участвовал (gangster (name Tom)(truthful Yes))
)
..останавливаемся когда про всех все известно (defrule stop
(gangster (name Jack) (guilty -Unk) (truthful -Unk))
(gangster (name Bob) (guilty -Unk) (truthful -Unk)) (gangster (name Fred) (guilty -Unk) (truthful -Unk))
(gangster (name Tom) (guilty -Unk) (truthful -Unk))
=>
(halt)
)
;;в соответствии с показаниями Джека и Тома
(defrule Jack_Tom_truthful_l (gangster (name Jack|Tom) (truthful Yes)) (gangster (name Tom) (guilty No))
?Bob =>
(modify ?Bob(guilty Yes))
)
(defrule Jack_Tom_truthful_2 (gangster (name Jack|Tom) (truthful Yes)) (gangster (name Bob) (guilty No))
?Tom =>
(modify ?Tom(guilty Yes))
)
(defrule Jack_Tom_not_truthful (gangster (name Jack|Tom) (truthful No))
?X =>
(modify ?X(guilty No)) • в соответствии с показаниями Боба и Фреда
(defrule Bob_Fred_truthful_l (gangster (name Bob|Fred) (truthful Yes)) (gangster (name Jack) (guilty No))
?Tom =>
(modify ?Tom(guilty Yes))
)
(defrule Bob_Fred_truthful_2 (gangster (name Bob|Fred) (truthful Yes)) (gangster (name Tom) (guilty No))
?Jack =>
(modify ?Jack(guilty Yes))
)
(defrule Bob_Fred_not_truthful (gangster (name Bob|Fred) (truthful No))
?X =>
(modify ?X(guilty No))
)
;;Выясняем кто говорит правду, а кто нет (defrule Jack_Tom_is Jruthfbl
?X (gangster(name Tom|Bob) (guilty Yes))
=>
(modify ?X(truthful Yes))
)
(defrule Jack_Tom_is_not_truthfii] ?X (gangster(name Bob) (guilty No))
=>
(modify ?X(truthful No))
)
(defrule Bob_Fred_is_truthful ?X (gangster(name Tom|Jack) (guilty Yes))
=>
(modify ?X(truthful Yes))
)
(defrule Bob_Fred_is_not_truthful ?X (gangster(name Jack) (guilty No))
=>
(modify ?X(truthful No))
)
3.3. Варианты заданий
1 В школе было разбито стекло. В содеянном были заподозрены четыре ученика: Миша, Леня, Толя и Дима. Вот что они сказали в кабинете директора:
Леня: Я не виноват. Я даже не подходил к окну. Миша знает, кто это сделал.
Дима: Стекло разбил не я. С Мишей я не был знаком до поступления в школу. Это сделал Толя.
Толя: Я не виновен. Это сделал Миша. Дима говорит неправду, утверждая, что я разбил стекло.
Миша: Я не виноват. Стекло разбил Леня. Дима может поручиться за меня, т.к. знает меня очень давно.
При дальнейших расспросах ребята сознались, что 2 фразы из сказанных ими - истинны, а одна, соответственно, ложна. Требуется выяснить, кто разбил стекло.
2. Определите, кто из подозреваемых участвовал в преступлении, если известно:
a) если Иванов не участвовал или Петров участвовал, то Сидоров участвовал;
b) если Иванов не участвовал, то Сидоров не участвовал.
3. Аня, Вика и Сергей решили пойти в кино. Учитель, хорошо знавший ребят, высказал предположения:
a) Аня пойдет в кино только тогда, когда пойдут Вика и Сергей;
b) Аня и Сергей пойдут в кино вместе или же оба останутся дома;
c) чтобы Сергей пошел в кино необходимо чтобы пошла Вика.
Когда ребята пошли в кино, оказалось, что учитель немного ошибся: из
трех его утверждений истинными оказались только два. Кто из ребят пошел в кино?
Виктор, Роман, Леонид и Сергей заняли на олимпиаде по физике четыре первых места. Когда их спросили о распределении мест, они дали три
ответа:
a) Сергей - первый, Роман - второй;
b) Сергей - второй, Виктор - третий;
c) Леонид - второй, Виктор - четвертый.
Известно, что в каждом ответе только одно утверждение истинно. Как распределились места?
5. Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения: Алеша: Это сосуд греческий и изготовлен в V веке.
Боря: Это сосуд финикийский и изготовлен в III веке.
Гриша: Это сосуд не греческий и изготовлен в IV веке.
Учитель истории сказал ребятам, что каждый из них прав только в одном
из двух предположений. Где и в каком веке изготовлен сосуд?
6. В нарушении правил обмена валюты подозреваются четыре работника банка - А, В, С, D. Известно, что:
a) если А нарушил, то и В нарушил правила обмена валюты;
b) если В нарушил, то и С нарушил или А не нарушал;
c) если D не нарушил, то А нарушил, а С не нарушал;
d) если D нарушил, то и А нарушил. Кто из подозреваемых нарушил правила обмена валюты?
7. Богданову, Демидову и Смирнову предъявлено обвинение в ограблении ювелирного магазина. С места преступления они скрылись на автомобиле. На следствии Богданов сказал, что они уехали на синем «Москвиче», Демидов сказал, что это была черная «Волга», Смирнов утверждал, что эт были «Жигули», но не синие. Известно, что каждый из них правильно назвал либо марку автомобиля, либо цвет. Определите марку автомобиля И ее цвет.
8. Четыре подруги Аня, Маша, Настя, Вика пришли в магазин. Продавец сказал, что осталось только четыре платья: Красное, Розовое, Оранжевое, Синее.
a) Красное платье купила Аня, а розовое - Маша;
b) Аня взяла розовое платье, а Вика купила оранжевое;
c) Настя забрала розовое, а Вика - синее платье.
Кто купил синее платье и какое платье выбрала Вика, если известно, что половина каждого утверждения истинна, а половина - ложь.
9. В олимпиаде по биологии участвовало пять девушек: Алла, Нина, Вика, Рита, Соня. Об итогах олимпиады имеется пять высказываний:
a) первое место заняла Алла, а Рита оказалась третьей;
b) пятой была Вика, а вот Нина поднялась на первое место;
c) первое место заняла Соня, а вот Вика была второй;
d) Рита на последнем, пятом, месте, а Нина была предпоследней;
e) Нина была четвертой, а первой - Алла.
Кто занял первое место и на каком месте была Алла, если известно, что в каждом высказывании одно утверждение правильное, а другое - нет.
10. Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:
a) Макс победит, Билл - второй;
b) Билл - третий, Ник - первый;
c) Макс - последний, а первый - Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
11. Классный руководитель пожаловался директору, что у него в классе появилась компания из Зх учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто - нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля: Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша. Сзща: Это был мой первый прогул этого предмета.
Миша: Все, что говорит Коля - правда. Определите, кто из них кто.
12. Однажды Алиса повстречала Льва и Единорога, отдыхавших по деревом. Странные это были существа. Лев лгал по понедельника вторникам и средам и говорил правду во все остальные дни неде~ Единорог же вел себя иначе: он лгал по четвергам, пятницам и субботам говорил правду во все остальные дни недели. Они высказали следующ- утверждения:
Лев: «Вчера был один из дней, когда я лгу».
Единорог: « Вчера был один из дней, когда я тоже лгу».
Из этих двух высказываний Алиса сумела вывести, какой день недели бы
вчера. Что это был за день?
13. Покупатель в каждом из магазинов А, В, С и D сделал по одной покуп и приобрел джойстик, дискеты, бумагу и картридж. Известно, что:
a) джойстик и картридж купил не в А;
b) в С зашел когда уже купил дискеты и бумагу;
c) в D не было ни картриджа, ни дискет;
d) в В приехал, когда джойстик уже был куплен;
e) из D уходил без джойстика.
Необходимо определить в каком магазине были куплены дискеты.
14. Три подразделения А, В, С компании хотят получить по итогам квартал максимальную прибыль. Были сделаны следующие прогнозы:
a) если А получит максимальную прибыль, то максимальную прибыл получат также В и С;
b) либо А и С получат максимальную прибыль одновременно, ли одновременно не получат;
c) для того, чтобы С получило максимальную прибыль, необходим чтобы и В получило максимальную прибыль.
По завершении квартала оказалось, что один из трех прогнозов ложе Какие из названных подразделений получили максимальную прибыль?
15. Есть 2 комнаты. В каждой из комнат будет находиться либо принцесса, либо тиф, хотя вполне может статься, что сразу в обеих комнатах обнаружится по тигру или там окажутся одни лишь принцессы. Уздник должен угадать, кто находится в каждой комнате. Если он угадает, то женится на принцессе, если нет, то его растерзает тигр. На табличках, прикрепленных к дверям каждой из комнат, написано:
I. В этой комнате находится принцесса, а в другой комнате сидит тигр И. В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр
Причем, известно, что на одной табличке написана правда, а на другой - ложь.
А вы на месте узника, какую бы дверь открыли?
16. В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые таблички. На первой повесили табличку: «По крайней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории - табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу известно только, что надписи либо истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.
17. Фамилии командира взвода, заместителя командира взвода и командиров трех отделений - Антипов, Борисов, Васильев, Григорьев, Дмитриев. Фамилии командиров первого и второго отделений начинаются на F и L и они решили подружиться. Дмитриев недавно узнал, что командир взвода и командир второго отделения - двоюродный братья. Григорьев дружит с командиром и его заместителем. У Васильева нет двоюродных братьев. Определите фамилии командира, заместителя командира и командиров отделений.?
Если представить пространство поиска в игре в восемь в виде дерева, g(n) - это глубина от первой вершины до п-й вершины. В качестве h(n можно, например, выбрать число шашек, стоящих не на своих мес~ Стратегия прохождения вершин - по минимуму оценочной функции.

Рис 1. Поиск решения в игре «восемь» по алгоритму А* ,
Исходная вершина
2 8 3
1 6 4
7 5

2 8 3
1 4
7 6 5

2 3
1 1 8 4
7 6 5
8 з!
2 1 4
7 6 5
0
1 2 3
7 8 4
6 5
На рис. 1. показан результат поиска. Выбираем вершину с наименьшим и значений оценочной функции, указанных цифрами в кружочках, применяв оператор и раскрываем вершину, затем создаем дочерние вершины (при это( не возвращаемся к уже появившимся вершинам). Повторяем эту процедуру д целевого состояния.
2 8 3
1 6 4
7 5

2 8 3
1 4
7 6 5

2 8 3
N 7 1 4
6 5
0

1 2 3
8 4
7 6 5
Целевая вершина ^Т^

Результаты применения оценочной функции приведены на рис 4.1. Значе) f для каждой вершины заключены в кружок. Видно, что найден решаюИ
2 Если OPEN := {}, то прекратить выполнение. Пути к целевому состоянию на графе не существует.
3. Удалить из списка OPEN узел п, для которого f(n) 4. Сформировать список очередных узлов, в который возможен переход из узла п, и удалить из него все узлы, образующие петли; с каждым из оставшихся связать указатель на узел п.
5. Если в сформированном списке очередных узлов присутствует g, то завершить выполнение. Сформировать результат - путь, порожденный прослеживанием указателей от узла g до узла s.
6. В противном случае для каждого очередного узла п', включенного в список выполнить следующую последовательность операций:
6.1 Вычислить f{ri).
6.2 Если п' не присутствует ни в списке OPEN, ни в списке CLOSED, добавить его в список, присоединить к нему оценку /(и') и установить обратный указатель на узел п.
6.3 Если п' уже присутствует в списке OPEN или в списке CLOSED, сравнить новое значение /(и') = new с прежним /(п') = old.
6.4 Если old 6.5 Если old > new, заменить новым узлом прежний в списке, причем, если прежний узел был в списке CLOSED, перенести его в список OPEN.
4.2. Пример решения задачи поиска в пространстве состояний
Возьмем классическую головоломку - игру в "Восемь". В ней принимает участие 8 пронумерованных фишек, которые могут перемещаться по игровому полю 3x3. Цель состоит в том, чтобы из некоторого случайного расположения фишек перейти к упорядоченному.?
4. Лабораторная работа №3. Реализация эвристических поисковых алгоритмов на примере алгоритма А*
4.1. Эвристический алгоритм поиска в пространстве состояний
Большинство поисковых задач можно сформулировать как задачи поиск пространстве состояний пути от исходного состояния заданной задачи целевого состояния путем повторения возможных преобразований. При э~ для организации поиска в пространстве состояний удобно использовать дере поиска (или его более общую форму - граф).
Одним из подобных алгоритмов поиска является т.н. алгоритм А*, г используются априорные оценки стоимости пути до целевого состояния, обеспечивает высокую эффективность поиска.
Основная идея алгоритма состоит в использовании для каждого узла п графе пространства состояний оценочной функции вида f(n) = g(n) + h(n Здесь g(rt) соответствует расстоянию на графе от узла п до начально состояния, а Ып) - оценка расстояния от узла п до узла, представляюще конечное (целевое) состояние. Чем меньше значение оценочной функции /(я тем "лучше", т.е. узел п лежит на более коротком пути от исходного состоян к целевому. Идея алгоритма состоит в том, чтобы с помощью /(«) отыска кратчайший путь на графе от исходного состояния к целевому.
Алгоритм.
Введем следующие обозначения: s - узел начального состояния; g— узел конечного (целевого) состояния; OPEN- список выбранных, но необработанных узлов; CLOSED - список обработанных узлов.
Шаги: 1. OPEN ~{s}.
путь, но использование оценочной функции позволило раскрыть значительно меньше вершин чем при полном поиске на графе.
При реализации решения данной задачи на CLIPS необходимо будет создать шаблон ситуации игры:
(deftemplate Field (slot LeftTop(type NUMBER)) (slot MiddleTop(type NUMBER)) (slot RightTop(type NUMBER)) (slot LeftMiddle(type NUMBER)) (slot MiddleMiddle(type NUMBER)) (slot RightMiddle(type NUMBER)) (slot Lefffiottom(type NUMBER)) (slot MiddleBottom(type NUMBER)) (slot RightBottom(type NUMBER)) (slot Level(type NUMBER)) (slot Id(type NUMBER) (default 0)) (slot State(type NUMBER) (default 0)) (slot From (type NUMBER)) (slot Exp (type NUMBER))
)
Слоты LeftTop, MiddleTop, RightTop, LeftMiddle, MiddleMiddle, RightMiddle, LeftBottom, MiddleBottom и RightBottom являются ячейками игрового поля, в которых задаются номера соответствующих фишек. Если поле пустое, то значение соответствующего ему слота будет равно 0. Level - определяет число шагов от начальной ситуации к текущей. Id - уникальный номер состояния. State - определяет принадлежность данной ситуации множеству OPEN если значение О, CLOSED - значение 1, если ситуация является промежуточной на пути к решению, то значение данному слоту будет присваиваться 2 (определяется, когда цель будет достигнута). From - Id итуации, из которой возможен переход в данное состояние. Ехр - значение
целевой функции для данной ситуации.
Так как Id каждой ситуации должно быть уникальным, то целесообр, присваивать новой ситуации на единицу больший Id, чем у предыдущ- Чтобы хранить номер предыдущей ситуации используем глобаль переменную и соответствующую функцию: (defglobal ?*Id* = О
)
(deffunction Get_Id() (bind ?*Id* (+ ?*Id* 1)) ?*Id*
)
Для вычисления значения целевой функции ситуации необходимо ч~ шагов от начальной ситуации к текущей и номера фишек на каждой позиц
(deffunction W(?Level ?LeftTop ?MiddleTop ?RightTop ?RightMi ?RightBottom ?MiddleBottom ?LeftBottom ?LeftMiddle) (bind ?a ?Level) (if (not (= '.'LeftTop 1)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?MiddleTop 2)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?RightTop 3)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?RightMiddle 4)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?RightBottom 5)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?MiddleBottom 6)) then (bind ?a (+ 1 ?a))
)
(if (not (= ? Left Bottom 7)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?LeftMiddle 8)) then (bind ?a (+ 1 ?a))
)
?a
)
В базу фактов помещаем начальную ситуацию и инициализируем минимум:
(deffacts start
(min (W 028345071)) (Field (LeftTop 2) (MiddleTop 8) (RightTop 3) (LeftMiddle 1) (MiddleMiddle 6) (RightMiddle 4) (LeftBottom 7) (MiddleBottom 0) (RightBottom 5) (Level 0) (From 0) (Exp (W 0 2 8 3 4 5 0 7 1)) (Id (Get_Id))
)
)
Далее необходимо создать правила для следующих действий:
1) Если решений найдено, то выделить его.
2) Удалить ситуации, которые не являются промежуточными между начальной и конечной ситуацией.
3) Останов программы если найдено решение или решений нет.
4) Удаление повторяющихся ситуаций.
5) Поиск min - минимального значения из значений целевой функции
ситуаций множества OPEN.
6) Порождение новых всевозможных ситуаций из текущего, значен целевой функции которого равна min.
Обратите внимание, что список действий составлен в порядке приорит т. е. прежде чем приступить к следующему шагу необходимо выполн предыдущий. Аналогично в программе будут расставлены приоритеты соответствующих правил.
Считается, что решение найдено если на каком-то этапе в программе бы порождена ситуация соответствующая конечной. В этом случае необходи выделить все промежуточные ситуации от начальной до конечной. Дани действия выполняются в следующих правилах:
(defrule startselectanswer (declare (salience 500))
?f (LeftBottom 7) (MiddleBottom 6) (RightBottom 5) (State -2) (From ?Id))
=>
(modify ?f(State 2))
)
(defrule select_answer (declare (salience 500)) (Field (State 2) (From ?Id))
?f =>
(modify ?f(State 2))
)
В первом правиле помечается ситуация, соответствующая конечной, а втором с помощью значения в слоте From помеченной ситуации ищ непомеченная ситуация.
Если предыдущие правила не выполнимы и решение найдено, то необходимо удалить лишнее: (defrule deletejnotanswer (declare (salience 400)) (Field (State 2))
?f =>
(retract ?f)
)
Первая предпосылка гарантирует, что действие данного правила будет выполнено только в том случае, если решение найдено, вторая позволяет выбрать для удаления правила не соответствующие решению.
Возможность останова программы реализуем в следующих правилах: (defrule Stopl (declare (salience 200))
(not (Fieid(State 0j2)))
=>
(halt)
(printout t "no solutions" crlf)
)
(defrule Stop_2 (declare (salience 200))
(Field(State 2))
=>
(halt)
(printout t "fined solution" crlf)
)
Действия первого правила выполняются, если решение не найдено: в базе фактов нет ситуаций помеченных 0 или 2. Второе правило выполняется, если
решение найдено.
Для удаления повторяющихся ситуаций создадим правило: (defrule movecircle (declare (salience 1000)) (Field (Exp ?X)) ?Field2 (test ( =>
(retract ?Field2)
)
Обратите внимание на предпосылку (test ( Для поиска минимального значения создадим правило, которое бу выполняться, когда будет существовать ситуация из множества OPEN которой значение целевой функции меньше заданной в min: (defrule findmin (declare (salience 150)) ?fmin (Field (Exp ?E& :( =>
(retract ?fmin) (assert (min ?E)) )
Для порождения новых ситуаций создадим 9 правил, каждое из кото- будет соответствовать местонахождению пустого поля. Так как принцип реализации идентичный, рассмотрим одно из них (остальные правила см листинге 3):
(defrule make_new_path_RightBottom (declare (salience 100)) ?fmin (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom 0) (Exp ?E& :(= ?E
?min)))
=>
(modify ?f(State 1))
(bind ?a (W (+ ?L 1) ?LT ?MT ?RT 0 ?RM ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop 7LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle 0) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RM) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Get_Id))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom 0) (RightBottom ?MB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?RM ?MB 0 ?LB ?LM)) (Id (Get_Id)) )
)
)
В каждом правиле выполняются следующие действия:
• помечается выбранная ситуация как принадлежащая множеству CLOSED.
• создаются новые всевозможные ситуации.
• запоминается значение целевой функции одной из новых ситуаций (инициализация поиска min).
Полный текст программы приведен в листинге 4.
Листинг 4. Программа поиска решения для игры в «восемь» ; задается шаблон в соответствии с квадратом 3x3 (deftemplate Field (slot LeftTop(type NUMBER)) (slot MiddleTop(type NUMBER)) (slot RightTop(type NUMBER)) (slot LeftMiddle(type NUMBER)) (slot MiddleMiddle(type NUMBER)) (slot RightMiddle(type NUMBER)) (slot LeftBottom(type NUMBER)) (slot MiddleBottom(type NUMBER)) (slot RightBottom(type NUMBER)) (slot Level(type NUMBER));;3aflaeT уровень в дереве (slot Id(type NUMBER) (default 0))
(slot State(type NUMBER) (default 0));;0 - не рассматривалось, I рассмотрено 2 - соответствует решению (slot From (type NUMBER))
(slot Exp (type NUMBER));;3Ha4eHHe целевой функции
)
;глобальная переменная (defglobal ?*ld* = 0
)
; целевая функция
(deffunction W(?Level ?LeftTop ?MiddleTop ?RightTop ?RightMiddl ?RightBottom ?MiddleBottom ?LeftBottom ?LeftMiddle) (bind ?a ?Level) (if (not (= ?LeftTop 1)) then
(bind ?a (+ 1 ?a))
)
(if (not (= ?MiddleTop 2)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?RightTop 3)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?RightMiddle 4)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?RightBottom 5)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?MiddleBottom 6)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?LeftBottom 7)) then (bind ?a (+ 1 ?a))
)
(if (not (= ?LeftMiddle 8)) then (bind ?a (+ 1 ?a))
)
?a
)
«определяет идентификатор (чтобы можно найти элементы последовательности) (deffunction Get_Id()
(bind ?*Id* (+ ?*Id* 1))
?*Id*
;;задаем начальное положение (deffacts start (min (W 02834507 1))
(Field (LeftTop 2) (MiddleTop 8) (RightTop 3) (LeftMiddle 1) (MiddleMiddle 6) (RightMiddle 4) (LeftBottom 7) (MiddleBottom 0) (RightBottom 5) (Level 0);;это корень дерева (From 0) (Exp (W 0 2 8 3 4 5 0 7 1)) (Id (Get_Id))
)
)
;;удаляем правила, которые встретились повторно (defrule move_circle (declare (salience 1000)) (Field (Exp ?Х));;первый факт
?Field2 (test ( =>
(retract ?Field2) (printout t "delete rule" crlf)
)
;;выбираем узлы из множества Open, и создаем соответствующие пути
него
;;для этого создается 9 правил с одинаковым приоритетом, что д случайность
(defrule make_new_path_LeftTop
(declare (salience 100))
?fmin ?f (LeftTop 0) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(= ?E
?min)))
=>
(printout t ?min "" (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ 1 ?L) ?MT 0 ?RT ?RM ?RB ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?MT) (MiddleTop 0) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Get_Id))
)
)
(assert (Field (LeftTop ?LM) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle 0) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LM ?MT ?RT ?RM ?RB ?MB ?LB 0)) (Id (Getld)) )
)
(printout t "LeftTop" crlf)
)
(defrule make_new_path_MiddleTop
(declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop 0) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(
?min)))
=>
(printout t ?min " " (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ 1 ?L) 0 ?LT ?RT ?RM ?RB ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop 0) (MiddleTop ?LT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Get_Id))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MM) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle 0) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MM ?RT ?RB ?MB ?LB ?LM)) (Id (Getld)) )
)
(assert (Field (LeftTop ?LT) (MiddleTop ?RT) (RightTop 0)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?RT 0 ?RM
?MB ?LB ?LM)) (Id (Get ld)) )
)
(printout t "MiddleTop" crlf)
)
(defrule make_new_path_RightTop (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop 0) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(= ?E
?min)))
=>
(printout t ?min "" (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ 1 ?L) ?LT 0 ?MT ?RM ?RB ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?LT) (MiddleTop 0) (RightTop ?MT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Getjd))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RM)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle 0) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MT ?RM 0 ?RB
?MB ?LB ?LM)) (Id (Get ld)) )
)
(printout t "RightTop" crlf)
)
(defrule make_new_path_LeftMiddle (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle 0) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(
?min)))
=>
(printout t ?min " " (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ 1 ?L) 0 ?MT ?RT ?RM ?RB ?MB ?LB ?LT)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop 0) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LT) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Get_Id))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?MM) (MiddleMiddle 0) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MT ?RT
?RB ?MB ?LB ?MM)) (Id (Getjd)) )
)
(assert (Field (LeftTop ?LT) (MiddleTop ?М'Г) (RightTop ?RT)
(LeftMiddle ?LB) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom 0) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MT ?RT ?RM ?RB ?MB 0 ?LB)) (Id (Get ld)) )
)
(printout t "LeftMiddle" crlf)
)
(defrule make_new_path_MiddleMiddle (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle 0) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(= ?E
?min)))
=>
(printout t ?min " " (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ 1 ?L) ?LT 0 ?RT ?RM ?RB ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?LT) (MiddleTop 0) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MT) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB)
(Level (+ ?L 1)) (From ?ld) (Exp ?a) (Id (Getjd))
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?RM) (RightMiddle 0) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MT ?RT 0 ?
?MB ?LB ?LM)) (Id (Get ld)) )
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MB) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom 0) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MT ?RT ?
?RB 0 ?LB ?LM)) (Id (Get ld)) )
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle 0) (MiddleMiddle ?LM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ 1 ?L) ?LT ?MT ?RT ?
?RB ?MB ?LB 0)) (Id (Get ld)) )
)
(printout t "MiddleMiddle" crlf)
)
(defrule make_new_path_RightMiddle (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle 0) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(= ?E
?min)))
=>
(printout t ?min "" (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ ?L 1) ?LT ?MT 0 ?RT ?RB ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop 0)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RT) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Getjd))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle 0) (RightMiddle ?MM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?MM ?RB ?MB ?LB ?LM)) (Id (Get ld)) )
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RB) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom 0) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?RB 0 ?MB ?LB ?LM)) (Id (Getjd)) )
(printout t "RightMiddle" crlf)
(defrule make_new_path_Lefffiottom (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom 0) (MiddleBottom ?MB) (RightBottom ?RB) (Exp ?E& :(
?min)))
=>
(printout t ?min "" (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ ?L 1) ?LT ?MT ?RT ?RM ?RB ?MB ?LM 0)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle 0) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LM) (MiddleBottom ?MB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Getjd))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?MB) (MiddleBottom 0) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?RB 0 ?MB ?LM)) (Id (Getjd)) )
)
(printout t "LeftBottom" crlf)
)
(defrule make_new_path_MiddleBottom (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom 0) (RightBottom ?RB) (Exp ?E& :(= ?E
?min)))
=>
(printout t ?min "" (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ ?L 1) ?LT ?MT ?RT ?RM ?RB ?LB 0 ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom 0) (MiddleBottom ?LB) (RightBottom ?RB) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Get_Id))
)
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle 0) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MM) (RightBottom ?RB) (Level (+ ?L I)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?RM ?RB ?MM ?LB ?LM)) (Id (Getjd)) )
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle '.'MM) (RightMiddle 7RM) (LeftBottom 7LB) (MiddleBottom ?RB) (RightBottom 0) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?RM ?RB ?LB ?LM)) (Id (Getjd)) )
)
(printout t "MiddleBottom" crlf)
)
(defrule make new path RightBottom (declare (salience 100)) ?fmin ?f (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT) (LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom 0) (Exp ?E& :(= ?
?min)))
=>
(printout t ?min " " (fact-slot-value ?f Exp) crlf) (modify ?f(State 1))
(bind ?a (W (+ ?L 1) ?LT ?MT ?RT 0 ?RM ?MB ?LB ?LM)) (retract ?fmin) (assert (min ?a))
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle 0) (LeftBottom ?LB) (MiddleBottom ?MB) (RightBottom ?RM) (Level (+ ?L 1)) (From ?Id) (Exp ?a) (Id (Getjd))
)
(assert (Field (LeftTop ?LT) (MiddleTop ?MT) (RightTop ?RT)
(LeftMiddle ?LM) (MiddleMiddle ?MM) (RightMiddle ?RM) (LeftBottom ?LB) (MiddleBottom 0) (RightBottom ?MB) (Level (+ ?L 1)) (From ?Id) (Exp (W (+ ?L 1) ?LT ?MT ?RT ?RM 7MB 0 ?LB ?LM)) (Id (Getjd)) )
)
(printout t "RightBottom" crlf)
)
(defrule fmd_min (declare (salience 150))
; приоритет ниже чем у правила исключающего циклы и выше чем у правил порождения новых ходов ?fmin (Field (Exp ?E& :( =>
(retract ?fmin) (assert (min ?E)) )
;;если нашли решение, то выделяем его (defrule start_select_answer (declare (salience 500))
?f (LeftBottom 7) (MiddleBottom 6) (RightBottom 5) (State ~2) (From ?Id))
=>
(printout t "start select answer Id-' (fact-slot-value ?f Id) crlf)
(modify ?f(State 2))

¦;делаем останов если решение есть (defrule Stop_2
(declare (salience 200))
(Field(State 2))
=>
(halt)
(printout t "fined solution" crlf)
)
4.3. Варианты заданий
Задание. Для задачи из варианта придумать адекватную задаче оценочную функцию и составить программу, реализующую алгоритм А*. Причем программа должна показывать (в любом виде) дерево поиска с указанием значений узлов и их оценок.
1. Трем миссионерам и трем каннибалам необходимо переправиться на другой берег реки. На берегу реки находится лодка (без гребца), которая может вместить не более 2-х человек. Необходимо организовать переправу так, чтобы ни на одном берегу количество каннибалов не превышало количество миссионеров.
2. Три рыцаря, каждый в сопровождении оруженосца, съехались на берегу реки, намереваясь переправиться на другую сторону. Им удалось найти Двухместную лодку и переправа произошла бы легко, если бы не одно затруднение: все оруженосцы, словно сговорившись, наотрез отказались оставаться в обществе незнакомых рыцарей без своих хозяев. Необходимо организовать переправу, соблюдая условия оруженосцев.
(defrule select_answer (declare (salience 500)) (Field (State 2) (From ?Id>)
?f =>
(modify ?f(State 2))
(printout t "select answer Id=" ?Id crlf)
)
;;удапяем остальные (defrule delete_not_answer (declare (salience 400)) (Field (State 2))
?f =>
(retract ?f)
(printout t "delete not answer" crlf)
)
;;делаем останов если решений нет (defrule Stop l (declare (salience 200)) (Field(State ?x))
(not (Field(State 0|2)))
=>
(halt)
(printout t "no solutions" crlf)
На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5, 2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (х, у) в одну из
трех точек: или точку с координатами (лг+З, у), или в точку с координатами (л, >*+3), или в точку с координатами (х, у+4). Выигрывает игрок, после хода которого расстояния от фишки до точки с координатами (0, 0) не меньше 13 единиц. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
4. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (3, 2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (х, у) в одну из трех точек: или в точку с координатами (лг+З, у), или в точку с координатами (л\ у+2), или в точку с координатами (лс, >+4). Выигрывает игрок, после хода которого расстояние от фишки до точки с координатами (0, 0) больше единиц. Выяснить, кто выигрывает при правильной игре - первый или второйг игрок.
5. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (0, -5). Ход состоит в том, что игрок перемещает фишку из точки с координатами (х, у) в одну из трех точек: или в точку с координатами (t+4, j>), или в точку с координатами (х, jH-4), или в точку с координатами (jc+4, у+4). Выигрывает игрок, после хода которого расстояние от фишки до точки с координатами (0, 0) н меньше 13 единиц. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
6. Перед игроками лежат две кучи камней, в первой из которых 1, а во второй - 2 камня. У каждого игрока неограниченное количество камней. Игрок" ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 pi число камней в какой-то куче, или добавляет 2 камня в какую-то кучу Выигрывает игрок, после хода которого общее число камней становится менее 17 камней. Выяснить, кто выигрывает при правильной игре - первы или второй игрок.
7. Перед игроками лежат две кучи камней, в первой из которых 6, а во второй
5 камней. У каждого игрока неограниченно много камней. Игроки ходят п" очереди. Ход состоит в том, что игрок увеличивает или в 2 раза или в 3 раза число камней в какой-то куче. Выигрывает игрок, после хода которого общее число камней в двух кучах становится менее 48 камней. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
8. Перед двумя игроками лежат две кучи камней, в первой из которых 3, а во второй - 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого число камней в двух кучах становится не менее 24 камней. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
9. Даны три кучи камней, содержащих соответственно 2, 3 и 4 камня. За один ход разрешается или удвоить количество камней в меньшей куче (если их две - то в каждой из них), или добавить по 1 камню в каждую из всех трех куч. Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
10. Перед игроками лежат две кучки камней, в первой из которых 3, а во второй - 4 камня. У каждого игрока неограниченно много камней. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число камней в 2 раза, или добавляет в какую-то кучку 3 камня. Выигрывает тот игрок, после хода которого общее число камней в двух кучках становится не менее 23. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
11. Перед игроками лежат две кучки камней, в первой из которых 2, во второй - 3 камня. У каждого игрока неограниченное количество камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает число камней в какой-то куче в 3 раза, или добавляет 3 камня в любую из куч. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 33. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
12. Даны две горки фишек, содержащих соответственно 2 и 4 фишки. За один ход разрешается или удвоить количество фишек в какой-нибудь горке, или добавить по две фишки в каждую из двух горок. Выигрывает тот игрок, после чьего хода в двух горках суммарно становится не менее 24 фишек. Игроки ходят но очереди. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
13. Два игрока играют в следующую игру. Перед ними лежат две кучки фишек, в первой из которых 3, а во второй - 5 фишек. У каждого игрока неограниченно много фишек. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число фишек в 2 раза, или добавляет в какую-то кучку 2 фишки. Выигрывает тот игрок, после хода которого общее число фишек в двух кучках становится не менее 23. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.
14. Даны три кучи камней, содержащих соответственно 3, 4, и 5 камней. За один ход разрешается или удвоить количество камней в меньшей куче (если таких две - то лишь в одной из них), или добавить 2 камня в большую из куч (если таких две - то лишь в одну из них). Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре - первый или второй ИФОК.
15. Имеются три колышка А, В, С, и я дисков разного размера, перенумерованных от 1 до и в порядке возрастания их размеров. Сначала все диски надеты на колышек А так, что диски меньшего размера находятся на дисках большего размера. Требуется перенести все диски с колышка А на колышек С соблюдая следующие условия: диски можно переносить только по одному, больший диск можно ставить на меньший.
16. Имеется п населенных пунктов, перенумерованных от 1 до я. Некоторые пары пунктов соединены дорогами. Определить, кратчайший путь из пункта х в пункту (1 5. Лабораторная работа №4. Объектное программирование в CLIPS
5.1. Использование объектно-ориентированных средств в CLIPS
Использование объектно-ориентированных средств в CLIPS позволяет значительно упростить программирование правил, поскольку для обновления данных можно применять механизм передачи и обработки сообщений методами классов.
Общий синтаксис определения класса выглядит следующим образом:
(defclass [] (is-a +) []
[
] *
*)
::= (role concrete | abstract)