- •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.18.6 Поиск в ширину
Здесь будем представлять множества списком путей кандидатов, а каждый путь - списком вершин в обратном порядке, т.е. головой списка будет самая последняя вершина, а последним элементом списка - стартовая вершина.
a
b c d e
Особенность :
В списке ОТК будем хранить не имена пройденных нами вершин, а пути-кандидаты.
1. [ [a] ] Дерево
2. [ [b,a], [c,a] ] a
3. [ [c,a], [d,b,a], [c,b,a] ] / \
4. [ [d,b,a], [c,b,a], [f,c,a], [g,c,a] ] b c
5. [ [f,c,a], [g,c,a] ] /\ /\
d e f g
целевая
Алгоритм поиска в ширину состоит из следующих пунктов:
1. Поместить в список путей-кандидатов исходную вершину.
2. Является ли 1-ая вершина 1-го пути-кандидата целевой?
Если "да", то - выдать путь-кандидат.
3. Иначе - удалить 1-ый путь-кандидат из последователь-
ности путей-кандидатов, найти его продолжения и доба-
вить их в конец последовательности путей-кандидатов.
4. Go to 2.
Существует такой предикат : bagof(X,P,L) - собирает все объекты X, удовлетворяющие условию P, в список L.
Этим предикатом мы будем пользоваться для того, чтобы получить список продолжений некоторого пути-кандидата.
solve(Start,R) :- width_sch( [[Start]], R).
width_sch( [[B|W]|_], [B,W] ):- goal(B).
width_sch( [[B|W]|Ways],R ):-
_bagof( . [B1,[B|W]],
( after(B,B1),not element(B1,[B|W]) ),
New_W _) .,
%
% После выполнения bagof() получим: [ [b,a], [c,a] ]
%
concat(Ways, New_W, Ways_1),
width_sch(Ways_1, R),
width_sch(Ways, R).
%
% Этот (последний) вызов предиката width_sch() связан с
% отбрасыванием тупиковых ветвей, когда after(B,B1)=false
%
findall и setof - выполняют работу, подобную bagof().
Поиск с использованием алгоритма равных цен м.б. реализован на базе программы.
Только сейчас: Все новые пути-кандидаты - помещаются в
конец списка.
надо : После получения списка Ways_1 отсортировать
его.
Рассмотренный алгоритм поиска в ширину связан со списко-
вым представлением дерева поиска, что не эффективно поскольку
начальные участки путей могут многократно повторяться. Поэтому
рассмотрим древовидное представление данных, что улучшит рабо-
ту программы поиска в ширину.
Здесь речь не пойдет о бинарном дереве : a
/ \
1 2 , нет,
под деревом будем понимать запись, вида:
T(B,SubT) <==> Д(Верш,Пд) - где
В - вершина,
SubT - список поддеревьев
SubT ::= { Пд1, Пд2, ... ,ПдN }
Кроме того - если имеется вершина В и она является узлом, то дерево с такой вершиной будем называть "листом" и обозначать L(B).
Например a описывается с учетом введенных обозначе-
/ \ ний следующим образом :
b c
/ \ / \ T( a,[ T( b,[ L(d), L(e)] ),
d e f d T( c,[ L(f), L(d)] ), ] )
такая структура дерева более эконо-
мит память.
Введем предикат:
let_width(W, T, T1, ExS, S). или
расширить(П, Д, Д1, СщР, Р) - где ( см. рис.* )
П (путь)/W (way) - путь, ведущий из старто-
вой вершины в корень де-
рева Д/T ,
Д (дерево)/T (tree) - путь до промежуточной
вершины ,
Д1(дерево1)/T1(tree1) - расширение дерева Д/Т
на один уровень ,
Р (решение)/S (solving) - путь, продолженный
до целевой вершины.
СщР (существует решение)/ExS (exist solving)
W
T
T1
Рис. *.
В этом предикате переменные W и T должны быть всегда определены (конкретизированы).
Идея алгоритма состоит в следующем:
Нужно расширять дерево T до тех пор, пока в ходе расширения не встретится целевая вершина.
Предикат let_width(W, T, T1, ExS, S) будет порождать 2 вида решений, зависящих от значения переменной ExS :
1. ExS = "да" ==> S - конкретизировано
Т1 - не конкретизировано
2. ExS = "нет" ==> S - не конкретизировано
Т1 - конкретизировано
Определим предикат solve()
с использованием предиката let_width()
Идея алгоритма - в каждый текущий момент расширяется дерево. Если в процессе расширения встретится целевая вершина, то необходимо выдать решающий путь, являющийся продолжением пути W от текущей корневой вершины до целевой вершины G.
solve( Start, Solving ):- width_sch( L(Start), Solving).
width_sch( T, S):-
let_width([], T, T1, ExS, S),
( ExS = да;
ExS = нет, !, width_sch(T1,S) ).
let_width( W, L(B), _, да, [B|W] ) :- goal(B).
let_width( W, L(B), T(B,SubT), нет, _) :-
bagof( L(B),
( after(B,B1), not element(B1,W) ),
SubT ).
let_width( W, T(B,SubT), T(B,SubT1), ExS, S) :-
let_width_all([B|W], SubT, SubT1, ExS, S).
% -------------------------------------------------------
% Предикат _let_width_all() . (расширить_все) расширяет все
% деревья из списка под-деревьев (Пд), выбрасывает все
% тупиковые ветки и собирает все полученные расширения в
% список Пд1.
% Определим его:
% Список Пд представляется в виде головы и хвоста, затем
% с помощью let_width() расширяется голова списка Пд,
% проверяется значение переменной ExS - существует ли ре-
% шение в ходе расширения. Если решение существует, то
% ExS=да, иначе ExS=нет. Если ExS=нет, то расширяется
% хвост списка Пд с помощью let_width_all()
% -------------------------------------------------------
%
let_width_all(W, [T|TT], [TT1], ExS, S):-
let_width(W, T, T1, ExS1, S),
( ExS1 = да, ExS = да;
ExS1 = нет, !,
let_width_all(W, TT, [T1|TT1], ExS, S) ).