Лекции в ворде (1156536), страница 17
Текст из файла (страница 17)
XY, write(Y),
write ('меньше, 4CM'),write(X).
Целевое утверждение
?- меньше (5, 2).
сопоставляется с головой первого утверждения при Х=5 и У=2. Однако не удается согласовать первый член конъюнкции в теле утверждения X<Y. Значит, Пролог нс может использовать первое утверждение для согласования целевого утверждения меньше(5, 2). Тогда Пролог переходит к следующему утверждению, голова которого сопоставима с целевым утверждением. В нашем случае это второе утверждение. При значениях переменных Х=5 и Y=2 тело утверждения согласуется. Целевое утверждение меньше(5,2) доказано, и Пролог выдает сообщение «2 меньше, чем 5». Запрос
?-меньше (2, 2).
сопоставляется с головой первого утверждения, но тело утверждения согласовать не удается. Затем происходит сопоставление с головой второго утверждения, но согласовать тело опять-таки оказывается невозможно. Поэтому попытка доказательства целевого утверждения меньше(2, 2) заканчивается неудачей.
Такой процесс согласования целевого утверждения путем прямого продвижения по программе мы называем прямой трассировкой (forward tracking). Даже если целевое утверждение согласовано, с помощью прямой трассировки мы можем попытаться получить другие варианты его доказательства, т.е. вновь согласовать целевое утверждение.
Пролог производит доказательство конъюнкции целевых утверждений слева направо. При этом может встретиться целевое утверждение, согласовать которое не удается. Если такое случается, то происходит смещение влево до тех пор, пока не будет найдено целевое утверждение, которое может быть вновь согласовано, или не будут ис черпаны все предшествующие целевые утверждения. Если слева нет целевых утверждений, то конъюнкцию целевых утверждений согласовать нельзя. Однако, если предшествующее целевое утверждениг может быть согласовано вновь, Пролог возобновляет процесс доказательства целевых утверждений слева направо, начиная со следующего справа целевого утверждения. Описанный процесс смещения влево для повторного согласования целевого утверждения и возвращения вправо носит название механизма возврата.
Пример: задача поиска пути в лабиринте
В качестве примера использования механизма возврата напишем процедуру для поиска пути в лабиринте. Лабиринт представлен фактами вида:
стена(I, J) для позиции в I-м ряду и J-й колонке, где есть стена
отсутств_стена(I, J) для позиции в I-м ряду и J-й колонке, где нет стены
выход (I, J) для позиции в 1-м ряду и J-й колонке, являющейся выходом
Рассмотрим небольшой лабиринт:
| Выход | ||||
Последний ряд лабиринта описывается фактами:
стена(4,1).
стена(4,3).
стена(4,4).
отсутств_стена(4,2).
Если задана исходная позиция, путь к выходу можно найти следующим образом.
Граничное условие:
Если исходная позиция является выходом, то путь найден.
Рекурсивные условия:
Ищем путь из исходной позиции в северном направлении. Если пути нет, идем на юг. Если пути нет, идем на запад. Если нельзя, идем на восток. Если соседняя позиция на севере (юге, западе, востоке) является стеной, то нет смысла искать путь из начальной позиции к выходу. Чтобы не ходить кругами, будем вести список позиций, в которых мы побывали.
Изложенному способу решения задачи соответствует процедура путь: она ищет путь (второй аргумент) к выходу из некоторой позиции (первый аргумент). Третьим аргументом является список позиций, где мы побывали.
/* Терм a(I, J) представляет позицию в
/* I-м ряду и J-й колонке.
/* Нашли путь ?
путь(а(I, J),[а(I, J)], Были) :- выход(I, J).
/* Пытаемся идти на север
путь(а(I, J),[а(I, J) | Р], Были) :-
К is I-1,
можем_идти(a (K, J), Были),
путь(а(I, J) ,Р, [a(K, J) | Были]).
/* Пытаемся идти на юг
путь(а(I, J),[а(I, J) | Р], Были) :-
К is I+1,
можем_идти(a (K, J), Были),
путь(а(I, J) ,Р, [a(K, J) | Были]).
/* Пытаемся идти на запад
путь(а (I, J), [a (I, J) | P], Были) :-
L is J-1,
можем_идти(а(I, L), Были),
путь(а(I, L), Р, [а(I, L)| Были]).
/* Пытаемся идти на восток
путь(а (I, J), [a (I, J) | P], Были) :-
L is J+1,
можем_идти(а(I, L), Были),
путь(а(I, L), Р, [а(I, L)| Были]).
/* в позицию a(I, J) можно попасть при
/* условии, что там нет стены и мы
/* не побывали в ней прежде
можем_идти(а(I, J)), Были) :-
отсутств_стена(I, J),
not (принадлежит (a (I, J), Были)).
Для того чтобы понять, каким образом процедура ищет путь к выходу, рассмотрим процесс согласования запроса с описанием лабиринта, описанного выше:
?-путь(а(4,2), Р, [а(4.2)]).
Выходом из лабиринта является позиция выход (3,1).
Выбор первого утверждения не приводит к согласованию целевого утверждения, поскольку а (4,2) - не выход. Во втором утверждении делается попытка найти путь в северном направлении, т.е. согласовать целевое утверждение
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).
Целевое утверждение не удается согласовать с первым утверждением
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)])
так как а (3,2) не является выходом. Во втором утверждении предпринимается попытка найти путь, двигаясь на север, т.е. согласовать целевое утверждение
путь(а(2,2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).
Ни одно из утверждений не может согласовать
путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).
Первое утверждение - потому, что а (2, 2) не является выходом, второе - потому, что северная позиция является стеной, третье утверждение - потому, что в южной позиции мы уже побывали, а четвертое и пятое утверждения - потому, что западная и восточная границы - это стены.
Неудача в согласовании
путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)])
заставляет Пролог-систему вернуться в ту точку, где было выбрано второе утверждение при попытке согласовать
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).
Решение пересматривается и выбирается третье утверждение.
В третьем утверждении осуществляется попытка найти путь, двигаясь на юг, но она оказывается неудачной, поскольку мы уже побывали в позиции а (4, 2). Тогда, чтобы согласовать
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]),
выбирается четвертое утверждение. Мы успешно находим путь, двигаясь в западном направлении к позиции а(3,1), которая и является выходом. Рекурсия сворачивается, и в результате получается путь
Р=[а(4, 2),а(3, 2), а(3,1)]
другие решения(да/нет)? да
Других решений нет
Альтернативный путь
[a(4,2), a(3,2), a(2,2), a(3,2), a(3,1)]
мы получить не можем, потому что не разрешается дважды бывать в одной и той же позиции.
Описанная процедура не обязательно находит кратчайший путь к выходу. Кратчайший путь можно найти, генерируя альтернативные пути с помощью вызова состояния неудачи и запоминая кратчайший из них.
Элементы нечеткой логики
Как известно, классическая логика оперирует только с двумя значениями: истина и ложь. Однако этими двумя значениями довольно сложно представить (можно, но громоздко) большое количество реальных задач. Поэтому для их решения был разработан специальный математический аппарат, называемый нечеткой логикой. Основным отличием нечеткой логики от классической, как явствует из названия, является наличие не только двух классических состояний (значений), но и промежуточных:
F{0…1}
Соответственно, вводятся расширения базовых операций логического умножения, сложения и отрицания (сравните с соответствующими операциями теории вероятностей):
Как можно легко заметить, при использовании только классических состояний (ложь-0, истина-1) мы приходим с классическим законам логики.
Нечеткое логическое управление может использоваться, чтобы осуществлять разнообразные интеллектуальные функции, в самых разнообразных электронных товарах и домашних приборах, к авто электронике, управлению производственными процессами и автоматизации.
Указатели
I
intelligence 1
artificial 1
И
интеллект 1
искусственный 1
интеллектуальная задача 1
Содержание
Лекция 1-2: Базовые понятия ИИ 1
Цель преподавания дисциплины 1
Терминология 1
Философские аспекты проблемы систем ИИ (возможность существования, безопасность, полезность). 3
История развития систем ИИ. 5
Лекция 3: Архитектура и основные составные части систем ИИ 9
Различные подходы к построению систем ИИ 9
Вспомогательные системы нижнего уровня (распознавание образов зрительных и звуковых, идентификация, моделирование, жесткое программирование) и их место в системах ИИ 11
Лекции 4-7: Системы распознавания образов (идентификации) 14
Понятие образа 14
Проблема обучения распознаванию образов (ОРО) 14
Геометрический и структурный подходы. 17
Гипотеза компактности 19
Обучение и самообучение. Адаптация и обучение 19
Перцептроны 20
Нейронные сети 22
История исследований в области нейронных сетей 22
Модель нейронной сети с обратным распространением ошибки (back propagation) 23
Нейронные сети: обучение без учителя 26
Нейронные сети Хопфилда и Хэмминга 29
Метод потенциальных функций 32
Метод группового учета аргументов МГУА 33
Метод наименьших квадратов 33
Общая схема построения алгоритмов метода группового учета аргументов (МГУА). 35
Алгоритм с ковариациями и с квадратичными описаниями. 36
Метод предельных упрощений (МПУ) 37
Коллективы решающих правил 38
Методы и алгоритмы анализа структуры многомерных данных 39
Кластерный анализ 39
Иерархическое группирование 41
Лекции 8-11. Логический подход к построению систем ИИ 43
Неформальные процедуры 43
Алгоритмические модели 43
Продукционные модели 44
Режим возвратов 45
Логический вывод 45
Зависимость продукций 46
Продукционные системы с исключениями 46
Язык Рефал 47
Пролог 49
Синтаксис 49
ТЕРМЫ 49
КОНСТАНТЫ 50
ATOM 50
ЧИСЛА 50
ПЕРЕМЕННЫЕ 50
ОБЛАСТЬ ДЕЙСТВИЯ ПЕРЕМЕННЫХ 50
СЛОЖНЫЕ ТЕРМЫ, ИЛИ СТРУКТУРЫ 51
СИНТАКСИС ОПЕРАТОРОВ 51
СИНТАКСИС СПИСКОВ 51
СИНТАКСИС СТРОК 51
УТВЕРЖДЕНИЯ 51
ЗАПРОСЫ 52
ВВОД программ 52
Унификация 53
Арифметические выражения 54
Введение 54
Арифметические выражения 55
Арифметические операторы 55
Вычисление арифметических выражений 55
Сравнение результатов арифметических выражений 56
Структуры данных 56
Списки 56
Бинарные деревья 61
ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ 61
ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ 61
Механизм возврата и процедурная семантика 63
Механизм возврата 63
Пример: задача поиска пути в лабиринте 64
Элементы нечеткой логики 66
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
