ПРОЛОГ для искуственного интеллекта


     редан официальный сайт |     

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

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

Расширение программы-примера с помощью правил
Процесс рассуждений
Объекты данных
Обработка символов

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

В средние века знание латинского и греческого языков являлось существенной частью образования любого ученого. Ученый, владеющий только одним языком, неизбежно чувствовал себя неполноценным, поскольку он был лишен той полноты восприятия, которая возникает благодаря возможности посмотреть на мир сразу с двух точек зрения. Таким же неполноценным ощущает себя сегодняшний исследователь в области искусственного интеллекта, если он не обладает основательным знакомством как с Лиспом, так и с Прологом - с этими двумя основополагающими языками искусственного интеллекта, без знания которых невозможен более широкий взгляд на предмет исследования.
Сам я приверженец Лиспа, так как воспитывался в Массачусетском технологическом институте, где этот язык был изобретен. Тем не менее, я никогда не забуду того волнения, которое я испытал, увидев в действии свою первую программу, написанную в прологовском стиле. Эта программа была частью знаменитой системы Shrdlu Терри Винограда. Решатель задач, встроенный в систему, работал в "мире кубиков" и заставлял руку робота (точнее, ее модель) перемещать кубики на экране дисплея, решая при этом хитроумные задачи, поставленные оператором.
Решатель задач Винограда был написан на Микропленнере, языке, который, как мы теперь понимаем, был своего рода Прологом в миниатюре. Любой прологоподобный язык заставляет программиста мыслить в терминах целей, поэтому, несмотря на все недостатки Микропленнера, достоинством этой программы было то, что в ее структуре содержались многочисленные явные указания на те или иные цели. Процедуры-цели "схватить", "освободить", "избавиться", "переместить", "отпустить" и т.п. делали программу простой и компактной, а поведение ее казалось поразительно разумным.
Решатель задач Винограда навсегда изменил мое программистское мышление. Я даже переписал его на Лиспе и привел в своем учебнике по Лиспу в качестве примера - настолько эта программа всегда поражала меня мощью заложенной в ней философии "целевого" программирования, да и само программирование в терминах целей всегда доставляло мне удовольствие.
Однако учиться целевому программированию на примерах лисповских программ - это все равно, что читать Шекспира на языке, отличном от английского. Какое-то впечатление вы получите, но сила эстетического воздействия будет меньшей, чем при чтении оригинала. Аналогично этому, лучший способ научиться целевому программированию - это читать и писать программы на Прологе, поскольку сама сущность Пролога как раз и состоит в программировании в терминах целей.
В самом широком смысле слова эволюция языков программирования - это движение от языков низкого уровня, пользуясь которыми, программист описывает, как что-либо следует делать, к языкам высокого уровня, на которых просто указывается, что необходимо сделать. Так, например, появление Фортрана освободило программистов от необходимости разговаривать с машиной на прокрустовом языке адресов и регистров. Теперь они уже могли говорить на своем (или почти на своем) языке, только изредка делая уступки примитивному миру 80-колонных перфокарт.
Однако Фортран и почти все другие языки программирования все еще остаются языками типа "как". И чемпионом среди этих языков является, пожалуй, современный модернизированный Лисп. Так, скажем, Common Lisp, имея богатейшие выразительные возможности, разрешает программисту описывать наиболее "выразительно" именно то, как что-либо следует делать. В то же время очевидно, что Пролог порывает с традициями языков типа "как", поскольку он определенным образом направляет программистское мышление, заставляя программиста давать определения ситуаций и формулировать задачи вместо того, чтобы во всех деталях описывать способ решения этих задач.

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

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

Пример программы родственные отношения
Дерево родственных отношений
Отношение родитель родителя
Упражнения
Расширение программы примера с помощью правил
Графы отношений родитель родителя
Определение отношения сестра
Рекурсивное определение правил
Пример отношения предок X ближайший предок Z
Пары предок потомок разделенных разным числом

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

Обьекты данных Пролога
Атомы и числа
Переменные
Имеетребенка( X) родитель( X _ )
Некто_имеет_ребенка родитель( _ _ )
Некто_имеет_ребенка родитель( X Y)
? Родитель( X _ )
Структуры
Дата пример структурного
Простые геометрические объекты

Списки. Операторы. Арифметика
Список - это простая структура данных, широко используемая в нечисловом программировании. Список - это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так: [ энн, теннис, том, лыжи ] Однако таково лишь внешнее представление списков. Как мы уже видели в гл. 2, все структурные объекты Пролога - это деревья. Списки не являются исключением из этого правила.

Некоторые операции над списками
Принадлежность к списку
Сцепление ( конкатенация)
Конкатенация списков
Процедура принадлежит
Упражнения
Добавление элемента
Удаление элемента
Подсписок
Отношения принадлежит и подсписок

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

Описания объектов
Упражнения
Абстракция данных
Упражнение
Моделирование недетерминированного автомата
Пример недетерминированного конечного автомата
Допущение цепочки
Упражнения
Планирование поездки
Планировщик воздушных маршрутов

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

Ограничение перебора
Двухступенчатая функция
В точке помеченной
Примеры использующие отсечение
Вычисление максимума
Процедура проверки принадлежности списку
Задача классификации объектов
Упражнения
Отрицание как неуспех
Упражнения

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

Обработка файлов термов
Reаd и write
Вывод списков
Формирование термов
Улучшенный формат вывода термов семьи
Вывод в формате представленном на 6 2
Обработка произвольного файла термов
Обработка символов
Упражнение
Создание и декомпозиция атомов

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

Проверка типов термов
Предикаты var nоnvar atom integer atomic
Решение числового ребуса с использованием nonvar
Поразрядное сложение
Упражнения
Создание и декомпозиция термов = functor arg name
Процедура подстановки в терм другого подтерма
Упражнения
Различные виды равенства
Работа с базой данных

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

Использование рекурсии
Обобщение
Использование рисунков
Стиль программирования
Некоторые правила хорошего стиля
Табличная организация длинных процедур
Отладка
Эффективность
Решение задачи о восьми ферзях
Повышение эффективности программы раскраски

Операции над структурами данных
Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка больше( X, Y) означающее, что Х больше, чем Y, независимо от того, что мы в действительности понимаем под "больше, чем". Если элементами списка являются числа, то отношение больше будет, вероятно, определено как больше( X, Y) := Х Y.

Сортировка списков
Сортировка списка процедурой быстрсорт
Более эффективная
Упражнения
Представление множеств двоичными деревьями
Двоичное дерево
Представление двоичных деревьев
Поиск элемента Х в двоичном справочнике
Дерево Д
Упражнения

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

Двоично троичные справочники
Полностью разбалансированный
Процесс поиска элемента
Иллюстрирует описанный принцип
Вставление нового
Объекты показанные на рисунке
Некоторые из случаев
Упражнения
Программа
AVL дерево приближенно сбалансированное

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

Задача перестановки кубиков
"Игра в восемь" и ее представление в форме графа
Стратегия поиска в глубину
Пример простого пространства
Бесконечный цикл между d и h a b d h d h d
Отношение в глубину( Путь В Решение)
Программа поиска в глубину без зацикливания
Программа поиска в глубину с ограничением
Упражнения
Поиск в ширину

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

Поиск кратчайшего
Программа поиска с предпочтением
Отношение расширить
Связь между gоценкой
Упражнение
Поиск к головоломке "игра в восемь"
Процедуры для головоломки
Три стартовых позиции
Упражнение
Применение поиска с предпочтением

Сведение задач к подзадачам. И/ИЛИ-графы
В главах 11 и 12, говоря о решении задач, мы сконцентрировали свое внимание на пространстве состояний как средстве представления этих задач. В соответствии с таким подходом решение задач сводилось к поиску пути в графе пространства состояний. Однако для некоторых категорий задач представление в форме И / ИЛИ-графа является более естественным. Такое представление основано на разбиении задач на подзадачи. Разбиение на подзадачи дает преимущества в том случае, когда подзадачи взаимно независимы, а, следовательно, и решать их можно независимо друг от друга.

Поиск маршрута из
И / ИЛИ представление
Решить Р это
Пример И / ИЛИ графа
Примеры И/ИЛИ представления задач
И / ИЛИ представление задачи поиска маршрута
Решающее дерево минимальной
Задача о ханойской башне
Задача о ханойской башне
Формулировка задач в терминах И / ИЛИ графов

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

Грубая структура экспертной системы
Правила типа "еслито" для представления знаний
"Еслито" правило
14 3 и 14 4 дают
Два правила из демонстрационной
Правило уточнения плана из системы AL3
Простая база знаний
Соединения между предохранителями и приборами
Разработка оболочки
Процесс рассуждений

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

Минимаксный принцип
Статические (нижний
Упрощенная реализация минимаксного принципа
Альфабета алгоритм эффективная реализация
Дерево 15
Реализация альфабета алгоритма
Проект
Минимаксные программы усовершенствования
Знания о типовых ситуациях и механизм "советов"
Цели и ограничения на ходы

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

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

Ответы
Глава 1
Глава 2
Глава 3
Глава 6
Глава 9
Глава 10


Частные деньги - перейти
Международные деньги и расчеты - перейти
Ведения международного бизнеса - перейти
Международная валютно-финансовая система - перейти
Международные экономические отношения - перейти
Экономические концепции - перейти
После капитализма - перейти
Демократия и экономика - мировой опыт - перейти
Агамамедова Гюлюш - Акимов Андрей - перейти
Акимов В М - Алексеев Александр - перейти
Алексеев В & Кузнецова А & Ашкинази Л - Аллилуева Светлана - перейти
Андреев Леонид - Антоновская Анна Арнольдовна - перейти
Артамонов Михаил - Афанасьева Елена - перейти
Афонькин С Ю - Бажина Елена - перейти
Бажов Павел - Барановский Вадим - перейти