- •1 Общая характеристика дисциплины
- •1.1 Значение дисциплины ии
- •1.2 Понятие "искусственный интеллект"
- •1.3 Краткая история развития ии
- •1.4 Классификация систем ии
- •Представления знаний - центральная проблема ии.
- •Компьютерной лингвистики, решение которой обеспечивает процесс естественно- языкового общения с эвм и процесс автомтического перевода с иностранных языков.
- •Компьютерной логики, имеющей особо важное значение для развития экспертных систем, поскольку ее цель – моделирование человеческих рассуждений.
- •1.5 Основные направления развития ии
- •2Языки систем искусственного интеллекта
- •2.1 Общие сведения о языках сии
- •2.2 Язык лисп
- •2.2.1 Алфавит
- •2.2.2 Атомы и точечные пары
- •2.2.3 Списки
- •2.2.4 Арифметические функции языка лисп
- •2.2.5 Функции setq и quote
- •2.2.6 Функции car и cdr
- •2.2.7 Композиция функций саr и cdr.
- •2.2.8 Пустой список
- •2.2.9 Функция cons
- •2.2.10 Логические значения и предикаты
- •2.2.11 Предикаты атом и eq
- •2.2.12 Предикат null
- •2.2.13 Предикаты, классифицирующие атомы
- •2.2.14 Арифметические предикаты сравнения
- •2.2.15 Операции над строками битов
- •2.2.16 Функция cond
- •2.2.17 Определяющее выражение функции
- •2.2.18 Определяемые функции
- •2.2.19 Рекурсивные функции
- •2.2.20 Prog- механизм.
- •2.3 Обращение (инверсия) списков
- •2.4 Вычисление факториала числа
- •2.5 Вычисление длины списка
- •2.6 Вычисление длины списка и его подсписков
- •2.7 Соединение списков
- •2.8 Удаление элемента из списка
- •2.9 Функция, вычисляющая список общих элементов двух списков
- •2.10 Функция, объединяющая два списка и не включающая повторяющиеся элементы
- •2.11 Ассоциативные списки
- •2.12 Функции, изменяющие значения указателей
- •2.13 Функции read и print
- •2.14 Функция eval
- •3 Представление задач и поиск решений
- •3.1 Представление задач в пространстве состояний
- •3.2 Сведение задачи к подзадачам
- •3.3Представление задач в виде доказательства теорем
- •3.4 Поиск решения в пространстве состояний
- •3.5 Алгоритм поиска в ширину
- •3.6 Алгоритм поиска в глубину
- •3.7Алгоритм равных цен
- •3.8 Алгоритмы эвристического (упорядочного) поиска
- •3.9 Поиск решения задачи, при сведении задачи к подзадачам
- •3.10 Представление знаний
- •3.10.1 Продукционные системы
- •3.10.2Семантические сети
- •3.10.3 Представление знаний фреймами
- •3.11 Сопоставление с образцом
- •3.11.1 Функции Mapcad, Apply и Funcall
- •3.11.2 Свойства Атомов
- •3.11.3 Функция сопоставления с образцом
- •3.11.4 Присваивание значений при сопоставлении с образцом
- •3.11.5 Функции Explope, Compress, AtomCar, AtomCdr
- •3.11.6 Задание ограничений при сопоставлении с образцом
- •3.12 Программная реализация лисп - машин
- •3.12.1 Структура памяти лисп - машины
- •3.12.2 Диалекты языка лисп
- •3.12.3 Аппаратная реализация языка лисп
- •4 Математические основы логического вывода
- •4.1 Решение задач с помощью доказательства теорем
- •4.2 Тождественные преобразования при доказательстве теорем
- •4.3 Принцип резолюции
- •4.4Примеры применения принципа резолюции
- •4.5 Система управления роботом strips.
- •5Решение задач искусственного интеллекта на языке пролог
- •5.1 Применение метода доказательства теорем в системе пролог
- •5.2 Особенности программирования на пролоГе
- •5.4 Арифметические предикаты
- •5.5 Предикаты управления возвратом
- •5.6 Программа вычисления квадратного корня
- •5.7 Вычисление n!
- •5.8 Область действия предиката отсечения
- •5.9 Отрицание на пролоГе
- •5.10 Определение структур управления
- •5.11 Организация циклов в языке пролог
- •5.11.1 Цикл repeat-fail
- •5.11.2 Сопоставление цикла с возвратом и рекурсии
- •5.12 Операторная запись.
- •5.13 Ввод-вывод в системе пролог
- •5.13.1 Предикаты ввода-вывода символов
- •5.13.2 Предикаты ввода-вывода термов
- •5.13.3 Примеры применения предикатов ввода-вывода
- •5.14 Предикат name
- •5.15 Предикаты проверки типов термов
- •5.16 Создание и декомпозиция термов
- •5.17 Предикаты работы с базой данных .
- •5.18 Бинарные деревья
- •5.18.1 Построение бинарного дерева
- •5.18.2 Преобразование списка в упорядоченное дерево
- •5.18.3 Преобразование дерева в список
- •5.18.4 Удаление элемента из дерева
- •5.18.5 Поиск в глубину
- •5.18.6 Поиск в ширину
- •5.19 Поиск решений в игровых программах.
- •5.20 Обратное усечение дерева.
5Решение задач искусственного интеллекта на языке пролог
5.1 Применение метода доказательства теорем в системе пролог
В логическом программировании процесс доказательства теорем рассматривается как процесс вычисления и выполнения программы. Соответствие процесса доказательства и процесса выполнения программы было установлено Р.Ковальским. Существенный недостаток принципа резолюции заключается в формировании на каждом шаге вывода множества резольвент - новых дизъюнктов, большинство из которых являются лишними. В связи с этим, разработаны модификации принципа резолюции, использующие более эффективные стратегии поиска при различного рода ограничениях на вид исходных дизъюнктов. В этом смысле наиболее удачной и популярной считается система Пролог.
Пролог использует принцип резолюции для специальных предложений - дизъюнктов Хорна. По определению, дизъюнктами Хорна называются предложения, содержащие не более одного положительного литерала.
Различают дизъюнкты Хорна трех типов:
Дизньюнкт содержащий только один положительный литерал В(х). Такие дизъюнкты называются допущениями без условий или фактами.
Дизньюнкт содержащий 1 положительный и любое количество отрицательных литералов:
__ __ __
B(x) U L1 U L2 U L3 <==> B(x)<-- L1/\L2/\L3.
B(x) выполняется, если выполняется L1 и L2 и L3. Это - допщения с условиями или правила.
Дизньюнкт содержащий одни отрицательные литералы :
__ __ __ __________
L1 U L2 U L3 <==> L1/\L2/\L3.
Такие дизъюнкты в Прологе называют целевыми утверждениями.
В 60-х годах было показано, что если процедура доказательства теорем применяется для определения вычислимых функций, то вполне достаточно использовать для этого лишь дизъюнкты Хорна. В этом случае метод резолюций получается достаточно простым и может быть положен в основу практической системы программирования. Т.о., для поиска решения в Пролог-системе используется линейная резолюция.
Рассмотрим принцип линейной резолюции при использовании только хорновских дизъюнктов. Конкретная стратегия, используемая при этом, является разновидностью линейной входной резолюции. При использовании этой стратегии выбор дизъюнктов для резолюции на каждом шаге ограничен следующими условиями:
Процедура доказательства теорем начинается с применения правила резолюции к целевому дизъюнкту и одной из аксиом, что дает новый дизъюнкт.
Затем производится резолюция этого дизъюнкта и одной из гипотез и т.д.
На каждом этапе правило резолюций применяется к последнему из вновь полученных дизъюнктов и к одной из исходных аксиом.
Правило резолюций никогда не применяется, если оба дизъюнкта были выведены на предыдущих этапах или являются исходными гипотезами.
Пусть есть исходные предложения А1,А2,...Аn, где Аi-
дизньюнкт 1-ой или 2-ой разновидности .
Цель: ~G
Тогда линейная резолюция : _
A1 A2 . . . An G
D1 -новая подцель
D2
-В системе ПРОЛОГ
Dn не реализованно
Линейная резолюция выполняется по этапам:
Ищется следствие м/у отрицанием ЦУ ~G и одной из аксиом А1,...,Аn, которые представленны в виде дизньюнктов Хорна.
Полученное следствие соответствует новому ЦУ
Опять ищем следствие м/у новым ЦУ и 1-ой из аксиом.
Запрещено находить следствие м/у промежуточными ЦУ.
С точки зрения Пролога последний выведенный дизъюнкт рассматривается как конъюнкция целевых утверждений, которые надо еще доказать (согласовать с БД). В начальный момент это вопрос, а в конце процесса при благоприятных условиях это пустое утверждение. На каждом этапе ищется утверждение (положительный литерал), заголовок которого сопоставляется с одним из целевых литералов. Если необходимо, делаются требуемые подстановки, т.е. производится конкретизация переменных. Удаляется целевое утверждение, с которым произошло сопоставление, а затем к целевым утверждениям, которые необходимо согласовать, добавляется тело найденного утверждения.
Линейная резолюция в ПРОЛОГе соответствует поиску в глубину на графе.
ПРИМЕРЫ ПРИМЕНЕНИЯ МЕТОДА РЕЗОЛЮЦИИ В СИСТЕМЕ ПРОЛОГ
Определим ф-ю МEMBER(X Y) на ЛИСПе:
(DEFUN MEMBER(X Y)
(COND ((EQ Y NIL) NIL)
((EQ X (CAR Y)) T)
(T (MEMBER X (CDR Y)))
)
)
Т.о. проверяется, содержится ли Х в голове списка, если его там не было, то проверяется содержится ли он в хвосте, представляя хвост в виде другого списка.
В Прологе это необходимо сначала сфориулировать в виде гипотез, аксиом, а затем применить процесс доказательства теорем. Введем в рассмотрение предикат member(X,Y). Особенностью Пролога является то, что имена предикатов и констант записываются строчными буквами, имена переменных начинаются с символа подчеркивания или заглавной буквы. Списки в языке ПРОЛОГ записываются в виде: [a,b,c,...] или [ H|T ], если надо показать, что список состоит из головы (H) и хвоста (T).
Рассмотрим предикат с именем "member":
member(H,[H|T]).
если не поставить точку,
система б.ждать ввода.
Теперь запишем правило :
member(H,[Х|T]) :- member(H,T).
Знаком ":-" может читаться с.о:
Если верно, что member(H,T),то и member(H,[ H|T ])- верно.
Кроме того он эквивалентен знаку "<--":
member(H,[ H|T ]) :- member(H,T).
member(H,[ H|T ]) <--member(H,T).
Пусть запрос: ?- member(с,[a,b,c]).
_ _
Знаем, что A-->B <==> A U B ,тогда B<--A <==> B U A
ЦУ: G
member(H,[Х|T])Umember(H,T),
member(H,[H|T]) member(c,[a,b,c])
a X member(c,[b,c])
c H с H
[b,c] T b X - Не можем сопоставить!
[c] T
member(c,[c]) c H
[] T
NIL
Это называется "деревом утверждения"
Это дерево строится в ПРОЛОГе с.о: __
ПРОЛОГ-Система пытается сопоставить ЦУ с 1 из фактов
Если п.1 неудачен, то сопоставляется ~ЦУ с головой 1-го из правил. Если сопоставление удачно, то получается новая подцель.
Процесс повторяется до тех пор, пока не будет получен результат NIL, или пока все варианты не будут перепробованы.
Слияние 2-х списков
В действительности, используемая в Прологе стратегия является более огрниченной. Некоторую особенность имеет процесс построения резолюции, когда целевое утверждение содержит переменную. Например, нужно удовлетворить цель вида ЕхР(х). В этом случае, Пролог-система должна возвратить то значение х при котором цель является истинным утверждением. Рассмотрим программу, позволяющую получить третий аргумент путем присоединения списка, являющегося вторым аргументом, к списку, являющемуся первым аргументом.
append(X,Y,Z) -где X -1-ый список
Y -2-ой список
Z -результирующий список
Текст программы:
append([],L,L).
append([H|U],V,[H|W]) :-append(U,V,W).
?- append([a,b],[c],H).
ap([],L,L) ap([H|U],V,[H|W]) U ap(U,V,W) ap([a,b],[c],H)
H [ X|W ]=[a|W] a H
[b] U
[c] V
ap([b],[c],W)
b H
[] U W [H|W]=[b|W]
[c] V
ap([],[c],W)
[c] L W
[c] L
NIL
Найдем H:
1.H<--[a|W]
2.H<--[a|[b|W]]
3.H<--[a|[b|c]] ,т.е. [a,b,c]
Т.о., для нахождения Н нужно выполнить всю систему подстановок.
Мы рассмотрели простой пример, когда целевое утверждение содержало один литерал. В действительности, оно может содержать несколько литералов:
__ __ __
C1 \/ C2 \/...\/ Cn
В Прологе всегда сопоставляется первый литерал, а образовавшиеся новые литералы опять помещаются в начало целевого дизъюнкта. Если представить целевой дизъюнкт в виде списка целей (С1,С2,...,Сn), то на первом шаге Пролог пытается разрешить С1. Образовавшийся новый дизъюнкт занимает место С1. Т.о. Пролог завершит доказательство всех подцелей С1',C1", и т.д., прежде, чем перейдет к доказательству следующего целевого утверждения. Т.е. в Прлоге используется стратегия поиска в глубину, а не в ширину. каждый раз рассматривается одна альтернатива до тех пор, пока она не окажется безуспешной. Такая стратегия проще для реализации ее на ЭВМ.