23670

Поиск решения со сменой подцелей

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

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

В процессе работы необходимо реализовать в среде CLIPS программу решения задачи построения башни из блоков. Вводные замечания Задача построения башни из блоков кубиков заключается в последовательном выборе из неупорядоченной кучи блоков и постановки их друг на друга. Процесс решения задачи представляет собой чередование двух фаз: выбора блока из кучи и установки его в башню. При этом больший по размерам блок не может ставиться на меньший по размерам и следовательно на каждом шаге решения задачи необходимо выбирать из кучи самый большой...

Русский

2013-08-05

33.5 KB

10 чел.

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

Тема: Поиск решения со сменой подцелей

Цель работы: Закрепить понимание принципов решения задач на основе продукционной модели с динамическим изменением подцелей в процессе решения. В процессе работы необходимо реализовать в среде CLIPS программу решения задачи построения башни из блоков.

Вводные замечания

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

Каждый блок характеризуется размером, цветом и положением, поэтому для его описания можно использовать следующий шаблон:

(deftemplate block 

(slot size (type INTEGER))

(slot place (type SYMBOL))

(slot color (type SYMBOL))

)

Каждый блок может находиться либо в куче (heap), либо в руке (hand), когда он выбран из кучи, либо в башне (tower).

Результатом решения задачи должно быть взаимное положение блоков в башне, т. е. при выводе результата необходимо указать порядок блоков в башне по цвету. С этой целью для блоков, находящихся в башне, необходимо определить отношение, указывающее, какой блок (upper) на каком (lower) стоит:

(deftemplate on 

(slot upper (type SYMBOL))

(slot lower (type SYMBOL))

(slot place (type SYMBOL)(default heap))

)

Если блок ставится в основание башни, слоту place присваивается значение tower, а слоты upper и lower остаются неопределенными. Если блок ставится на другой блок, слотам upper и lower должны присваиваться значения цветов соответствующих блоков.

Поскольку процесс решения задачи представляет собой чередование фаз поиска в куче самого большого блока (find) и его установки в башню (build), необходимо иметь факт, определяющий текущую задачу. Его можно определить с помощью следующего шаблона:

(deftemplate goal 

(slot current-task (type SYMBOL))

)

Для решения задачи необходимы правила для:

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

 

Правило установки начального значения текущей задачи должно активироваться исходным фактом (initial-fact) и устанавливать в качестве текущей задачи  find.

Правило выбора из кучи самого большого блока должно активироваться следующими условиями:

  •  текущая задача – find;
  •  наличие в куче блока, для которого не существует большего по размерам.

Действия правила:

  •  взять найденный блок в руку (изменить его местоположение на hand);
  •  изменить текущую задачу на build.

Правило установки блока в основание башни (первого блока) имеет следующие условия активации:

  •  текущая задача – build;
  •  имеется блок в руке;
  •  отсутствуют блоки в башне – нет блока, у которого значение слота place равно tower.

Действия правила:

  •  изменить местоположение блока в руке на tower;
  •  изменить текущую задачу на find.

Правило установки в башню последующих блоков имеет условия активации:

  •  текущая задача – build;
  •  имеется блок в руке (для него надо запомнить цвет);
  •  имеется блок в башне, на котором не стоит другой блок (для него также надо запомнить цвет);

Действия правила:

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

Правило определения окончания процесса должно активироваться, когда в куче больше нет блоков и удалять из рабочей памяти факт текущей задачи.

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

1. Разработать программу на языке CLIPS, реализующую описанные выше правила, в соответствии с вариантом задания указанным в таблице (см. ниже).

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

2. Вывод результатов на экран должен обеспечивать пошаговое отображение процесса построения башни.

Таблица вариантов заданий

№ варианта

Блок-1

(цвет/размер)

Блок-2

Блок-3

Блок-4

1

2

3

4

5

6

7

8

9

синий/10

красный/20

желтый/15

зеленый/10

коричневый/5

красный/10

желтый/12

белый/16

черный/18

зеленый/8

коричневый/5

красный/10

желтый/14

белый/25

черный/18

синий/10

красный/5

желтый/15

красный/18

желтый/12

белый/25

черный/18

синий/14

желтый/15

зеленый/8

коричневый/15

красный/20

желтый/15

зеленый/8

коричневый/5

красный/11

желтый/12

белый/25

черный/18

синий/10

белый/10


 

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

83511. Правовий статус і міжнародна правосуб’єктність міжнародних організацій 36.36 KB
  В основі правової природи міжнародних організацій лежить наявність спільних цілей і інтересів держав-членів. Для правової природи міжнародної організації істотним є те, що її цілі і принципи, компетенція, структура і т.п. має узгоджену договірну основу.
83512. Функції міжнародних організацій 32.88 KB
  У багатщ випадках держави зобов\'язані регулярно представляти доповіді про виконання ними норм міжнародного права і актів організації у відповідній області особливо в області прав людини. Оперативна функція полягає в досягненні цілей організації шляхом безпосередньої діяльності власними засобами організації. Організації надають економічну науковотехнічну і іншу допомогу консультаційні послуги.
83513. Правова природа актів міжнародних організацій 44.29 KB
  Так у сучасній міжнародноправовій літературі звертається увага на подібність процедури розробки міжнародних стандартів з одного боку і процесом вироблення міжнародної угоди в рамках міжнародної організації з іншого. Крім того висловлюється позиція що регламенти міжнародних організацій є результат їх законодавчої або Квазізаконодавчо діяльності. За своєю юридичною силою акти міжнародних орагнізацій можуть бути як рекомендаційними так і носити юридично обов\'язковий характер.
83514. Створення і припинення діяльності міжнародних організацій 34.13 KB
  Міжнародні організації як вторинні похідні суб’єкти міжнародного права створюються державами. Процес створення нової міжнародної організації проходить в три етапи: ухвалення засновницького документу; створення матеріальної структури організації; скликання головних органів що свідчить про початок функціонування організації. Злагоджене волевиявлення держав щодо створення міжнародної організації може бути зафіксовано 2 способами: у міжнародному договорі; у рішенні вже існуючої міжнародної організації. Укладення міжнародного договору припускає...
83515. ООН: цілі і принципи діяльності 37.81 KB
  Організація Об’єднаних Націй ООН універсальна міжнародна міжурядова організація що діє на підставі Статуту підписаний 26 червня 1945 р. Статут ООН є універсальним загальнообов’язковим міжнародним договором що закріплює основи сучасного міжнародного правопорядку. ООН переслідує наступні цілі: підтримувати міжнародний мир і безпеку і з цією метою вживати ефективні колективні заходи для запобігання і усунення загрози миру і придушення актів агресії або інших порушень миру й проводити мирними засобами вирішення міжнародних спорів;...
83516. Рада безпеки ООН, її функції. Членство. Порядок прийняття рішень 36.98 KB
  Рада Безпеки є одним з головних органів ООНщо виконує основну роль в підтримці міжнародного миру і безпеки та згідно з п. Рада безпеки уповноважена розслідувати будьякий спір або ситуацію для визначення того чи не може продовження цього спору або ситуації загрожувати міжнародному миру і безпеці. Сторони спору продовження якого може загрожувати міжнародному миру або безпеці мають право самостійно ухвалити рішення про його передачу на вирішення Ради Безпеки.
83517. Генеральна Асамблея ООН, її структура. Порядок роботи та порядок прийняття рішень 36.41 KB
  Порядок роботи та порядок прийняття рішень Генеральна Асамблея один з головних органів ООН що складається з представників всіх державчленів ООН. Делегація кожної державичлена ООН складається не більш ніж з п\'яти представник і п\'яти їх заступників. Генеральна Асамблея в межах Статуту ООН має право обговори вати та робити рекомендації членам ООН або Раді Безпеки з будьяких питань або справ в межах Статуту крім питань що знаходяться розгляді Ради Безпеки стосовно будьякого спору або ситуації.
83518. Міжнародні конференції: поняття, правила процедури, порядок прийняття рішень 36.35 KB
  Конференції з широкими повноваженнями приймають досить детальні правила. Конференції з широким представництвом мають досип складну організаційну структуру: голова комітети підкомітетиробочі групи секретаріат. Основні організаційні питання вирішує генеральний комітет що складається з голови конференції і голів комітетів.
83519. Поняття і значення права мирного вирішення міжнародних спорів 36.45 KB
  Право мирного вирішення міжнародних спорів - галузь міжнародного права, норми та принципи якої встановлюють порядок врегулювання спорів між суб\'єктами міжнародного права мирними засобами.