Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Алгоритм работы Пролог-машины



А.Л. Машкова

РЕАЛИЗАЦИЯ МЕТОДОВ ИСКУССТВЕННОГО

ИНТЕЛЛЕКТА СРЕДСТВАМИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ

Дисциплина - «Методы искусственного интеллекта»

ОРЕЛ 2015


Автор: А.Л. Машкова

 

 

Рецензент: д.э.н., профессор О.А. Савина

 

Методические указания предназначены для студентов очной формы обучения. В методических указаниях представлены основные теоретические сведения, необходимые для выполнения лабораторных работ по настоящей дисциплине, приведен порядок выполнения лабораторных работ.

 


Содержание

1 Лабораторная работа № 1. 4

1.1 Данные и знания. 5

1.2 Синтаксис языка Пролог. 7

1.3 Семантика языка Пролог. 8

1.4 Алгоритм работы Пролог-машины. 9

1.5 Пример построения базы правил на Пролог. 10

1.6 Задание на лабораторную работу. 11

2 Лабораторная работа № 2. 12

2.1 Использование списков в Пролог. 13

2.2 Использование накапливающего параметра. 14

2.3 Управление перебором. 15

2.4 Задание на лабораторную работу. 17

3 Лабораторная работа № 3. 18

3.1 Представление задачи в терминах пространства состояний. 19

3.2 Слепые методы поиска. 19

3.3 Методы эвристического поиска. 20

3.4 Поиск оптимального пути. 23

3.4 Задание на лабораторную работу. 24

4 Лабораторная работа № 4. 25

4.1 Основные понятия теории игр. 26

4.2 Представление игры в матричной форме. 27

4.3 Представление игры в виде игрового дерева. 29

4.4 Задание на лабораторную работу. 30

 


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

 

ПРОДУКЦИОННАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

Цель занятия

Ознакомиться с основными принципами представления знаний в продукционной форме и способами их представления на языке Пролог.

 

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

1 Изучить основные синтаксические и семантические правила в языке Пролог

2 Рассмотреть пример построения базы знаний на Пролог

3 Реализовать базу знаний о родственных отношениях

4 Оформить отчет

5 Ответить на контрольные вопросы

 

Содержание отчета

1 Текст базы фактов и правил

2 Вопросы системе

3 Результаты выполнения запросов к базе знаний

 

Контрольные вопросы

1 Этапы формализации знаний

2 Виды предложений в языке Пролог

3 Декларативный и процедурный смысл правил в языке Пролог



4 Алгоритм работы Пролог-машины

 


Данные и знания

 

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

Информация, с которой имеют дело ЭВМ, разделяется на процедурную и декларативную. Процедурная информация овеществлена в программах, которые выполняются в процессе решения задач, декларативная информация - в данных, с которыми эти программы работают. Стандартной формой представления информации в ЭВМ является машинное слово, состоящее из определенного для данного типа ЭВМ числа двоичных разрядов - битов.

Параллельно с развитием структуры ЭВМ происходило развитие информационных структур для представления данных. Появились способы описания данных в виде векторов и матриц, возникли списочные структуры, иерархические структуры. В настоящее время в языках программирования высокого уровня используются абстрактные типы данных, структура которых задается программистом. Появление баз данных (БД) знаменовало собой еще один шаг на пути организации работы с декларативной информацией. В базах данных могут одновременно храниться большие объемы информации, а специальные средства, образующие систему управления базами данных (СУБД), позволяют эффективно манипулировать с данными, при необходимости извлекать их из базы данных и записывать их в нужном порядке в базу.



По мере развития исследований в области ИС возникла концепция знаний, которые объединили в себе многие черты процедурной и декларативной информации.Данные – это отдельные факты, характеризующие объекты и процессы предметной области. Знания – это закономерности предметной области, полученные в результате практической деятельности, т.е. основанные на опыте человека. Знания – это хорошо структурированные данные. Знания проходят этапы:

1 – знания в голове человека;

2 – знания на бумажном носителе информации, записанные на естественном языке;

3 – формальные модели представления знаний;

4 – база знаний на машинном носителе информации.

Продукционные правила имеют вид:

P1… Pm^Q1…Qn

Если предпосылки P1… Рт верны, то верны и заключения Q1…Qn. Предпосылки часто называются условиями. Иногда используется и другая терминология, согласно которой предпосылки называются левой частью правила, а действия — правой. Иногда подобные правила записывают в виде условного оператора: if P1… Pm then Q1…Qn.

Продукционная модель представления знаний реализована в языке ЛП Пролог. Она включает факты и правила. Основными понятиями в языке Пролог являются факты, правила логического вывода и запросы, позволяющие описывать базы знаний, процедуры логического вывода и принятия решений. Особую роль в интерпретаторе Пролога играют конкретные запросы к базам знаний, на которые система логического программирования генерирует ответы «истина» и «ложь». Для обобщённых запросов с переменными в качестве аргументов созданная систем Пролог выводит конкретные данные в подтверждение истинности обобщённых сведений и правил вывода. В языке Прологе факты описываются в форме логических предикатов с конкретными значениями. Правила описываются логическими предикатами с определением правил логического вывода в виде списка предикатов над базами знаний и процедурами обработки информации.

Синтаксис языка Пролог

 

Наименьшие элементы Пролог-программы: Атомы, Числа, Переменные.

Атомы можно записывать тремя способами:

1 - в виде букв, цифр и _, начинающейся со строчной буквы. Пр.катя.

2 – как последовательность спец. Символов +, -, *,/,=. Пр. :-

3 – цепочка символов, заключенная в ''. Пр. 'катя'.

Числа в Прологе могут быть целые и вещественные.

Переменные представляются в виде последовательности букв, цифр и _, начинающейся с заглавной буквы. Пр. Х. Особая переменная _ используется в тех местах, где значение нам безразлично.

Пример: имеет_ребенка(Х) :- родитель(Х, _).

Структура – это конструкция Пролог, которая позволяет объединить другие компоненты: атомы, числа, переменные и др. структуры. В последнем случае структура рекурсивная (дерево, список). Количество аргументов структуры называется ее арностью.

Пример: дерево на Пролог узел(а1, а2) или узел(узел(а1,а2), а3)

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

p(t1, t2,…,tn).

p – предикатный символ.

t1, t2,…,tn – термы.

Из предикатов строятся предложения: факты, правила и вопросы.

Факт – это предикат, после которого ставится точка.

Вопрос (цель) – это предикат или последовательность предикатов, которые формулируют результат, который должна выдать программа. Начинается вопрос с ?- , заканчивается точкой, цели разделяются запятыми.

Правила имеют вид: p:-p1, p2,…,pn.

P, p1, p2,…,pn – предикаты

P – заголовок правила

p1, p2,…,pn – тело правила

Факт – это правило, у которого нет тела.

 

Семантика языка Пролог

 

Правила в пролог имеют 2 смысла: декларативный и процедурный.

1 – декларативный смысл правила p:-p1, p2,…,pn.

р истинно, если истинны все p1, p2,…,pn.

2 – процедурный смысл правила определяет порядок достижения целей. Если предикат рассматривать как цель, то для достижения цели р нужно последовательно достичь цели p1, p2,…,pn.

Правило можно представить как процедуру р с параметрами t1, t2,…,tm:

p(t1, t2,…,tm):-

p1(…),

p2(…),

…,

рn(…).

Для выполнения процедуры р необходимо выполнить процедуры p1(…), p2(…),…, рn(…).

Вопрос системе можно рассматривать как вызов процедуры.

?- p(t1, t2,…,tm).

Параметры в Пролог передаются путем сопоставления. ! и тот же параметр может быть и входным, и выходным. Применяется алгоритм унификации. 2 терма сопоставимы, если они идентичны или если они станут идентичными при применении подстановки.

 

 

Алгоритм работы Пролог-машины.

 

Процедура «Вычислить» получает на входе список целей, на выходе результат: успех или неудача. В случае успеха выдается подстановка. Этот алгоритм в процессе работы просматривает базу фактов и правил и согласует их с целями. Факты можно считать правилами, у которых нет тела.

1. Если список целей пуст, то алгоритм успешно завершает работу.

2. если список не пуст, то запускается процедура «Просмотр». Она просматривает факты и правила (предложения), пока не обнаружит предложение С, голова которого сопоставима с первой целью G1.

3. Если такого предложения найти не удается, то процедура «Просмотр» возвращает неудачу. Если предложение найдено, то оно будет иметь вид H :- B1, B2,..,Bn. Подходящих предложений может быть несколько, тогда выберет первый. Находим подстановку (пока достаточно знать, что переменная сопоставима с конкретным значением). В списке целей первая цель G1 заменяется телом правила:

B1, B2,..,Bn, G2,…, Gm. //новый список целей

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

4. К новому списку целей применяется подстановка. Этот список возвращается процедуре «Вычислить».

5. Если этот список целей приведет к успеху, то и вычисление всей программы будет успешным. Если вычисление списка приведет к неудаче, то и процедура «Просмотр» должна продолжить свою работу: найти еще одно предложение.

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!