- •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 Обратное усечение дерева.
3.6 Алгоритм поиска в глубину
Глубина вершины - номер ее уровня. При этом методе всегда раскрывается та вершина, которая имеет наибольшую глубину. Если таких вершин несколько, то должно существовать правило выбора (зависит от задачи). Глубину поиска обычно ограничивают некоторым уровнем. Этот уровень называется граничным. Т.е. раскрывается вершина с максимальной глубиной из вершин с глубиной, меньше граничного значения.
Алгоритм:
1.Поместить начальную вершину в список ОТК .
2.Если ОТК- пуст, то завершить решение задачи, сообщить о неудаче.
3.Перенести первую вершину ОТК в ЗКР. Проверить, является ли эта вершина целевой. Если вершина целевая, то возвратить пройденный путь на графе.
4.Раскрыть 1-ю вершину списка ЗКР и поместить все дочерние вершины, снабженные ссылками на родительскую вершину, которых нет в списке ЗКР в начало списка ОТК. Проверить критический уровень. Если мы его достигли, то не раскрывать вершину, а перейти к п.2.
5.Если критический уровень не достигнут, то перейти к п.3.
П ример:
ОТК ЗКР
1.Севастополь ---> Сев
2.Терновка-Сев ---> Терновка-Сев
Бахчисарай-Сев Сев
3.Куйбышево-Терн ---> Куйбышево-Терн
Ялта-Терн Терновка-Сев
Бахчисарай-Сев Сев
4.Ялта-Куйб ---> Ялта-Куйб
Ялта-Терн Куйбышево-Терн
Бахчисарай-Сев Терновка-Сев
Сев
5.Симф.-Ялта ---> Симф.-Ялта
Симф.-Бахчисарай Ялта-Куйб
Ялта-Терн Куйбышево-Терн
Бахчисарай-Сев Терновка-Сев
Сев
Обычно, критический уровень вводят тогда, когда граф представлен в виде дерева. В рассмотренном примере не имеет смысла вводить критический уровень.
Метод поиска в глубину не дает ни оптимального, ни минимального пути. Он легко программируется с помощью алгоритмических языков.
Методы слепого перебора дают решение всегда, но они являются затратными.
3.7Алгоритм равных цен
Каждой вершине присваивается стоимость раскрытия вершин. Стоимость раскрытия некоторой вершины определяется: g(Vi+1)=g(Vi)+g(Vi,Vi+1), где Vi- родительская вершина.
Vi Vi+1
g(Vi,Vi+1)- стоимость пути.
Стоимость раскрытия начальной вершины g(V0)=0.
Алгоритм:
1.Поместить начальную вершину V0 в список ОТК и положить стоимость раскрытия g(V0)=0.
2.Если ОТК- пустой, то завершить решение задачи, сообщить о неудаче.
3.Взять из ОТК ту вершину, которая имеет минимальную стоимость раскрытия и поместить ее в ЗКР на первое место. Присвоить этой вершине идентификатор V. Если вершин с равной минимальной стоимостью несколько, то берем любую из них.
4.Если V- целевая вершина, то выдать обратный путь.
5.Раскрыть вершину V и для каждой дочерней вершины определить стоимость раскрытия. Поместить эти вершины вместе с соответствующими стоимостями и указателями на родителtq в список ОТК. Если V не имеет дочерних вершин, то п.2. Если дочерние вершины есть, то раскрыть их и п.2.
Пример:
Севастополь
20 50
Терновка Бахчисарай
50 Куйбошево 25
50 30
50
Ялта 70 Симферополь
ОТК ЗКР
1.Севастополь,0 ---> Сев,0
2.Терновка-Сев,20 ---> Терновка-Сев,20
Бахчисарай-Сев,50 Сев,0
3.Бахчисарай-Сев,50 ---> Бахчисарай-Сев,50
Куйбош.-Терн,50 Терновка-Сев,20
Ялта-Терн,70 Сев,0
4.Симферополь-Бахч,80 ---> Куйбош.-Терн,50
Куйбош.-Терн,50 Бахчисарай-Сев,50
Ялта-Терн,70 Терновка-Сев,30
Куйбош.-Бахчисарай,75 Сев,0
5.Ялта - Куйбош.,100 ---> Ялта-Терн,70
Симферополь-Бахч,80 Куйбош.-Терн,50
Ялта-Терн,70 Бахчисарай-Сев,50
Куйбош.-Бахчисарай,75 Терновка-Сев,20
Сев,0
6.Ялта - Куйбош.,100 ---> Куйбош.-Бахчисарай,75
Симферополь-Бахч,80 Ялта-Терн,70
Куйбош.-Бахчисарай,75 Куйбош.-Терн,50
Ялта – Симферополь,140 Бахчисарай-Сев,50
Терновка-Сев,20
Сев,0
7.Ялта - Куйбош.,100 ---> Симферополь-Бахч,80
Ялта – Симферополь,140 Бахчисарай-Сев,50
Сев,0
Помещать вершины в список можно любым образом. Его требуется упорядочить по стоимости и выбрать минимальную вершину. Алгоритм всегда выдает путь минимальной стоимости и эквивалентен поиску в ширину, если положить все стоимости равными 1.
Метод применяется, когда пространство поиска мало