Исследование дидактических возможностей сетевых моделей при разработке программных приложений систем искусственного интеллекта

 

Введение

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

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

Разработка учебных систем для студентов специальности «информатика» не должна проводиться эмпирическим путем. Каждая задача должна иметь математическое обоснование, в нашем случае, обоснование правильности перевода условий и решения задачи с языка теории графов на язык формальной логики.

Объект исследования: Процесс обучения студентов педагогической специальности «информатика» дисциплине «Основы искусственного интеллекта».

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

Цель: Исследование дидактических возможностей сетевых моделей при разработке программных приложений систем искусственного интеллекта в рамках дисциплины "Основы искусственного интеллекта".

Исходя из цели дипломной работы, были определены следующие задачи:

1. Определить перечень вопросов раздела "Основы искусственного интеллекта" современной образовательной информатики на основе анализа учебно-методической литературы и документов Министерства образования и науки РФ.
2. Провести сравнительный анализ дидактических возможностей различных моделей знаний в преподавании дисциплины "Основы искусственного интеллекта".
3. Выделить класс учебных задач дисциплины «Основы искусственного интеллекта» на основе представления моделей предметных областей.
4. Привести математическое обоснование хода решения выделенных задач.
5. Сформулировать математические высказывания на языке предикатов 1-го порядка.
6. Выделить класс учебных систем дисциплины «Основы искусственного интеллекта», рассмотреть этапы построения их прототипа.
7. Сформулировать методические рекомендации к преподаванию технологии логического программирования в дисциплине «Основы искусственного интеллекта».
8. Провести апробацию работы для студентов специальности «математика, информатика».

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

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

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

Дипломная работа состоит из введения, двух глав, заключения и двух приложений.

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

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

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

Результаты проведенной работы были изложены н6а седьмой научно-практической конференции «Наука и образование: проблемы и перспективы» (15 апреля 2005 г), доклад на тему: «Методика решения задач обхода сетей на Прологе при изучении дисциплины «Основы искусственного интеллекта» и на научно-практической конференции ФМФ (16 мая 2005 г), доклад на тему: «Дидактические возможности сетевых моделей при преподавании дисциплины «Основы искусственного интеллекта».

Глава 1. Взаимосвязь моделей представления знаний в дисциплине «Основы искусственного интеллекта»

§ 1. Содержание дисциплины "Основы искусственного интеллекта" для педагогических специальностей

Современные направления исследований в области искусственного интеллекта.

Научное направление, связанное с машинным моделированием человеческих интеллектуальных функций - искусственный интеллект - возникло в середине 60-х годов XX столетия. Его возникновение непосредственно связано с общим направлением научной и инженерной мысли, которое привело к созданию компьютера - направлением на автоматизацию человеческой интеллектуальной деятельности, на то, чтобы сложные интеллектуальные задачи, считавшиеся прерогативой человека, решались техническими средствами [14].

Несмотря на свою краткость, история исследований и разработок систем искусственного интеллекта может быть разделена на 4 периода [14]:

• 60-е - начало 70-х годов XX века - исследования по «общему интеллекту», попытки смоделировать общие интеллектуальные процессы, свойственные человеку: свободный диалог, решение разнообразных задач, доказательство теорем, различные игры (шашки, шахматы и т.д.), сочинение стихов и музыки и т.д.;
• 70-е - исследования и разработка подходов к формальному представлению знаний и умозаключений, попытки свести интеллектуальную деятельность к формальным преобразованиям символов, строк и т.д.;
• с конца 70-х - разработка специализированных на определенных предметных областях интеллектуальных систем, имеющих прикладное практическое значение (экспертных систем);
• 90-е годы - фронтальные работы по созданию ЭВМ нового поколения, построенных на иных принципах, чем обычные универсальные ЭВМ, и программного обеспечения для них.

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

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

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

Основные направления развития искусственного интеллекта [8]:

1. Представление знаний и разработка систем, основанных на знаниях.

Это основное направление искусственного интеллекта. Оно связано с разработкой моделей представления знаний, созданием баз знаний, образующих ядро экспертных систем. В последнее время включает в себя модели и методы извлечения и структурирования знаний и сливается с инженерией знаний.

1. Игры и творчество. Традиционно искусственный интеллект включает в себя игровые интеллектуальные задачи - шахматы, шашки, го.
2. Разработка естественно-языковых интерфейсов и машинный перевод.
3. Распознавание образов. Берет начало у самых истоков развития искусственного интеллекта. Это направление тесно связано с нейрокибернетикой.
4. Новые архитектуры компьютеров. Это направление занимается разработкой новых аппаратных решений и архитектур, направленных на обработку символьных и логических данных. Создаются Пролог-машины и Лисп-машины, компьютеры 5-го поколения.
5. Интеллектуальные роботы. Роботы - это электромеханические устройства, предназначенные для автоматизации человеческого труда. Самоорганизующиеся, или интеллектуальные, роботы - это конечная цель развития робототехники. Основная проблема при их создании - проблема машинного зрения.
6. Специальное программное обеспечение. В рамках этого направления разрабатываются специальные языки для решения задач невычислительного типа (LISP, PROLOG, РЕФАЛ). Помимо этого создаются пакеты прикладных программ, ориентированных на промышленную разработку интеллектуальных систем, или программные инструментарии искусственного интеллекта, например, KEE, ARTS.
7. Обучение и самообучение. Включает модели, методы и алгоритмы, ориентированные на автоматическое накопление знаний на основе анализа и обобщения данных. Включает обучение по примерам (или индуктивное), а также традиционные подходы распознавания образов.

Таким образом, одним из актуальных направлений информатики является интеллектуализация информационных технологий. Это означает, что одной из задач современного профессионального образования в области информатики является отражение проблематики исследований в области искусственного интеллекта, такое, как обучение основам инженерии знаний, технологии построения экспертных систем, формирование навыков работы со специальным программным обеспечением.

Обзор образовательных стандартов педагогического образования в области искусственного интеллекта

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

1. Государственный образовательный стандарт высшего профессионального образования для педагогической специальности «информатика», Министерство Образования РФ

ДПП.Ф.10Основы искусственного интеллекта Основные направления исследований в области искусственного интеллекта. Система знаний. Модели представления знаний: логическая, сетевая, фреймовая, продукционная. Понятие об экспертной системе (ЭС). Общая характеристика ЭС. Виды ЭС и типы решаемых задач. Структура и режимы использования ЭС. Классификация инструментальных средств ЭС и организация знаний в ЭС. Интеллектуальные информационные ЭС. Представление о логическом программировании. Представление знаний о предметной области в виде фактов и правил базы знаний Пролога. Дескриптивный, процедурный и машинный смысл программы на Прологе. Рекурсия и структуры данных в программах на Прологе. Представление о функциональном программировании.144

) Рабочая программа учебной дисциплины "Основы искусственного интеллекта", Белгородский государственный университет, разработана доцентом Паком Д.Н.

Объем дисциплины и виды учебной работы:

Вид учебной работыВсего часовСеместр6Общая трудоемкость дисциплины6464Аудиторные занятия1616Лекции (Л)1010Лабораторные работы (ЛР)66Самостоятельная работа (СР)4848Вид итогового контроля (зачет, экзамен)Экзамен

Содержание дисциплины:

№ п.пРаздел дисциплины Название темыВсего часов в трудоемкостиАудиторные занятия (часов)Самостоятельная работаВсегоВ том числеЛЛР1Основные направления исследований в области искусственного интеллекта.62242Система знаний. Модели представления знаний: логическая, сетевая, фреймовая, продукционная.1222103Понятие об экспертной системе (ЭС). Общая характеристика ЭС. Виды ЭС и типы решаемых задач. Структура и режимы использования ЭС.22422184Классификация инструментальных средств ЭС и организация знаний в ЭС.1042265Представление о функциональном программировании.1442210641610648

) Рабочая программа учебной дисциплины «Программирование", модуль «Языки программирования искусственного интеллекта", Бийский педагогический государственный университет, разработан ст. преподавателем Дудышевой Е.В.

Лекции

1. ИИ и области его применения. Программное обеспечение, предназначенное для решения задач ИИ. Типы знаний и методы их представления. Основные методы решения задач ИИ, их связь с методами программирования. Понятие парадигмы программирования, основные парадигмы.(2 часа)
2. Основы программирования на языке Лисп (6 часов)
3. Основы программирования на языке Пролог(6 часов)
4. Принципы логического программирования. Основные понятия языка Пролог, его теоретические основы. Представление системы знаний в виде фактов и правил, организация запросов. Особенности программирования на Турбо-Прологе: структура программы, синтаксис правил и фактов. (2 часа)
5. Различные подходы к программированию на Прологе. Организация выполнения программ: механизм перебора и возврата. Управление перебором с помощью «отсечения». Рекурсивная организация программ. Принудительный откат как рекурсивное средство повторения вычислений. (2 часа)
6. Структуры данных языка Пролог, их реализация в Турбо-Прологе: составные объекты, множественные типы, списки. Механизм сопоставления. Базы данных: статистические, динамические, внешние. Предикаты Турбо-Пролога для работы с данными, стандартный предикат FINDALL. Шаблоны предикатов. (2 часа)
7. Введение в экспертные системы.(2 часа)

Семинарские занятия (18 часов).

На семинарских занятиях рассматриваются практические примеры программирования на языках Лисп и Пролог, а также простейшая реализация некоторых задач ИИ.

Лабораторные работы

• Знакомство со средой Турбо-Пролога. Задание фактов, нерекурсивных правил. Организация сложных запросов. (4 часа)
• Определение рекурсивных предикатов. Правила задания рекурсии с учетом процедурного смысла программ. (4 часа)
• Управления механизмами перебора и возврата, использование «отсечения». (2 часа)
• Структура данных на Прологе на примере задачи управления кадрами. (2 часа)
• Динамические базы данных, накопление фактов. (2 часа)
• Использование предиката FINDALL для преобразования баз данных в структуры данных. (2 часа)

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

Сравнительный анализ учебно-методической литературы по дисциплине "Основы искусственного интеллекта".

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

1. А.В. Могилев, Н.И. Пак, Е.К. Хеннер "Информатика" [14]
2. "Информатика" под редакцией Н.В. Макаровой [8]
3. В.А. Каймин "Информатика" [10]
4. М.П. Лапчик, И.Г. Семакин, Е.К. Хеннер "Методика преподавания информатики" [12].

В учебнике А.В. Могилева и др. вопрос о системах искусственного интеллекта рассматривается в I главе §12 «Понятие искусственного интеллекта». В первом пункте данного параграфа авторы показывают направления исследований и разработок в области систем искусственного интеллекта. Затрагивается и вопрос об истории исследований в этой области. Далее авторы описывают модели представления знаний в системах искусственного интеллекта, они выделяют три основные модели представления знаний:

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

Здесь также каждой из моделей даны определения и приведены примеры всех моделей представления знаний, кроме формальной логической модели.

В следующих двух параграфах данной главы авторы уделяют внимание экспертным системам и технологии их разработки.

В главе 17 данного учебника проводится обзор теоретических аспектов инженерии знаний. Авторы знакомят читателей и с некоторыми практическими методами работы инженеров по знаниям, в частности, с практическими методами извлечения знаний и структурировании знаний о предметной области.

В учебнике В.А. Каймина как таковые, проблемы искусственного интеллекта не рассматриваются, но достаточно полно разбираются технологии проектирования логических систем искусственного интеллекта. Вопрос об искусственном интеллекте затрагивается в пункте 3.3. В данном пункте рассмотрены общие вопросы, относящиеся и к системам искусственного интеллекта и к математической логике.

В главе 10 пункте последнего учебника очень кратко рассматривается вопрос о моделировании знаний в школьном курсе информатики. Автор затрагивает следующие вопросы: что такое база знаний, различные типы знаний, логическая модель знаний и язык Пролог. Дано определение базы знаний, кратко описана каждая из моделей представления знаний (семантические сети, фреймы, логическая модель, продукционная модель). Рассмотрен язык Пролог, как один из языков программирования для изучения в школе и даны ссылки на литературу, в которой можно подробнее познакомиться с данным языком программирования.

На основе анализа приведенных источников можно выделить следующие учебные темы образования в области искусственного интеллекта: «Направления исследования ИИ», «Модели представления знаний в системах ИИ», «Принципы построения программных систем ИИ», «Инженерия знаний», «Технологии и языки программирования ИИ».

Сводная таблица освещения тем в учебной литературе, рассмотренной ранее:

УчебникиА.В. Могилев, Н.И. Пак, Е.К. Хеннер ИнформатикаИнформатика под редакцией Н.В. МакаровойВ.А. Каймин ИнформатикаМ.П. Лапчик, И.Г. Семакин, Е.К. Хеннер Методика преподавания информатикиУчебные темыНаправления исследований в области ИИОтражено полноОтражено полноНе отраженоНе отраженоМодели представления знаний в системах ИИОтражено полноОтражено полноКраткий обзорКраткий обзорИнженерия знанийНе отраженоОтражено полноНе отраженоНе отраженоПринципы построения программных систем ИИКраткий обзорОтражено полноНе отраженоНе отраженоТехнология и языки программиро-вания ИИОбзор языков Лисп и ПрологКраткий обзор технологииКраткий обзор языка ПрологКраткий обзор языка Пролог

Можно заметить, что модели представления знаний рассматриваются во всех источниках, так как они служат основой для изучения других тем. Технологии и средства отражены во всех учебниках, но по-разному. Только в одном учебнике Макаровой описан технологический процесс создания экспертной системы, но описание носит общий характер. В остальных учебниках рассмотрены достаточно подробно языки программирования систем искусственного интеллекта, в частности, язык Пролог. Однако в них отсутствуют примеры разработки с помощью Пролога программных систем.

В специальной литературе, такой как Братко И. [1], Малпас Дж. [13], Хювёнен Э. [21], примеры построения систем ИИ, в частности, экспертных систем, рассматриваются подробно, но только после изложения конструкций самого языка, что не укладывается в рамки дисциплины «Основы искусственного интеллекта». К тому же специальная литература слишком сложна и объемна для изучения студентами рассматриваемой дисциплины.

Выше мы отметили, что логическое программирование (технологические средства) и способы построения систем ИИ (технология разработки) дополняют друг друга и, в принципе, могут изучаться вместе. Таким образом, необходимо подобрать такие дидактические средства, которые позволят реализовать данную дидактическую задачу.

§ 2. Логическое программирование как технология реализации логической модели представления знаний

Модели представления знаний в системах искусственного интеллекта.

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

При обработке на ЭВМ знания трансформируются, условно проходя следующие этапы:

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

База знаний - это основа любой информационной системы. Наиболее фундаментальной и важной проблемой является описание смыслового содержания проблем самого широкого диапазона, т.е. должна использоваться такая форма описания знаний, которая гарантировала бы правильную обработку их содержимого по некоторым формальным правилам. Эта проблема называется проблемой представления знаний [14].

В настоящее время наиболее известны четыре подхода к представлению знаний в обсуждаемых системах:

• продукционные модели;
• семантические сети;
• фреймы;
• формальные логические модели.

Продукционная модель основана на представлении знаний в форме правил, структурированных в соответствии с образцом «ЕСЛИ - ТО». Часть правила «ЕСЛИ» называется условие, а «ТО» - выводом или действием. Под условием понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под действием - действия, выполняемые при успешном исходе поиска. Правило в общем виде записывается так:

ЕСЛИ А1, А2, …, Аn ТО В.

Такая запись означает, что «если все условия от А1 до Аn являются истинными, то В также истинно» или «когда все условия от А1 до Аn выполняются, то следует выполнить действие В». В случае n=0 продукция описывает знание, состоящее только из вывода, т.е. факт. Переменные в правиле показывают, что правило содержит некое универсальное общее знание, абстрагированное от конкретных значений переменных. Одна и та же переменная, использованная в выводе и различных посылках, может получать различные конкретные значения. При использовании продукционной модели база знаний состоит из набора правил. В интеллектуальную систему входит также механизм выводов, который позволяет на основе знаний, имеющихся в базе знаний, получать новые знания [14].

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

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

Семантическая сеть - это ориентированный граф, вершины которого - понятия, а дуги - отношения между понятиями [8]. Семантические сети способны отображать структуру знаний во всей сложности их взаимосвязей, увязать в единое целое объекты и их свойства. Можно ввести несколько классификаций семантических сетей [8].

1. По количеству типов отношений:
2. однородные (с единственным типом отношений);
3. неоднородные (с различными типами отношений).
4. По типам отношений
5. бинарные;
6. n-арные.

Наиболее часто в семантических сетях используются следующие отношения:

• связи типа "часть-целое" ("класс-подкласс", "элемент-множество" и т.д.);
• функциональные связи;
• количественные (больше, меньше, равно …);
• пространственные (далеко от, близко от, под, над …);
• временные;
• атрибутивные связи (иметь свойство, иметь значение …);
• логические связи (и, или, не) и др.

Ниже приведен пример части семантической сети [8].

Основное преимущество этой модели - в соответствии с современным представлениям об организации долговременной памяти человека. Недостаток модели - сложность поиска вывода на семантической сети [8].

Фреймовая система имеет все свойства, присущие языку представления знаний, и одновременно являет собой новый способ обработки информации. Слово «фрейм» в переводе с английского языка означает «рамка». Фрейм является единицей представления знаний об объекте, которую можно описать некоторой совокупностью понятий и сущностей. Фрейм имеет определенную внутреннюю структуру, состоящую из множества элементов, называемых слотами. Каждый слот в свою очередь, представляется определенной структурой данных, процедурой, или может быть связан с другим фреймом. Приведем пример фрейма: человек [14]

Фрейм: человек

Класс : Животное

Структурный элемент : Голова, шея, руки, ноги, …

Рост : 30 - 220 см

Масса : 1 - 200 кг

Хвост : Нет

Фрейм аналогии : Обезьяна

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

Традиционно в преставлении знаний выделяют формальные логические модели, основанные на классическом исчислении предикатов 1-го порядка, когда предметная область или задача описывается в виде аксиом.

Существуют и другие, менее распространенные подходы к представлению знаний в интеллектуальных системах, в том числе гибридные, на основе уже описанных подходов.

Перечислим главные особенности машинного представления данных.

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

Наиболее наглядной и соответствующей современным представлениям об организации долговременной памяти человека моделью представления знаний является семантическая сеть [8], что особенно важно учитывать при обучении. Однако этой модели присущ основной недостаток - в ней затруднителен поиск вывода, который сводится к задаче поиска фрагмента сети, соответствующей поставленному вопросу. Как показано выше, чаще всего при обучении используется логическая модель представления знаний, которая имеет технологическое средство разработки систем и решения прикладных задач - логическое программирование.

Логическая модель представления знаний.

В предыдущем пункте выделены формальные логические модели представления знаний, которые преимущественно основаны на классическом исчислении предикатов 1-го порядка.

Начало исследованиям в области формальной логики было положено работами Аристотеля в IV в. до н.э. Логика предикатов - это универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений. Терминология логики предикатов включает следующие понятия: рассуждение, предикат, термы, литерал, метод резолюций.

Рассуждение - один из важнейших видов мыслительной деятельности человека, в результате которого он формулирует на основе некоторых предложений, высказываний, суждений новые предложения, высказывания, суждения. Действительный механизм рассуждений человека остается пока недостаточно исследованным. Человеческим рассуждениям присущи: неформальность, нечеткость, нелогичность, широкое использование образов, эмоций и чувств, что делает чрезвычайно трудными их исследование и моделирование. К настоящему времени лучше всего изучены логические рассуждения и разработано много механизмов дедуктивных выводов, реализованных в различных интеллектуальных системах, основанных на представлении знаний с помощью логики предикатов 1-го порядка [14].

Предикат - это конструкция вида P(t1, t2, …, tn) выражающая какую-то связь между некоторыми объектами или свойствами объектов. Обозначение этой связи или свойства, P, называют «предикатным символом»; t1, t2, …, tn обозначают объекты, связанные свойством (предикатом) P, и называют термами [14].

Термы могут быть только трех следующих типов:

1. константа (обозначает индивидуальный объект или понятие);
2. переменная (обозначает в разное время различные объекты);
3. составной терм - функция f(t1, t2, …, tm), имеющая в качестве своих аргументов m термов t1, t2, …, tm.

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

Предикаты могут быть объединены в формулы с помощью логических связок: ^ («и», конъюнкция), V («или», дизъюнкция), ~ («не», отрицание), ® («следует», импликация), « («тогда, и только тогда, когда », эквиваленция).

Ниже приведена таблица истинности этих связок, позволяющие определить, истинно или ложно значение формулы-связки при различных значениях входящих в нее предикатов А и В.

Математически строго формулы логики предикатов определяются рекурсивно:

1. предикат есть формула;
2. если А и В - формулы, то ~А, А^В, АVВ, А®В, А«В - тоже формулы;
3. других формул не бывает.

Истинность связок предикатов (И - истина, Л - ложь)

АВАÙВАÚВ~АА?ВА?ВИ И Л ЛИ Л И ЛИ Л Л ЛИ И И ЛЛ Л И ИИ Л И ИИ Л Л И

Многие формулы логики предикатов требуют использования кванторов, определяющих область значения переменных - аргументов предикатов. Используются кванторы общности и квантор существования. Кванторы связывают переменные предикатов, на которые они действуют, и превращают предикаты в высказывания.

Из всевозможных формул нам потребуется только один их вид, называемый фразами Хорна. Фразы Хорна содержат в общем случае импликацию и конъюнкцию предикатов А, В1, В2,…, Вn следующим образом: В1 В2 … Вn? А, или в более удобных обозначениях:

А: - В1, В2, …, Вn.

Очевидно, фраза Хорна является формой записи некоего правила, и в дальнейшем и будет называться правилом. Предикат А называется заголовком или головой правила, а предикаты В1, В2, …, Вn - его подцелями.

Отдельный предикат является частным случаем фразы Хорна: А.

Другой частный случай фразы Хорна - правило без головы

: - В1, В2, …, Вn, или : - В.

Такая фраза Хорна называется вопросом.

Поясним логический смысл такой формулы. Импликация А:- В (А?В) может быть выражена через отрицание и дизъюнкцию: ~ВVА. Значит, если отбросить А, останется только ~ В - отрицание В.

Множество фраз Хорна применительно к некоторой проблемной области образует теорию (в логическом смысле).

Для выполнения логического вывода используют правила вывода, называемые методом резолюций.

Правило резолюции действует следующим образом. Две фразы могут быть резольвированы друг с другом, если одна из них содержит позитивный литерал, а другая - соответствующий негативный литерал с одним и тем же обозначением предиката и одинаковым количеством аргументов, и если аргументы обоих литералов могут быть унифицированы (т.е. согласованы) друг с другом [13].

Как уже отмечалось ранее, во фразовой форме не употребляется явная квантификация переменных. Неявно, однако, все переменные квантифицированны кванторами существования. Если в качестве аргумента выступает переменная, то она унифицируема с любой константой. Если в одной и той же фразе переменная встречается более одного раза и эта переменная в процессе резолюции унифицируется с константой, то резольвента будет содержать данную константу на тех местах, где рассматриваемая переменная располагалась в исходной фразе [13].

Рассмотрим две фразы:

P (a) (1)

~ P (a) (2)

Фраза (1) - это заключение без условий, а фраза (2) - это условие без заключения. Присутствие фраз (1) и (2) в одной теории является противоречием. Если фразы (1) и (2) резольвируются друг с другом, то получающаяся резольвента называется пустой фразой. Если при резолюции двух фраз, входящих в теории, получается пустая фраза, то эта теория должна быть непоследовательной.

При использовании правила резолюции применима более чем одна стратегия решения задач. Рассмотрим нисходящую (обратную) стратегию. В этой стратегии ставится цель обнаружить, является ли единственная фраза С следствием существующего множества фраз Т. Предполагается, что множество фраз Т является непротиворечивым. Алгоритм работает следующим образом. Вначале к существующему множеству фраз добавляется отрицание проверяемой фразы ~С. При этом образуется новое множество фраз Т', состоящее из множества Т плюс фраза ~C. Если алгоритм позволит вывести пустую фразу из Т', то Т' будет непоследовательной из-за присутствия фразы ~C, и поэтому С должно являться следствием Т [13].

Изложенные положения логики предикатов находят реализацию и дальнейшее развитие в логическом программировании.

Логическое программирование.

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

Логическое программирование - это один из подходов в программировании, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна. Логическое программирование строится не с помощью некоторой последовательности абстракций и преобразований, отталкивающейся от машинной архитектуры фон Неймана и присущего ей набора операций, а на основе абстрактной модели, которая никак не связана с каким-то типом машинной модели. Оно базируется на убеждении, что не человека следует обучать мышлению в терминах операций компьютера, а компьютер должен выполнять инструкции, свойственные человеку [24].

В своём чистом виде логическое программирование предполагает, что сами инструкции даже не задаются, а вместо этого явно, в виде логических аксиом, формулируются сведения о задаче и предположения, достаточные для её решения. Такое множество аксиом является альтернативой обычной программе. Подобная программа может выполняться при постановке задачи, формализованной в виде логического утверждения, подлежащего доказательству. Такое утверждение называется целевым утверждением. Выполнение программы состоит в попытке решить задачу, т.е. доказать целевое утверждение, используя предположения, заданные в логической программе [23].

Основная цель логического программирования - создать возможность разработки программ на языке высокого уровня. В идеале программист должен записать аксиомы, определяющие требуемые отношения, полностью игнорируя, каким образом эти аксиомы будут использоваться в процессе выполнения.

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

Таким образом, логическое программирование, во-первых, предоставляет реальный механизм для автоматизации обработки моделей знаний, а во-вторых, использует декларативный (описательный) стиль программирования, описания программы в терминах, близких предметной области задачи. Однако при изучении логического программирования для практического решения задач ИИ необходимо владение математическим аппаратом. В условиях недостаточной практики использования языка математической логики для многих студентов формулировка задач представляет трудность на начальном этапе обучения языку логического программирования. Поэтому в литературе (Братко И., Малпас Дж.) решения многих задач объясняются и иллюстрируются с помощью других формальных средств, в частности, сетей и графов. Нередко и в практической разработке систем ИИ для представления предметной области используются сетевые модели [8] - это один из методов, применяемых в инженерии знаний.

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

Построение модели предметной области в виде семантических сетей.

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

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

Для построения предметной области в виде семантической сети рассматриваются основные объекты-сущности данной предметной области и отношения между ними [2]. Первоначально выделяют основные понятия и категории, которыми оперируют (которыми выражаются) фрагменты предметной области. Данные понятия и категории принимаются за первоначальную основу списка объектов-сущностей предметной области. Далее на основе анализа формируются атрибуты, характеризующие выраженные объекты-сущности. При определении перечня атрибутов каждого объекта предметной области, как и самого перечня объектов-сущностей, руководствуются соображениями минимальной достаточности. Часть атрибутов и понятий предметной области выражают процессы-отношения между объектами-сущностями. Такие атрибуты выделяются, и далее анализируются параметры характер связей, которые они выражают - структурность, направленность, множественность, обязательность наличия экземпляров объектов. Чаще всего выделение объектов-сущностей, их атрибутов и отношений-связей осуществляется комбинированным способом на итерационной основе, с многократным уточнением исходного списка объектов, соединением атрибутов в группы и т.д. Распространенным приемом в этом случае является "обобщение" некоторых понятий и атрибутов. Суть обобщения заключается в объединении в одну сущность близких или однотипных понятий, категорий, атрибутов на основе анализа частных проявлений и вариантов [2].

В семантической сети сущности и классы сущностей ассоциируются с узлами, а отношения между сущностями ассоциируются с дугами, соединяющими узлы. Дуга, присоединенная к единственному узлу, устанавливает свойство этого узла. Семантическая сеть позволяет выполнять вывод по цепочкам, описываемым определенными типами дуг [13].

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

В качестве примера можно привести часть семантической сети, относящейся к понятию "птица" (рис. 2) [2].

семантический сеть пролог предметный

Напомним, что семантическая сеть - это способ представления знаний в виде помеченного ориентированного графа, в котором вершины соответствуют понятиям, объектам, действиям, ситуациям или сложным отношениям, а дуги - свойствам или элементарным отношения [19].

С точки зрения структуры, сети являются расширением понятия графа. В информатике под графом понимается конечное множество вершин, соединенных ребрами [19]. В теории графов данное понятие трактуется следующим образом: рассмотрим множество V, состоящее из соединенных некоторым образом точек. Назовем V множеством вершин и элементы vV - вершинами. Граф G=G(V,Е) (1) с множеством вершин V есть некоторое семейство сочетаний или пар вида E=(a,b), a,b V (2), указывающее, какие вершины считаются соединенными [16].

Число вершин графа G обозначим p, а число ребер - q.

В соответствии с геометрическим представлением графа каждая конкретная пара (2) называется ребром графа; вершины а и b называются концевыми точками или граничными точками ребра Е.

В определении ребра (2) можно принимать или не принимать во внимание порядок расположения 2-х его концов. Если этот порядок не существенен, то есть если E=(a,b)=(b,a), то говорят, что Е есть неориентированное ребро, если же порядок существенен, то Е называется ориентированным ребром или дугой. В последнем случае, а называется начальной вершиной, а b - конечной вершиной ребра. Также говорят, что Е ребро, выходящее из вершины а и входящее в вершину b. Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро Е инцидентно вершинам а и b, а также что а и b инцидентны Е. На рисунке 3 изображено неориентированное ребро (a,b) и ориентированное ребро (c,d). Количество ребер, инцидентных вершине v, называется степенью вершины v и обозначается d(v).

Если элементом множества Е является пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом) [15].

Пусть G - неориентированный граф.

Маршрутом в G называется такая конечная последовательность ребер (3) что каждые два соседних ребра и имеют общую концевую точку. Отметим, что одно и то же ребро Е может встречаться в маршруте несколько раз [16].

Если в маршруте (3) нет ребер, предшествующих , то называется начальной вершиной S, а если нет ребер, следующих за , то называется конечной вершиной S. Любая вершина, принадлежащая двум соседним ребрам и , называется внутренней. Так как ребра и вершины в маршруте могут повторяться, внутренняя вершина может также начальной или конечной вершиной [16].

Если маршрут S имеет как начальную вершину , так и конечную вершину , то можно написать (4) и называть и концевыми точками. S - есть маршрут длины n, соединяющий соответствующие вершины. Если , то маршрут называется циклическим [16].

Маршрут называется цепью, если каждое его ребро встречается в нем не более одного раза (вершины в цепи могут повторяться). Любой участок цепи есть цепь. Нециклическая цепь называется простой цепью, если в ней никакая вершина не повторяется. Ориентированная цепь называется путем.

Циклический маршрут называется циклом, если каждое ребро в нем встречается в нем не более одного раза. Цикл с концом называется простым циклом, если не является в нем промежуточной вершиной и никакие другие вершины не повторяются.

Пусть граф G неориентированный. Две вершины a и b называются связными, если существует маршрут вида (3) с концами a и b. Граф называется связным, если любая пара вершин связана [16].

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

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

Не уменьшая общности рассуждений, мы можем рассматривать однородные семантические сети - те, в которых всем ребрам соответствует одно и то же отношение, т.е. одна и та же семантическая функция.

Гамильтонов цикл в однородных семантических сетях

Рассмотрим задачу теории графов на нахождение гамильтонова цикла в заданном фрагменте графа (сети).

Гамильтоновой цепью в графе называется простая цепь, проходящая через все вершины по одному разу (см. рис) [15].

Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа по одному разу [16].

Теорема (Дирак): Если в графе G(V,E) "vÎV d(v)³p/2, то граф G является гамильтоновым [16].

Рассмотрим классическую задачу теории графов на нахождение гамильтонова цикла - задачу коммивояжера. Она звучит следующим образом: Имеется n городов, расстояния между которыми известны. Коммивояжер должен посетить все n городов по одному разу, вернувшись в тот с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным. Математическая постановка этой задачи состоит в следующем: во взвешенном графе требуется найти гамильтонов цикл наименьшего веса [11]. Данная задача является NP - полной; для нее не существует эффективного алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи; в связи, с чем она играет роль эталонной задачи.

В данной задаче города, представляя как вершины графа G, в котором каждой паре вершин приписывается расстояние m(a,b). Тогда задача состоит в том, чтобы найти такой гамильтонов цикл P, для которого сумма минимальна.

Проследим ход решения задачи коммивояжера.

Рассмотрим исходный неориентированный граф, где каждому городу соответствует вершины графа, дорогам между ними - ребра. Построим однородную сеть на том же множестве вершин следующим способом: каждому ребру ставим в соответствие две дуги, каждой из которых приписывается вес ребра.

Вершина u в орграфе G(V,E) достижима из вершины v, если существует путь из v в u.

Тогда отношение достижимости на взвешенном графе G(V,E) будет транзитивным замыканием E1 на V бинарного отношения E [15].

Построить транзитивное замыкание можно следующим образом: отношения со смежными вершинами принадлежат транзитивному замыканию E1; все отношения с вершинами, достижимыми из смежных вершин, тоже принадлежат замыканию.

На языке математической логики это выглядит следующим образом:

где I - тождественное отношение.

Введенное таким образом бинарное отношение E1 определяет новую однородную семантическую сеть S1(V,E1,W) с тем же множеством вершин. Заметим, что если граф исходной сети имеет одну компоненту связности, то граф полученной сети будет полным и не будет содержать кратных ребер. Соответствующий граф для данной сети - G1 (см. рис.).

Следующим шагом мы каждому дуге полученного графа G1(V,E1) приписываем множество, состоящее из множеств вершин, пройденных по пути в исходной сети от одной смежной ребру вершины до другой. Обозначим построенное отношение D, DÌE´2V.

По определению достижимости существует хотя бы один путь между заданными вершинами в исходном графе, значит это множество не пустое.

Можно показать, что существует хотя бы один путь с различными вершинами. Т.к. по определению достижимости: вершина u в орграфе G(V,E) достижима из вершины v, если существует путь из v в u, а путем называется ориентированная цепь. Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины [15].

Предложение: Для сети S1(V,E1,W,D) вес дуги, составляющий множество, состоящее из множества пройденных вершин, которое мы строим, содержит хотя бы одно множество различных вершин и его мощность не превосходит мощности множества вершин сети |V|.

Опираясь на предложение, мы для каждого такого множества, составляющего вес дуги e в S1, можем указать ненулевой максимум мощностей составных множеств из различных вершин. Для этого возьмем подмножество CÌD: D((X,Y))<=|V|. Согласно предложению оно соответствует множеству всех простых цепей из вершины X в вершину Y. Для множества C каждой цепи ставится в соответствие количество вершин в данной цепи .

Построим сеть S2(V,E1,W,M) на основании G1, приписывая каждому дуге полученный ненулевой максимум. Обозначим этот максимум для данного ребра M(e).

Утверждение 1: Если дуга e сети S2, такая что M(e)=|V|, то между вершинами смежными с e существует гамильтонова цепь.

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

Строим сеть S3(V,E2,W), где (vi, vj)ÎE2 тогда и только тогда, когда (vi, vj)ÎE1 и в сети S2 вес этой дуги равен |V|. Согласно утверждению 1 граф сети S3, будет отражать отношение существования гамильтоновой цепи в графе исходной сети S.

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

Утверждение 2: Если в графе G(V,E) между вершинами X и Y существует гамильтонова цепь, то она не содержит смежного ребра (X,Y).

Доказательство: По условию в графе G(V,E) существует гамильтонова цепь H={(X,V0),(V0,V1),…,(VN-1,VN),(VN,Y)}, |H|=|V|. Предположим, что в этом множестве присутствует смежная дуга (X,Y). Тогда имеется 3 возможности:

1. V0=Y ® получаем дугу;
2. VN=X ® получаем дугу;
3. если Vi и Vj смежные вершины и Vi=X, а Vj=Y, то видим, что вершины X и Y встречаются в цепи не по одному разу, что противоречит определению гамильтоновой цепи.

Данное противоречие доказывает истинность утверждения.?

Следствие: Если в графе G(V,E) между смежными вершинами существует гамильтонова цепь, то есть возможность в данном графе построить гамильтонов цикл. Для этого достаточно дополнить гамильтонову цепь смежной дугой.

Теперь для каждой вершины мы можем ввести свойство существования из нее хотя бы одного гамильтонова цикла. Припишем каждой вершине, имеющей свойство, вес - минимум сумм весов дуг, пройденных в каждом из гамильтоновых циклов, начинающихся в заданной вершине. Собственно это и требуется найти по условию задачи. Остальным вершинам приписываем: не определено.

На языке математической логики это свойство будет выглядеть следующим образом:

.

Если ввести следующие обозначения: C/E - цепь, состоящая из множества дуг; с - простая цепь из одной вершины в другую; m(e) - вес дуги e, то получим следующее утверждение:

Эйлеров цикл в однородных семантических сетях.

Перейдем к задаче на нахождение эйлерова цикла в заданном фрагменте сети.

Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом [16].

Теорема: Конечный граф G является эйлеровым графом тогда и только тогда, когда

1. G связен.
2. Все его локальные степени четны [16].

Классической задачей в теории графов на нахождение эйлерова цикла является задача китайского почтальона. Она звучит следующим образом: во взвешенном графе найти цикл, проходящий через каждое ребро, по крайней мере, один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если граф эйлеров, то любой эйлеров цикл дает оптимальное решение задачи [11].

Тогда задача будет состоять в том, чтобы проверить существования эйлерова цикла в графе (рис ).

Для данной задачи не получается рассуждать аналогичным способом, т.к. каждое ребро необходимо проходить ровно по одному разу, и механическая замена на две дуги невозможна.

Предлагаем следующий способ: искусственно вводится дополнительный вес Q для каждого ребра - это номер дороги. Далее заменяем каждое ребро на две дуги, каждой из которых присваиваем вес исходного ребра, т.е. его номер.

Вместо отношения достижимости (транзитивное замыкание) возьмем на взвешенном графе G(V,E) рефлексивно транзитивное замыкание E1 на V бинарного отношения E.

Т.о. получаем, что наш новый граф может содержать петли, т.е. является псевдографом:

Для каждой вершины графа G1(V,E1) задаем множество, состоящее из множеств дуг с различными номерами, пройденных по пути в исходной сети от одной смежной ребру вершины до другой. DÌE1´2E - отношение множества дуг полученного графа во множество множеств дуг с различными номерами, пройденных по пути от одной вершины к другой. Таким образом, D определяет подмножество цепей, по которым можно пройти от одной вершины к другой. Определим отношение CÌE1´2Q, которое для каждого дуги e из E1 ставит в соответствие номера дуг для D(e). Для множества C каждой цепи ставится в соответствие количество номеров дуг в данной цепи . Для каждого ребра приписываем новый вес MÌE´N - максимум мощностей множества номеров различных ребер, пройденных по пути в исходной сети - максимум длин соответствующих цепей. Этот максимум не превосходит половины мощности множества дуг исходной сети (мощности ребер |E|), а если совпадает с ним, то существует цепь, включающая дуги со всеми возможными номерами.

Построим сеть, где дуга eÎE2 тогда и только тогда, когда eÎE1 и в имеющейся сети вес этой дуги равен M(e)=|E|.

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

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

Или, применяя формулу,

.

Таким образом, мы получили набор математических высказываний, необходимых для описания преобразования сетевых моделей в ходе решения поставленных задач.

Глава 2. Применение сетевых моделей при разработке учебных экспертных систем на основе логической модели представления знаний

§ 1. Представление семантических сетей с помощью логической модели представления знаний

Описание моделей предметных областей с помощью языка предикатов.

Рассмотрим основные понятия исчисления предикатов I порядка. В логике предикатов элементарным объектом, обладающим истинностным значением, является атомарная формула. Атомарная формула состоит из символического обозначения предиката и термов, выступающих в роли аргументов этого предиката. Для предиката должны быть заданы домены аргументов - множества, являющиеся областью их определения.

В общем случае обозначение предиката - это имя отношения, существующего между аргументами. Атомарная формула записывается как обозначение предиката, за которым в скобках располагаются несколько аргументов. Каждый аргумент - это терм. Общий вид атомарной формулы: P (t1, t2, …, tn). Здесь P обозначение предиката, а t1, t2, …, tn - термы. Терм - это либо константа, либо переменная, либо употребление функции [13].

Правильно построенная формула (ППФ) получается в результате комбинирования атомарных формул с логическими соединителями. ППФ определятся следующим образом:

1. атомарная формула - ППФ;
2. если А и В - ППФ, то ППФ будут и формулы:

~А, А^В, АvВ, А«В, А®В, $x A, "x A [13].

Построение теории некоторой области знаний с использованием логики предикатов начинается с анализа области знаний. Он выполняется следующим образом. Вначале выделяется множество значимых сущностей из этой области; данное множество называется областью интерпретации. На следующем этапе определяется, какие функции над элементами области интерпретации представляются важными, если только такие функции вообще существуют. Функция - это отображение n элементов из области интерпретации (n - количество аргументов функции) на один элемент этой области [13].

Затем идентифицируются значимые отношения, которые существуют между элементами области интерпретации. Отношение - это отображение n элементов из области интерпретации (n - количество аргументов отношения) на истинностное значение (т.е. на элемент из множества {истина, ложь}). В заключении значимые отношения оформляются синтаксически, т.е. при помощи аксиом.

Следующим шагом после установления области интерпретации описываемой области знаний будет выбор обозначений для представления элементов области интерпретации. Сначала подбираются обозначения для констант - a, b, c, и т.д. Значениями этих констант будут элементы из области интерпретации. Затем подбираются обозначения для каждой важной функции. Заметим, что функция сама по себе не может иметь значения. Значением может обладать только употребление функции. Функция, представленная некоторым обозначением, определяется семантически путем указания значений различных ее употреблений (т.е. указанием конкретных случаев отображения n элементов из области интерпретации на один элемент этой области). В заключение для каждого важного отношения из области интерпретации подбираются обозначения предикатов. Отношение, представленное обозначением предиката, определяется семантически путем указания истинностных значений различных конкретных случаев этого отношения (т.е. указанием того, как данное отношение отображает n элементов из области интерпретации на истинностное значение). Конкретный случай отношения представляется атомарной формулой, построенной на основе выбранных обозначений предикатов, функций и констант [13].

Интерпретация ППФ состоит из четырех типов присваивания:

1. Каждой константе, входящей в ППФ, приписывается некоторый элемент из области интерпретации.
2. Каждой переменной, входящей в ППФ, приписывается элемент из области интерпретации.
3. Каждому употреблению функции в ППФ приписывается элемент из области интерпретации. Множество таких присваиваний для некоторой конкретной функции определяет эту функцию семантически.
4. Каждой атомарной формуле, входящей в ППФ, приписывается истинностное значение. Множество таких присваиваний для некоторого конкретного отношения определяет это отношение семантически [13].

Фразовая форма логики предикатов - это способ записи формул, при котором употребляется только соединители &, v и ~. Литерал - это позитивная или негативная атомарная формула. Каждая фраза - это множество литералов, соединенных символом v. Негативные литералы размещаются в конце каждой фразы, а позитивные вначале. Фразу можно рассматривать как обобщение понятия импликация. Если А и В - атомарные формулы, то формула А?В может также быть записана как ~АvВ. Поскольку ~А - негативно, а В - позитивно, то фразовая форма будет иметь вид: Вv ~А.

Все позитивные атомарные формулы, входящие во фразу, являются альтернативными заключениями, а все негативные атомарные формулы - необходимыми условиями.

Фраза Хорна - это фраза, содержащая только один позитивный литерал. Например, фраза CÚ ~EÚ ~FÚ ~G является фразой Хорна. Если воспользоваться обратной стрелкой, то эта фраза имеет вид C¬E,F,G [13].

Математические отношения, которые мы получили в 1 главе §3 пунктах 2 и 3, можно переписать с помощью фраз Хорна следующим образом.

Определим бинарное отношение смежности двух вершин А и В на множестве V в виде двуместного предиката дуга, где оба аргумента принадлежат домену V. Определенное нами отношение достижимости вершины А из вершины В в графе G(V,E), запишем предикатом путь с двумя аргументами, где оба аргумента принадлежат домену V.

(1).

Зададим двуместный предикат, определяющий существование гамильтоновой цепи в графе G (V,E) из вершины А в вершину В - цепь, оба аргумента которого принадлежат домену V - конечному множеству вершин.

(2)

Предикат количество, первый аргумент которого принадлежит домену 2VxV, а второй - домену N - множеству натуральных чисел, определяет количество вершин в пройденном простом пути. Предикат пр_цепь, где первые два аргумента принадлежат домену V, а третий принадлежит домену 2VxV, определяет простой путь между вершинами А и В, т.е. путь в котором каждая дуга встречается по одному разу.

Определим предикат ребро, оба аргумента которого принадлежат домену V, ставящий в соответствие каждой дуге ребро графа.

(3).

Опишем одноместный предикат цикл, первый аргумент которого принадлежит домену V, а второй - N, определяющий существование гамильтонова цикла из заданной вершины в исходном графе.

Предикат длина, определяет длину гамильтоновой цепи, первые два его аргумента принадлежат домену V, третий - домену N. Предикат вес, задает вес ребра, первые два его аргумента принадлежат домену V, третий - домену N.

Для задачи коммивояжера получаем следующее:

.

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

Для второй задачи определим бинарное отношение смежности двух вершин на множестве V в виде трехместного предиката дуга, первые два аргумента принадлежат домену V, а третий - домену N. Определенное нами отношение достижимости одной вершины из другой вершины в графе G(V,E), запишем двуместным предикатом путь, оба аргумента которого принадлежат домену V. Определение этого предиката в виде фразы Хорна будет аналогичным с фразой (1) (см. выше).

Определим одноместный предикат цикл, определяющий существование эйлерова цикла из заданной вершины, аргумент которого принадлежит домену V.

Предикат цепь определяет существование цепи из одной вершины в другую, где первые два аргумента принадлежат домену V, а третий принадлежит домену 2ExE. Предикат длина возвращает длину заданной цепи, первый аргумент, которого принадлежит домену 2ExE, а второй - домену N.

Основные средства языка логического программирования Пролог

Язык Пролог является представителем семейства языков логического программирования. При использовании данного языка основное внимание уделяется описанию объектов и связей между ними, а не разработке последовательности действий для достижения цели. Пролог-программа больше является описанием того, что нужно сделать, чем того, как это сделать.

Программирование на Прологе включает в себя следующие этапы [5]:

1)объявление фактов о объектах и отношениях между ними;

2)определение правил взаимосвязи объектов и отношений между ними;

)формулировка вопроса об объектах и отношениях между ними.

Основными составляющими программы на Прологе являются ….

Факты - это предикат с аргументами-константами, обозначающие отношения между объектами или свойства объектов, именованные этими константами. Факты в программе считаются всегда и безусловно истинными и таким образом служат основой доказательства, происходящего при выполнении программы [14].

Правила - это хорновские фразы с одной или несколькими переменными и с заголовком. Правила имеют форму <голова правила>:-<список подцелей>, где знак ":-" читается «если», а список подцелей состоит из отдельных подцелей, разделенных запятой, читаемой как «и». Правила позволяют определить новые отношения между объектами на основе уже объявленных с помощью фактов. В качестве аргументов в предикатах правила могут использоваться константы и переменные. На переменные в правилах действуют кванторы общности, поэтому правила концентрированно и лаконично выражают конструкции логического вывода [14]. Правила в Прологе часто бывают рекурсивными, т.е. использующими себя в своем определении.

Вопрос - отправная точка логического вывода, происходящего при выполнении программы [14].

В каждой процедуре должен быть принят порядок правил, или порядок предложений. Кроме того, в теле каждого предложения должен быть определён порядок целей. Порядок правил определяет порядок поиска решений. Изменение порядка правил в процедуре приводит к перестановке ветвей в любом дереве поиска цели, использующей данную процедуру. Обход дерева поиска происходит в глубину. Поэтому перестановка ветвей дерева изменяет порядок обхода дерева и порядок нахождения решений [24].

Декларативный смысл программы определяет, является ли данная цель истинной (достижимой) и, если да, при каких значениях переменных она достигается. Для точного определения декларативного смысла нам потребуется понятие конкретизации предложения. Конкретизацией предложения С называется результат подстановки в него на место каждой переменной некоторого терма. Вариантом предложения С называется такая конкретизация С, при которой каждая переменная заменена на другую переменную.

Пусть дана некоторая программа и цель G, тогда, в соответствии с декларативной семантикой, можно утверждать, что:

цель G истинна (т.е. достижима или логически следует из программы) тогда и только тогда, когда

1. в программе существует предложение С, такое, что
2. существует такая его конкретизация I, что

(а) голова I совпадает с G и

(b) все цели в теле I истинны.

Эти определения можно распространить на вопросы следующим образом. В общем случае вопрос к Пролог-системе представляет собой список целей, разделенных запятыми. Список целей называется истинным (достижимым), если все цели в этом списке истинны (достижимы) при одинаковых конкретизациях переменных. Значения переменных получаются из наиболее общей конкретизации [3].

Процедурная семантика определяет, как пролог-система отвечает на вопросы. Ответить на вопрос - это значит удовлетворить список целей. Этого можно добиться, приписав встречающимся переменным значения таким образом, чтобы цели логически следовали из программы. Можно сказать, что процедурная семантика Пролога - это процедура вычисления списка целей с учетом заданной программы. «Вычислить цели» это значит попытаться достичь их.

Автор Братко И. [1] называет эту процедуру "Вычислить". Как показано на рисунке, входом и выходом этой процедуры являются:

входом - программа и список целей,

выходом - признак успех/неуспех и подстановка переменных.

Смысл двух составляющих выхода такой:

1. Признак успех/неуспех принимает значение «да», если цели достижимы, и «нет» - в противном случае. Будем говорить, что «да» сигнализирует об успешном завершении и «нет» - о неуспехе.
2. Подстановка переменных порождается только в случае успешного завершения; в случае неуспешного подстановка отсутствует.

Чтобы вычислить список целевых утверждений

G1, G2, …, Gm

процедура вычислить делает следующее:

• Если список целей пуст - завершает работу успешно.
• Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию «ПРОСМОТР».
• ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.
• Если С найдено и имеет вид
• H :- B1, …,Bn.
• то переменные в С переименовываются, чтобы получить такой вариант С предложения С, в котором нет общих переменных со списком G1, …, Gm. Пусть С - это
• H :- B1, …, Bn.
• Сопоставляется G1 c H; пусть S - результирующая конкретизация переменных. В списке целей G1, G2, …, Gm, цель G1 заменяется на список B1, …, Bn, что порождает новый список целей:
• B1, …, Bn,G2, …, Gm.
• (Заметим, что, если С факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой список, а следовательно, - привести к успешному завершению.)
• Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей
• B1, …, Bn, G2, …, Gm
• Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы.

Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С - предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.

Всякий раз, как рекурсивный вызов процедуры вычислить приводит к неуспеху, процесс вычислений возвращается к ПРОСМОТРУ и продолжается с того предложения С, которое использовалось последним. Поскольку применение предложения С не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение С), в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки аннулируются. Такой порядок обеспечивает систематическую проверку Пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.

Рассмотрим, основные операторы Пролога, которые нам понадобятся для дальнейших рассуждений.

) Для остановки механизма возвратного поиска используется предикат ! - gut ("отсечение" или "замораживание"). При этом сохраняются значения переменных, которые они получили к данному моменту [3]. Отсечение следует применять в тех случаях когда:

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

Смысл механизма отсечения можно сформулировать так:

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

) Абстрактные типы данных (АТД) - типы данных, рассматриваемые независимо от способов их представления или реализации средствами языка программирования. АТД определяются множеством значений и совокупностью опреаций, которые могут выполняться над значениями данного типа [3]. Примерами АТД являются строки и массивы.

Список представляет собой упорядоченную последовательность данных. Его также можно представить в виде структуре, имеющей два компонента: заголовок (голова) и остаток (хвост). В частности, если список состоит из одного элемента, то ео хвост - пустой список. Таким образом, список имеет рекурсивную составную структуру данных. Рекурсивное определение выглядит так:

пустой список является списком;

объект, имеющий голову и хвост, является списком, если его хвост список.

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

) Внутренние базы данных

Различают статистическую и динамическую внутренние базы данных. Первая представляется в программе в виде фактов (в разделе clauses). Вторая состоит из фактов, которые добавляются и удаляются в оперативной памяти во время выполнения программы (утверждения динамической базы данных формируются в виде предикатов в разделе database) [3].

В случае, если необходимо не просто получить последовательность решений какого-либо целевого утверждения, полученных из внутренней базы данных (статистической или динамической), а обработать сразу все решения как часть единой составной структуры данных, используется встроенный предикат findall. У предиката findall три аргумента: имя переменной-параметр, который нужно собрать в список; имя предиката, из которого надо собрать значения; и список значений, собранных с помощью метода поиска с возвратом.

Таким образом, процедурная семантика Пролога моделирует недетерминированный выбор редуцирующего правила с помощью последовательного поиска и механизма возврата [13]. Следовательно, Пролог для решения логических задач применяет только метод формального перебора списка подцелей.

Реализация сетевых моделей на Прологе.

В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро парой вершин [1]. Если каждая вершина графа соединена ребром еще, по крайней мере, с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку неявным образом содержится в списке ребер. Еще один способ представления графа - связать с каждой вершиной список смежных вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины плюс ее список смежности.

Какой из способов для представления графов более удобным, зависит от того, какие операции имеются в виду выполнять над графами. Вот типичные операции:

найти путь между двумя заданными вершинами;

найти подграф, обладающий некоторыми заданными свойствами.

Рассмотрим подробнее понятие списка в Прологе.

Список - это в самом общем смысле, структура, которая либо

• пуста, либо
• состоит из головы и хвоста, причем хвост должен быть сам списком.

Список рассматривается в Прологе как специальный частный случай двоичного дерева [1]. Для повышения наглядности программ на Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде

[элемент1, элемент2, …]

или

[голова | хвост]

или

[элемент1, элемент2, …| остальные].

Списки можно применять для представления упорядоченных множеств, хотя и существует некоторое различие между этими понятиями: один и тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них

проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;

конкатенация (сцепления) двух списков, что соответствует объединению множеств;

добавление нового объекта в список или удаление некоторого объекта из него.

Реализация рассмотренных сетевых моделей на Прологе приведена ниже.

1)Программа на Прологе для задачи на нахождение гамильтонова цикла на заданном фрагменте сети:

Domains % Раздел определения типов данных

spisok=integer*

sp=symbol*

Predicates % Раздел описания заголовков предикатов

цепь (symbol, integer, sp, spisok, integer)

всп_цепь (symbol, integer, sp, sp, spisok, integer)

дуга (symbol, symbol, integer, integer)

ребро (symbol, symbol, integer, integer)

принадлежит (symbol, sp)

количество (spisok, integer, integer)

цикл (symbol, integer, sp, spisok)

итог (symbol, integer, sp, spisok)

минимум (spisok, integer)

последний (sp, symbol)

Goal % Раздел описания цели, в которомрасполагается целевое утверждение итог (a, I, L,Y).

Clauses % Раздел описания фактов и правил

дуга(x,v1,1,2). % факты предиката дуга()

дуга(v1,v2,2,1).

дуга(v2,v3,3,1).

дуга(v2,v3,4,3).

дуга(v3,v4,5,1).

дуга(v1,v4,6,1).

дуга(v3,v4,7,1).

дуга(v4,y,7,1).

дуга(x,y,7,1).

дуга(x,y,7,4).

итог(X,D,L,P):-findall(K, цикл(_,K,_,_),U), минимум(U,D), цикл(X,D,L,P).

цикл(X,D,L,P):-findall(K, цепь(K,_,_,_,_,_),M), количество (M,R,_), цепь(X,D,L,P,R).

цепь (X,D,L,P,R):- всп_цепь (X,D,L,[],P,R).

всп_цепь (X,D,[X,Y],K,[N],1):-ребро (X,Y,N,D), последний(K,Y).

всп_цепь(X,D,[X|L],K,[N|P],R):- ребро(X,Z,N,D1), not(принадлежит(Z,K)), R1=R-1, всп_цепь (Z,D2,L,[X|K],P,R1), D=D1+D2.

ребро(P,T,H,N):-дуга(P,T,H,N).

ребро(P,T,H,N):-дуга(T,P,H,N).

принадлежит (X,[X|_]):-!.

принадлежит (X,[_|L]):- принадлежит (X,L). % определяет принадлежность элемента списку

минимум ([X],X). % возвращает минимальный элемент списка

минимум ([X|T],M):- минимум (T,M),M<=X,!.

минимум ([X|_],X).

последний ([X],X). % возвращает последний элемент в списке

последний ([_|T],X):- последний (T,X).

количество ([ ],0,0). % определяет количество элементов в списке

количество ([X|C],D,S):- количество (C,D1,S1),D=D1+1,S=S1+X.

2)Программа на Прологе для задачи на нахождение эйлерова цикла в заданном фрагменте сети:

Domains % Раздел определения типов данных

spisok=integer*

Predicates % Раздел описания заголовков предикатов

путь (symbol, symbol, spisok)

всп_путь (symbol, symbol, spisok, spisok)

дуга (symbol, symbol, integer)

ребро (symbol, symbol, integer)

принадлежит (integer, spisok)

длина (spisok, integer)

цикл (symbol, symbol, spisok)

Goal % Раздел описания цели, в которомрасполагается целевое утверждение

цикл(a,a,P).

Clauses % Раздел описания фактов и правил

дуга (a,b,1). % факты предиката дуга()

дуга (b,c,2).

дуга (b,c,3).

дуга (d,e,4).

дуга (e,c,5).

дуга (e,b,6).

дуга (e,d,5).

дуга (a,e,6).

цикл(T,I,E):-findall(K,дуга(_,_,K),L),длина(L,R),путь(T,I,E),длина(E,R).

путь(X,Y,L):-всп_путь(X,Y,L,[]). % правила предиката путь()

всп_путь(X,Y,[N],P):-ребро(X,Y,N),not(принадлежит(N,P)).

всп_путь(X,Y,[N|R],P):-ребро(X,Z,N),not(принадлежит(N,P)),всп_путь(Z,Y,R,[N|P]).

ребро(P,T,H):-дуга(P,T,H). % правила предиката ребро()

ребро(P,T,H):-дуга(T,P,H).

принадлежит(X,[X|_]):-!. % определяет принадлежность элемента списку

принадлежит(X,[_|L]):-принадлежит(X,L).

длина([],0). % определяет количество элементов в списке

длина([_|B],K):-длина(B,K1),K=K1+1.

2 Разработка учебных экспертных систем с помощью логического программирования

Классификация задач по логическому программированию.

Одной из дидактических задач дисциплины "Основы ИИ", как нами было выделено выше, является знакомство с приемами логического программирования. В данном пункте проводится обзорный анализ учебно-методической литературы по логическому программированию ([1],[13],[5]).

Как отмечает автор [14], большинство задач, которые считаются логическими, сводятся к задаче нахождения пути в некотором графе - графе состояний задачи. Характерными особенностями этих задач является следующее:

1)наличие неких дискретных состояний, число которых конечно; чаще всего в этих задачах имеется начальное состояние, с которых начинается поиск;

2)определены правила перехода между состояниями;

)для каждого состояния заданы определенные условия допустимости (оценки) этого состояния.

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

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

Выделим ряд учебных задач, которые применяются при обучении логическому программированию: задачи на запросы к базе данных Пролог-программы; задачи на логические связи между объектами; задачи на описание базы знаний предметной области с выводом новых отношений; задачи на построение транзитивных замыканий существующих отношений; логические задачи на поиск решения; содержательные учебные задачи ИИ.

1.Задачи на запросы к базе данных Пролог-программы.

• Пусть дана база знаний "Спортивные увлечения".

летний (бег).

летний (плавание).

зимний (лыжи).

зимний (коньки).

спорт (Иван, бег).

спорт (Семен, плавание).

спорт (Петр, Х):- спорт (Иван, Х), зимний(Х).

Не определяя новых правил, сформулируйте вопросы:

• Какими видами спорта занимается Петр?
• Существуют ли такие одинаковые виды спорта, которыми занимаются Иван и Петр?
• Занимается ли Семен каким-нибудь летним видом спорта? [6]
• Описать базу знаний "Отборочные соревнования", в которой даны результаты прохождения лыжниками дистанций длиной 5 км и 10 км (в минутах). Если лыжник прошел 5 км за время, не превышающее 17 минут, а 10 км - менее чем за 35 минут, то он допускается к участию в соревнованиях. Сформулируйте следующие вопросы:
• Кто из лыжников пробежал дистанцию 5 км не более чем за 17 минут? Каково это время?
• Кто из лыжников допущен к участию в соревнованиях?
• Перечислить пары лыжников, из которых можно составить команду для участия в эстафетной гонке. В команду могут быть зачислены любые два лыжника, допущенные к участию в соревнованиях. (В ответе не должно появляться повторяющихся решений.) [6]
• Описать базу знаний "Крупнейшие озера земного шара", используя информацию из таблицы?

НазваниеПлощадьНаибольшая глубинаКаспийское море (Европа, Азия)394,3980Верхнее озеро (Сев. Америка)82,4308Виктория (Африка)6880Гурон (Сев. Америка)59,6222Мичиган (Сев. Америка)58263Танганьика (Африка)32,91453Байкал (Азия)31,51742Аральское море (Азия)66,568

Сформулируйте цели и ответьте на них:

• Какие озера расположены в Африке и Азии?
• Существует ли в Северной Америке озера, глубина которых меньше 300 метров (неглубокие), а также озера, глубина которых больше 800 метров (глубокие)?
• Какие озера расположены в Европе и на каких материках глубина озер находится в пределах от 400 до 1500 метров? [6]

2.Задачи на логические связи между объектами.

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

Кто чем занимается?

• Имеются два сосуда - на 3 и на 5 литров. Как отмерить с их помощью 4 литра воды? [6]

3.Задачи на описание базы знаний предметной области с выводом новых отношений.

• Определить базу знаний "Транспорт" по данной схеме движения транспорта.

Определить:

Можно ли доехать из города В в город Е?

В какие города можно доехать из города D?

Из каких городов можно доехать до города Е?

4) Можно ли доехать из города А в город D или в город F? [6]

• Дана база знаний "Автобусы". На схеме показано, между какими населенными пунктами курсирует автобус.

Если нет автобусного сообщения, то единственным транспортным средством является автомобиль. Описать отношения, позволяющие определить, каким видом транспорта можно доехать из одного населенного пункта в другой. Сформулировать вопросы и ответить на них:

• На каком виде транспорта можно доехать из пункта В в пункт Г?
• Можно ли доехать на автобусе из К в Л?
• В какие населенные пункты придется ехать на автомобиле из пункта Б? [6]

4.Задачи на построение транзитивных замыканий существующих отношений.

• Некоторая авиакомпания обеспечивает прямые рейсы между некоторыми городами, сведения о которых хранятся в программе в виде фактов (для упрощения задачи обратные рейсы исключены). Запрограммируйте рекурсивный предикат perelet, который определяет, можно ли попасть из одного города в другой (может быть, с пересадками) [3].
• В районе расположено несколько сел. Есть данные о наличии дорог между ними (в одну сторону) и их длине, которые хранятся в виде фактов предиката doroga.

Напишите предикат put, определяющий, можно ли попасть из одного села в другое, и какова суммарная протяженность дороги между ними [3].

5.Логические задачи на поиск решения.

• Напишите программу, которая решает следующую задачу: нарисовать конверт, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии. Результатом выполнения программы будет список пройденных вершин [14].
• Задача состоит в том, чтобы такую расстановку восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого [1].

6. Содержательные учебные задачи ИИ

К данному разделу мы отнесли задачи, где моделируется система с различными состояниями, переход между которыми осуществляется по законам человеческой логики.

К классическим задачам такого типа относится задача "Обезьяна и банан":

Возле двери комнаты стоит обезьяна. В середине этой комнаты к потолку подвешен банан. Обезьяна голодна и хочет съесть банан, однако она не может дотянуться до него, находясь на полу. Около окна этой же комнаты на полу лежит ящик, которым обезьяна может воспользоваться. Обезьяна может предпринимать следующие действия: ходить по полу, залезать на ящик, двигать ящик (если она уже возле него) и схватить банан, если она стоит на ящике прямо под бананом. Может ли обезьяна добраться до банана?

Как системы искусственного интеллекта рассматриваются игры со стратегиями. К учебной задаче можно отнести, например, игру в "пятнашки", "крестики-нолики", шахматные задачи.

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

Применение логического программирования для реализации экспертных систем.

Экспертные системы (ЭС) - это сложные программные комплексы, аккумулирующие знания специалистов в конкретных предметных областях и тиражирующие этот эмпирический опыт для консультаций менее квалифицированных пользователей. [1]

Обобщенная структура экспертной системы представлена на рисунке 6.

База знаний содержит знания, относящиеся к конкретной прикладной области, в том числе отдельные факты, правила, описывающие отношения или явления, а также возможно методы, эвристики и различные идеи, относящиеся к решению этих задач в этой прикладной области. Машина логического вывода умеет активно использовать информацию, содержащуюся в базе знаний. Интерфейс с пользователем отвечает за бесперебойный обмен информацией между пользователем и системой; он также дает пользователю возможность наблюдать за процессом решения задач, протекающим в машине логического вывода. Принято рассматривать машину вывода и интерфейс как один крупный модуль, обычно называемый оболочкой экспертной системы, или для краткости, просто оболочкой [1].

На самом деле реальные экспертные системы могут иметь более сложную структуру, однако блоки, изображенные на рисунке, непременно присутствуют в любой экспертной системе.

Рассмотрим этапы разработки прототипа учебной экспертной системы. Объем прототипа - несколько десятков правил. При разработке прототипа учебной ЭС особое значение имеют следующие этапы: структурирование или концептуализация знаний, формализация, реализация, тестирование.

При структурировании знаний выявляется структура полученных знаний о предметной области, т.е. определяются [8]:

• терминология;
• список основных понятий и атрибутов;
• отношения между понятиями;
• структура входной и выходной информации;
• стратегия принятия решений и т.д.

Концептуализация знаний - разработка неформального описания знаний о предметной области в виде графа, таблицы, диаграммы или текста, который отражает основные концепции и взаимосвязи между понятиями предметной области.

На этапе формализации строится формализованное представление концепций предметной области на основе выбранного языка представления знаний. Формализация знаний - разработка базы знаний на языке, который, с одной стороны, соответствует структуре модели предметной области, а с другой - позволяет реализовать прототип системы на следующей стадии программной реализации.

Реализация - разработка программной системы, построение прототипа, включающего базу знаний, при помощи одного из способов:

• программирование на традиционных языках типа Паскаль, Си и др.;
• программирование на специализированных языках, применяемых в задачах ИИ: Лисп, Пролог и т.д.;
• использование инструментальных средств разработки ЭС типа СПИЭС, ПИЭС:
• использование "пустых" ЭС или "оболочек" типа ЭКСПЕРТ, ФИАКР и др. [8]

Тестирование - выявление ошибок в подходе и реализации прототипа. Прототип проверяется на:

• удобство и адекватность интерфейсов ввода-вывода;
• эффективность стратегии управления;
• качество проверочных примеров;
• корректность базы знаний.

При разработке ЭС на Прологе схему экспертной системы можно уточнить:

Примеры построения экспертных систем на Прологе приведены в учебнике И. Братко разобран пример учебной ЭС «Животные», предназначенной для идентификации животных. В базе знаний этой системы имеются правила, определяющие принадлежность животного к какому-либо классу, виду и т.д. Разработана оболочка, интерпретирующая «если-то» - правила, которая обеспечивает выдачу объяснений типа «как» и «почему» и которая запрашивает у пользователя нужную ему информацию. На вопрос «Почему» («Почему вас интересует текущая цель?») дается объяснение в виде цепочки правил и целей, соединяющих текущую цель с исходным вопросом пользователя, находящимся в верхушке дерева вопросов. Одним из подходящих способов ответить на вопрос "как" - это представить доказательство, т.е. те правила и подцели, которые использовались для достижения полученного заключения. Это доказательство имеет вид решающего дерева, составленного из имен правил и подцелей. В качестве объяснения типа "как" на выходе системы будет отобраться это дерево. Эта система состоит из следующих программ на Прологе:

для процедуры «рассмотреть», являющаяся основной процедурой оболочки ЭС, которая находит ответ на заданный вопрос;

для процедуры "ответ_польз", которая реализует вопросы к пользователю и ответы на вопросы "почему";

для процедуры "выдать", которая отображает окончательный результат и объяснение типа "как".

Прототип учебной экспертной системы

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

С точки зрения методики преподавания необходимо выбрать предметную область достаточно хорошо знакомую студентам. В качестве прототипа ЭС мы предлагаем реализовать прототип учебной ЭС «Справочная система туристической фирмы». База знаний для этой системы будет состоять из базы данных различных маршрутов между набором населенных пунктов, правил перемещения между ними и запросов: существует ли возможность путешествия по всем населенным пунктам с минимальным расстоянием и возможность проезда по всем маршрутам с возвратом в начальный пункт. Обоснование правильности вывода ЭС для пользователя состоит в выводе списка населенных пунктов в порядке посещения или списка маршрутов в порядке их прохождения.

Для разработки студентами прототипа данной ЭС предлагаем использовать:

) модель преставления знаний предметной области в виде семантической сети;

) логическую модель предметной области на языке предикатов 1-го порядка.

При проектировании прототипа учебной ЭС на этапе структурирования знаний представляем модель предметной области в виде семантической сети.

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

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

Для тестирования системы можно воспользоваться теоремами о существовании эйлерова и гамильтонова циклов (См. П.2, П.3. §3 глава1).

§3. Организация обучения студентов решению задач теории графов на Прологе

Характеристика проблемного обучения.

Рассмотрим основные понятия и особенности, относящиеся к теории проблемного обучения.

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

Важнейшей чертой содержательного аспекта проблемного обучения является отражение объективных противоречий, закономерно возникающих в процессе научного познания, учебной или другой деятельности, которые и есть источник движения и развития [7].

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

Проблемное обучение осуществляется в трех основных формах: а) проблемного изложения материала преподавателем в лекциях (так называемые проблемные лекции); б) частично-поисковой деятельности студентов при участии преподавателя во время проведения семинарских и лабораторных занятий; в) самостоятельного исследования и решения проблемной ситуации, осуществляемого студентами под руководством преподавателя при написании рефератов, курсовых работ, дипломных проектов, а также при выполнении студентами исследовательской работы в научных кружках, в отраслевых лабораториях [22].

Ключевым понятием проблемного обучения является "проблемная ситуация", которая создается преподавателем с учебной целью. Проблемная ситуация - это психологическое состояние затруднения, невозможность объяснить факт или решить задачу с опорой на имеющиеся знания [18]. Она включает сложный теоретический или практический вопрос, требующий изучения, расширения, исследования в сочетании с определенными условиями и обстоятельствами, создающими ту или иную обстановку (ситуацию). Уровни проблемного обучения зависят от содержания учебного материала (наличие возможности создать проблемные ситуации различной степени трудности) и типа самостоятельных действий студента. По этим признакам специалисты правомерно выделяют четыре проблемности: 1) уровень, обусловливающий репродуктивную деятельность; 2) уровень, обеспечивающий применение прежних знаний в новой ситуации; 3) репродуктивно-поисковый уровень; 4) творческий уровень [22].

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

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

Все указанные противоречия возникают из-за дисбаланса между теоретической и практической информацией, избытком одной и недостатком другой, или наоборот.

Проблемная ситуация на основе анализа преобразуется в проблемную задачу. Проблемная задача ставит вопрос или вопросы: «Как разрешить это противоречие? Чем это объяснить?» Серия проблемных вопросов трансформирует проблемную задачу в модель поисков решений, где рассматриваются различные пути, средства и методы решения. В классификации проблемных задач выделяют задачи с неопределенностью условий, с избыточными, противоречивыми, частично неверными данными.

Методические указания по обучению решению задач теории графов.

Одним из методов обучения решению сложных задач является ее разбиение на более простые подзадачи; важным моментом является определение способа разбиения задач по сложности. Заметим, что в разработке реальных программных систем применяются структурные методы «сверху-вниз» и «снизу-вверх» [14]; последний из них означает постепенное укрупнение разрабатываемой системы. Таким образом, при обучении программированию естественно разбить построение исходной системы на ряд этапов, на каждом из которых решается более сложная относительно программирования задача. Конечный этап - построение всей системы.

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

• Некоторая авиакомпания обеспечивает прямые рейсы между n городами. Турист желает посетить все n городов по одному разу и вернуться в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным (сводится к нахождению гамильтонова цикла).
• В некотором районе ДРСУ проводит ремонт дорог между населенными пунктами. Прораб ДРСУ каждый день должен следить за работой на этих дорогах, и после работы возвращаться домой, при этом проезжая каждую из них по одному разу. Для отчета ему необходимо предоставить список названия дорог в порядке их посещения за день (сводится к нахождению эйлерова цикла).

Предлагаем разбить каждую из задач на 3 подзадачи.

Для первой задачи предлагаем следующее разбиение на подзадачи:

) Некоторая авиакомпания обеспечивает прямые рейсы между n городами. Определить есть ли возможность перелета из одного города в другой (рейсы считаем однонаправленными).

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

) Некоторая авиакомпания обеспечивает прямые рейсы между n городами (рейсы считаем двунаправленными). Проверяем, существует ли путь из одного города в другой, при этом запоминая посещенные города. Зная, расстояние между города, найти длину данного пути.

Для решения задачи на этом этапе студентам необходимо познакомиться с таким типом объектов, как списки, которые являются наиболее используемыми при программировании на Прологе. Студенты разбирают основные методы работы со списками и здесь же знакомятся с предикатом «отсечения», который используется для остановки возвратного поиска в Прологе. Также при решении этой задачи студенты могут использовать средства динамических баз данных в Прологе.

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

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

Разбиение задачи про прораба ДРСУ будет следующим:

1) В некотором районе ДРСУ проводит ремонт дорог между населенными пунктами. Выяснить, имеет ли возможность прораб попасть из одного населенного пункта в другой, если по дорогам установлено одностороннее движение.

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

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

Для решения задачи на этом этапе студентам необходимо познакомиться с таким типом объектов, как списки, которые являются наиболее используемыми при программировании на Прологе. Студенты разбирают основные методы работы со списками и здесь же знакомятся с предикатом «отсечения», который используется для остановки возвратного поиска в Прологе. Также при решении этой задачи студенты могут использовать средства динамических баз данных в Прологе.

) В некотором районе ДРСУ проводит ремонт дорог между населенными пунктами. Выяснить, существует ли возможность, выехав из некоторого населенного пункта, проехать по всем дорогам по одному разу и вернуться в начальный пункт. В качестве доказательства этого пути прорабу необходимо представить список посещенных дорог.

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

Далее студентам на закрепление предлагается решить классический вариант задач и ряд подобных им задач.

Задача № 1: Пусть конь стоит на любом поле шахматной доски. Определите хотя бы одну непрерывную траекторию, вдоль которой должен перемещаться конь, чтобы, побывав по одному разу в каждой клетке доски, вернуться последним ходом в исходную позицию [16].

Одон из вариантов решения этой задачи изображен в таблице.

63221540142591814396421601724337622316414195824133861205744311362552294655626511233855304535104928533247650273494875431

Задача №2: Можно ли прогуляться по парку и его окрестностям (см. рис.) так, чтобы перелезть через каждый забор ровно один раз?

Задача №3: На рисунке 5 план подземелья (слева), в одной из комнат которого скрыты богатства сеньора. После смерти его наследники нашли завещание, в котором было сказано, что для отыскания сокровищ достаточно войти в одну из крайних комнат подземелья, пройти через все двери, причем в точности по одному разу через каждую; сокровища скрыты за той дверью, которая будет последней [4].

Задача №4: Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается [17].

Факультативное занятие «Решение классических задач теории графов на Прологе».

Была проведена апробация, предложенной нами методики изложения данных задач в форме факультативного занятия для дисциплины программирования раздела «Языки программирования ИИ». Условия эксперимента - предварительное знакомство студентов с языком программирования Пролог. В апробации принимали участие 20% студентов третьего курса, обучающиеся по специальности "математика - информатика". 50% из них хорошей успеваемости, 50% - отличной успеваемости. Ниже приведен конспект проведенного занятия.

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

Тема: Решение классических задач теории графов на Прологе

Цель: Решение задач, сводимых к поиску на графе эйлерова и гамильтонова циклов.

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

Для начала решим более простую задачу.

1. Будем считать, что движение по дорогам возможно только в одном направлении. И пусть у прораба есть возможность переночевать в другом населенном пункте, т.е. не возвращаться домой.

Как мы должны поступить с графом, который соответствует начальным условиям задачи?

Мы нашим дорогам должны задать направление.

Как теперь будем решать эту задачу?

Напишем предикат, определяющий можно ли вообще попасть из одного населенного пункта в другой. Проверим, есть ли путь из 2 в 5; укажите, в какие села есть возможность попасть из села 3; из каких сел можно доехать в село 4.

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

Каким образом мы можем поступить, для того чтобы избежать этого?

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

Какая структура Пролога позволяет нам запомнить множество однородных элементов?

Списки.

1. Вспомогательный блок

Для решения данной задачи и в дальнейшем нам понадобятся некоторые вспомогательные предикаты для работы со списками:

1)предикат, проверяющий принадлежность элемента списку;

2)предикат, ставящий в соответствие списку его длину;

)предикат, ставящий в соответствие списку его последний элемент.

Напишем определение для этих предикатов на Прологе.

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

1. Теперь предложим возможность прорабу проезжать по дорогам в любом направлении.

Каким образом на Прологе мы можем задать двунаправленность дорог?

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

Посмотрим, существует ли путь из села 1 в село 2. Видим, что таких путей несколько.

Какие это пути? Хотелось бы узнать список пройденных дорог в каждом из путей, тем более это соответствует второму требованию исходной задачи.

Каким образом мы можем добиться нужного нам результата?

Нужно добавить выводимую переменную - список.

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

1. Как мы можем проверить прохождения всех дорог, что мы можем использовать?

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

Для этого нам понадобится предикат, ставящий в соответствие списку его длину.

Каким способом будем решать?

Используя первую возможность, мы видим, что данный предикат работает неэффективно, т.к. при каждом изменении базы данных нам необходимо менять и содержание программы, а точнее число в предикате dlina. Давайте попробуем решить задачу вторым способом.

Более эффективным является второй способ, в котором сравнение длин списков происходит автоматически (нужно использовать предикат findall).

Итак, исходная задача решена? Давайте еще раз просмотрим все этапы решения задачи. Что мы делали на первом этапе, что на втором, на третьем?

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

На втором этапе: дали возможность двигаться по дорогам в любом направлении; создали список, в котором вывели порядок посещения дорог.

На третьем этапе: проверили возможность обхода всех дорог, при этом использовали предикат findall.

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

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

Граф, в котором существует, такой цикл называется эйлеровым графом.

Значит нам, необходимо узнать является ли граф, изображенный на рисунке справа, эйлеровым. Имеется простая теорема для распознавания таких графов.

Теорема: Для того чтобы граф был эйлеровым необходимо и достаточно четности степеней его вершин.

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

domains=integer*

(symbol,symbol,spisok,integer)% откуда-куда-промежуточные(symbol,symbol,spisok,spisok,integer)% откуда-куда-промежут-посещенные(symbol,symbol,integer,integer)% откуда-куда-номер моста(symbol,symbol,integer,integer) % двунаправленность мостов

prin(integer,spisok)% принадлежность элемента списку

dlina(spisok,integer) % длину списка(symbol,symbol,integer,spisok) %(i,i,o)

(a,a,F,Q).

(a,b,1,1).(a,b,2,1).(a,c,3,1).(a,c,4,1).(c,d,5,1).(a,d,6,1).(b,d,7,1).

(T,I,Q,E):-findall(K,most(_,_,K,_),L),dlina(L,R),put(T,I,E,Q),dlina(E,R).(X,Y,L,Q):-vput(X,Y,L,[],Q).(X,Y,[N],P,Q):-smost(X,Y,N,Q),not(prin(N,P)).(X,Y,[N|R],P,Q):-smost(X,Z,N,Q1),not(prin(N,P)),vput(Z,Y,R,[N|P],Q2), Q=Q1+Q2.(P,T,H,N):-most(P,T,H,N).(P,T,H,N):-most(T,P,H,N).(X,[X|_]):-!.(X,[_|L]):-prin(X,L).([],0).([_|B],K):-dlina(B,K1),K=K1+1.

Рассмотрим несколько иную задачу: Некоторая авиакомпания обеспечивает прямые рейсы между n городами. Турист желает посетить все n городов по одному разу и вернуться в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным.

Решим более простую задачу.

I. Пусть у нас имеется возможность лететь из одного города в другой только в одном направлении (в качестве модели используем взвешенный ориентированный граф). И пусть турист в каждом городе покупает сувенир, который имеет определенный вес.

С чего начнем решение задачи?

База данных для этого графа будет следующей.

("Богота", «Москва"). ves("Москва",1).("Москва", «Лондон"). ves("Богота",1).("Москва", «Токио"). ves("Лондон",1).("Токио", «Богота"). ves("Токио",1).("Рим", «Лондон"). ves("Рим",1).("Лондон", «Вашингтон"). ves("Вашингтон",1).("Вашингтон", «Нью-Йорк"). ves("Нью-Йорк",1).("Нью-Йорк", «Мехико"). ves("Мехико",1).("Мехико", «Богота").("Рим", «Мехико").

Давайте, определим вес сувенира, привезенный при одном рейсе, и узнаем:

§Количество веса при рейсе из Боготы в Москву;

§В какие города можно попасть из Боготы, зная, что турист может привести не более 20 кг груза;

§Из каких городов, возможно, попасть в Москву, чтобы конечный груз был равен 12 кг.

Что мы теперь можем сделать? Как усложним задачу?

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

Проверим, существует ли путь из Москвы в Мехико. Видим, что произошло зацикливание.

Что нужно сделать, чтобы этого избежать?

Необходимо, как и предыдущей задачи запоминать пройденные города (!) и при каждом новом шаге проверять принадлежность данного города (вершины) списку уже пройденных городов.

Посмотрим, существует ли путь из Лондона в Мехико. Видим, что таких путей много и хотелось бы посмотреть, какие города мы в данном пути посетили.

III. Значит, аналогично предыдущей задаче добавляем в предикат put список посещенных городов.

Вспомним условие исходной задачи: нам кроме всего того, что мы уже сделали, требуется возвращение в тот же аэропорт, из которого мы вылетели. Как этого можно достичь? Существует следующая возможность: в определении вспомогательного предиката vput, в прямом правиле вместо проверки принадлежности города списку посещенных городов, ставим предикат, который будет проверять, является ли последний посещенный город последним в списке посещенных городов.

По аналогии с предыдущей задачей пишем предикат itog с двумя аргументами: начальный пункт, список пройденных городов.

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

Нужно минимизировать полученные расстояния.

Что для этого необходимо сделать?

Используя findall, собираем в список все пути и находим минимум расстояния.

Самоанализ

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

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

В ходе предварительного опроса были выявлены знания студентов и выделены две подгруппы.

подгруппа - хорошей успеваемости, поэтому для решения была выбрана лишь одна задача: задача Эйлера. Время, затраченное на решение этой задачи - 2 учебных часа.

подгруппа - отличная успеваемость, были решены обе задачи. Время, затраченное на решения двух задач 3,5 учебных часа. Вторая задача была решена несколько быстрее, нежели первая, т.к. стратегии решения этих задач похожи.

Итоги: Все студенты усвоили материал. Контрольное время решения подобной задачи составило 1 учебный час.

Заключение

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

Все поставленные задачи в дипломной работе были выполнены. Получены следующие результаты:

На основе анализа литературы и документов министерства образования РФ выделены основные вопросы, изучаемые в рамках дисциплины «Основы искусственного интеллекта».

Проведен сравнительный анализ дидактических возможностей различных моделей в данной дисциплине.

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

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

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

Проведена классификация задач по логическому программированию и выделен класс задач, который относится к задачам искусственного интеллекта.

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

Проведено факультативное занятие по теме: «Решение классических задач теории графов на Прологе» со студентами третьего курса, обучающихся по специальности «математика-информатика».

Можно сделать вывод о том, что методика обучения разработке программных систем искусственного интеллекта на основе логического программирования с использованием сетевых моделей допустима в преподавании дисциплины «Основы искусственного интеллекта» для студентов педагогической специальности "информатика".

Список литературы

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. - М.: Мир, 1990. - 560 с.
2. Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных. Вводный курс: Учебное пособие. - М.: Гелиос АРВ, 2002. - 368 с.
3. Дудышева Е.В. Основы логического и функционального программирования: методические материалы для проведения лабораторных работ. - Бийск: НИЦ БиГПИ, 2000. -70 с.
4. Евстигнеев В.А., Касьянов В.Н. Толковый словарь по теории графов. Часть1,2,3 / Новосибирск, 1996.
5. Загорулько Ю.А., Телерман В.В., Яхно Т.М. Введение в логическое программирование: методическое пособие. Часть 1. - Новосибирск, 1997. - 91
6. Залогова Л.А. Язык программирования Пролог // Информатика. - 2004. -№12,16,18,20.
7. Ильина Т.А. Педагогика: Курс лекций. Учебное пособие для студентов пед. ин-тов. - М.: Просвещение, 1984.- 496с.
8. Информатика: Учебник/ под ред. проф. Н.В. Макаровой. - М.: Финансы и статистика, 1998. - 768с.
9. Информатика. Систематический курс. Учебник для 11 класса / С.А. Бешенков, Н.В. Кузьмина, Е.А. Ракитина. - М.: Бином. Лаборатория Знаний, 2002. - 200 с.
10. Каймин В.А. Информатика: Учебник. - М.: ИНФРА - М, 2001. - 272 с.
11. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978
12. Лапчик М.П., Семакин И.Г., Хеннер Е.К. Методика преподавания информатики
13. Малпас Дж. Реляционный язык Пролог и его применение: Пер. с англ./ Под ред. В.Н. Соболева - М.: Наука., 1990. - 464 с.
14. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учеб. пособие для студ. пед. вузов - М.: «Академия», 2001. - 816 с.
15. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2003. - 304 с.
16. Оре О. Теория графов: Пер. с англ./ Под ред. Н.Н. Воробьева - М.: Наука, 1968. - 352 с.
17. Оре О. Графы и их применение. - М.: Мир, 1965
18. Педагогика. Учебное пособие для студентов пед. вузов и пед. колледжей / Под ред. П.И. Пидкасистого. - М.: Педагогическое общество России, 1998. - 640 с.
19. Першников В.И., Савинков В.М. Толковый словарь по информатике. - М.: "Финансы и статистика", 1991. - 497 с.
20. Столяренко Л.Д., Самыгин С.И. Педагогика. 100 экзаменационных ответов. Экспресс-справочник для студентов вузов. - Ростов н\Д: "МарТ", 2000. -256с.
21. Хювенен Э., Сеппянен Й. Мир Лиспа, Том 2: Методы и системы программирования. - М.: Мир, 1983.

Приложение 1

«Реализация задачи коммивояжера и задачи китайского почтальона на Прологе».

Задача коммивояжера: Имеется n городов, расстояния между которыми известны. Коммивояжер должен посетить все n городов по одному разу, вернувшись в тот с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным. Математическая постановка этой задачи состоит в следующем: во взвешенном графе требуется найти гамильтонов цикл наименьшего веса.

Сетевые модели для каждого шага решения задачи коммивояжера.

Программа на Прологе для задачи коммивояжера:

Domains=integer*=symbol*

цепь (symbol, integer, sp, spisok, integer)

всп_цепь (symbol, integer, sp, sp, spisok, integer)

дуга (symbol, symbol, integer, integer)

ребро (symbol, symbol, integer, integer)

принадлежит (symbol, sp)

количество (spisok, integer, integer)

цикл (symbol, integer, sp, spisok)

итог (symbol, integer, sp, spisok)

минимум (spisok, integer)

последний (sp, symbol)

итог (a, I, L,Y).

дуга(x,v1,1,2).

дуга(v1,v2,2,1).

дуга(v2,v3,3,1).

дуга(v2,v3,4,3).

дуга(v3,v4,5,1).

дуга(v1,v4,6,1).

дуга(v3,v4,7,1).

дуга(v4,y,7,1).

дуга(x,y,7,1).

дуга(x,y,7,4).

итог(X,D,L,P):-findall(K, цикл(_,K,_,_),U), минимум(U,D), цикл(X,D,L,P).

цикл(X,D,L,P):-findall(K, цепь(K,_,_,_,_,_),M), количество (M,R,_), цепь(X,D,L,P,R).

цепь (X,D,L,P,R):- всп_цепь (X,D,L,[],P,R).

всп_цепь (X,D,[X,Y],K,[N],1):-ребро (X,Y,N,D), последний(K,Y).

всп_цепь(X,D,[X|L],K,[N|P],R):- ребро(X,Z,N,D1), not(принадлежит(Z,K)), R1=R-1, всп_цепь (Z,D2,L,[X|K],P,R1), D=D1+D2.

ребро(P,T,H,N):-дуга(P,T,H,N).

ребро(P,T,H,N):-дуга(T,P,H,N).

принадлежит (X,[X|_]):-!.

принадлежит (X,[_|L]):- принадлежит (X,L).

минимум ([X],X).

минимум ([X|T],M):- минимум (T,M),M<=X,!.

минимум ([X|_],X).

последний ([X],X).

последний ([_|T],X):- последний (T,X).

количество ([ ],0,0).

количество ([X|C],D,S):- количество (C,D1,S1),D=D1+1,S=S1+X

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

Сетевые модели для задачи китайского почтальона.

Реализация на Прологе задачи Эйлера.

Domains=integer*

путь (symbol, symbol, spisok)

всп_путь (symbol, symbol, spisok, spisok)

дуга (symbol, symbol, integer)

ребро (symbol, symbol, integer)

принадлежит (integer, spisok)

длина (spisok, integer)

цикл (symbol, symbol, spisok)

цикл(a,a,P).

дуга (a,b,1).

дуга (b,c,2).

дуга (b,c,3).

дуга (d,e,4).

дуга (e,c,5).

дуга (e,b,6).

дуга (e,d,5).

дуга (a,e,6).

цикл(T,I,E):-findall(K,дуга(_,_,K),L),длина(L,R),путь(T,I,E),длина(E,R).

путь(X,Y,L):-всп_путь(X,Y,L,[]).

всп_путь(X,Y,[N],P):-ребро(X,Y,N),not(принадлежит(N,P)).

всп_путь(X,Y,[N|R],P):-ребро(X,Z,N),not(принадлежит(N,P)),всп_путь(Z,Y,R,[N|P]).

ребро(P,T,H):-дуга(P,T,H).

ребро(P,T,H):-дуга(T,P,H).

принадлежит(X,[X|_]):-!.

принадлежит(X,[_|L]):-принадлежит(X,L).

длина([],0).

длина([_|B],K):-длина(B,K1),K=K1+1.

Приложение 2

Этапы разработки прототипа учебной экспертной системы.

этап: структурирование и концептуализация знаний.

При структурировании знаний выявляется структура полученных знаний о предметной области, т.е. определяются:

• список основных понятий и атрибутов;
• отношения между понятиями;
• структура входной и выходной информации;
• стратегия принятия решений и т.д.

На этом же этапе проводим концептуализацию знаний, т.е. разрабатываем неформальное описание знаний о предметной области в виде однородной семантической сети, которая отражает основные концепции и взаимосвязи между понятиями предметной области.

этап: формализация знаний.

Формализация знаний - разработка базы знаний на языке, который, с одной стороны, соответствует структуре модели предметной области, а с другой - позволяет реализовать прототип системы на следующей стадии программной реализации.

На этом этапе строится формализованное представление концепций предметной области на основе выбранного языка представления знаний. В качестве такого языка предлагаем использовать язык формальной логики, а именно, исчисление предикатов 1-го порядка. Следовательно, на этапе формализации знаний нам необходимо разработать базу знаний для ранее полученной нами структуры, представленной в виде однородной семантической сети, на языке исчисления предикатов 1-го порядка.

этап: реализация прототипа учебной ЭС.

На данном этапе создается сам прототип учебной ЭС при помощи языка логического программирования, в частности, мы предлагаем использовать язык Пролог.

этап: тестирование программ прототипа учебной ЭС.

Тестирование - выявление ошибок в подходе и реализации прототипа.

Прототип проверяется на:

• эффективность стратегии управления;
• качество проверочных примеров;
• корректность базы знаний.

Введение Целью преподавания курса "Основы искусственного интеллекта" для студентов, обучающихся по специальности «информатика», являе

Больше работ по теме: