- •Содержание
- •Введение
- •Глава 1. Основные понятия
- •1.1. Понятие об искусственном интеллекте
- •1.1.1. Точка зрения Петрунина.
- •1.1.2. Интеллектуальные алгоритмы.
- •1.2. Основные направления исследования в области ии
- •1.3. Данные и знания. Основные модели представления знаний
- •Глава 2. Логические модели представления знаний
- •2.1. Логика высказываний
- •2.1.1. Булева алгебра.
- •2.1.2. Понятие о логическом следствии.
- •2.1.3. Метод резолюции в лв.
- •Имеет место теорема о полноте резолютивного вывода. Множество клозов противоречиво тогда и только тогда, когда из него методом резолюции можно вывести пустой клоз.
- •2.2. Логика предикатов первого порядка
- •2.2.1. Основные определения.
- •2.2.2. Метод резолюции в лппп.
- •2.2.3. Стратегии проведения резолюции.
- •2.2.4. Упорядоченный линейный вывод в лппп.
- •2.2.5.Применение поиска в пространстве состояний при реализации автоматизированного логического вывода.
- •2.2.6. Логический вывод на хорновских дизъюнктах.
- •Понятие экспертной системы и применение логического вывода при построении экспертных систем.
- •2.2.9. Запросы класса b.
- •2.2.10. Запросы класса c.
- •2.3. Понятие о нечетком выводе
- •2.4. Неклассические логики
- •2.4.1. Логики высших порядков.
- •2.4.2. Модальные логики.
- •2.4.3. Многозначные логики.
- •Глава 3. Продукционные модели представления знаний
- •3.1. Основные понятия
- •3.2. Стратегии управления
- •3.2.1. Поиск с возвратом.
- •3.2.2. Поиск в пространстве состояний.
- •3.3. Понятие о коммутативных системах продукций
- •3.4. Понятие о нечетком выводе на продукциях
- •3.5. Сравнение продукционных и логических моделей
- •Глава 4. Реляционные языки представления знаний
- •4.1. Основные элементы естественных языков
- •4.2. Дескрипторные модели
- •4.2.1. Понятие об ипс.
- •4.2.2. Линейная модель работы ипс.
- •4.2.3. Понятие о многоуровневом поиске.
- •4.2.4. Основные характеристики ипс.
- •4.4. Синтагматические цепи
- •4.4.1. Понятие синтагматических цепей.
- •4.4.2. Фреймы.
- •4.5. Сетевые модели представления знаний
- •4.5.1. Понятие семантической сети.
- •4.5.2. Структура интеллектуальной системы доступа к данным на основе семантической сети.
- •4.5.3. Задача поиска кратчайшего обхода образца в семантической сети.
- •4.5.4. Понятие о логическом выводе на семантических сетях.
- •Глава 5. Нейронные сети
- •5.1. Параллели из биологии
- •5.2. Базовая искусственная модель
- •5.3. Применение нейронных сетей
- •5.4. Обучение сети
- •Глава 6. Организация диалога с эвм на естественном языке
- •6.1. Элементы теории формальных языков
- •6.2. Обратная польская запись
- •6.3. Недостатки применения аппарата формальных грамматик
- •6.4. Элементы семиотики
- •6.5. Модель непосредственных составляющих
- •6.6. Многозначность в естественных языках
- •6.7. Расширенные сети переходов
- •6.8. Глубинные (семантические) падежи
- •Глава 7. Логическое программирование на языке пролог
- •7.1. Основные понятия в языке Пролог
- •7.2. Пакет Turbo Prolog
- •7.3. Структура программы
- •7.4. Поиск решений
- •7.5. Механизм отката
- •7.6. Операторы. Декларативный и процедурный смысл программы
- •7.7. Повторение и рекурсия
- •7.8. Повторение и откат
- •7.8.1. Метод отката после неудачи (опн).
- •7.8.2. Метод отсечения и отката (оо).
- •7.8.3. Метод повтора, определенный пользователем.
- •7.9. Методы организации рекурсии
- •7.10. Отладка программы и обнаружение ошибок
- •7.11. Графика в Turbo Prolog’е
- •7.11.1 Создание меню.
- •7.11.2. Создание графического режима.
- •7.11.3. Черепашья графика
- •7.12. Списки и их использование
- •7.12.1. Использование списка.
- •7.12.2. Поиск элементов в списке.
- •7.12.3. Создание нового списка путем слияния двух списков
- •7.12.3. Разделение на два списка.
- •7.13. Сортировки
- •7.13.1. Наивная сортировка.
- •7.13.2. Сортировка включением.
- •7.13.3. Метод «пузырька».
- •7.13.4. Быстрая сортировка.
- •7.14. Компоновка данных из базы в список
- •7.15. Работа с символами и строками
- •7.16. Специальные строки
- •7.17. Работа с файлами
- •7.18. Создание динамических баз данных
- •7.19. Библиотеки Turbo Prolog’а
- •7.19. Модульное программирование
- •7.20. Решение задачи о волке, козе и капусте
- •Глава 8. Введение в язык лисп
- •8.1. Основные особенности языка Лисп
- •8.2. Понятия языка Лисп
- •8.2.1 Атомы и списки.
- •8.2.2 . Внутреннее представление списка.
- •8.2.3 .Написание программы на Лиспе.
- •8.2.4. Определение функций.
- •8.2.5. Рекурсия и итерация.
- •В) maplist. Эта функция действует подобно mapcar, но действия осуществляет не над элементами списка, а над последовательными cdr этого списка.
- •8.2.6 . Функции интерпретации выражения.
- •8.2.7. Макросредства.
- •8.2.8. Функции ввода-вывода.
- •Список используемых источников
- •Перечень используемых сокращений
2.2.5.Применение поиска в пространстве состояний при реализации автоматизированного логического вывода.
Пусть дан простой ориентированный граф G=(V,E), и пусть существует некоторая вершина S, не имеющая предков (в эту вершину не входит ни одна дуга). Эта вершина называется начальным состоянием. Все остальные вершины имеют хотя бы одного предка. Также существует Term – подмножество терминальных вершин (состояний). Такой граф называется или пространством состояний или пространством решений, его вершины называются состояниями, а его дуги – правилами.
Пространство состояний используется при решении многих прикладных задач, и в частности, при автоматизированном OL – опровержении множества клозов. В этом случае вершинам будут соответствовать пары клозов (Ci,Bj), где Cj - центральные клозы, Bj – боковые клозы.
Раскрытием вершины или состояния называется определение исходящих из неё дуг.
В случае построения пространства состояний для задачи OL-опровержения вершины раскрываются следующим образом:
-
На (Ci,Bj) строится множество резольвент R.
-
Производится отождествление влево во всех клозах из R, где это возможно.
-
Заменяем все редуцируемые клозы в R на их редукции.
-
Определяем всевозможные боковые клозы для всех клозов из R.
Замечание: терминальными будут те пары, которые при резолюции дают пустой клоз.
Приведем для простоты пример из логики высказываний.
S={pq,pq, pq, pq}
(pq, - )
(pq, pq) (pq,pq)
(pqp=p,pq) (p, pq)
(pq, pq) ( pq, pq)
(pqp, pq ) (pqp, pq)
(pqpq=pqq, pq) (pqq, pq)
(pqqp=pq ) (pqqp=p qp = )
ПОВТОР
Алгоритм, обеспечивающий построение пространства состояний и определяющий фактически путь от начальной вершины до терминальной, называется алгоритмом поиска в пространстве состояний.
Примечание. Алгоритм поиска в пространстве состояний должен быть конструктивным, т.е. выдавать не только утвердительный или отрицательный ответ на поставленную задачу, но и дерево решений, содержащее последовательность применяемых правил.
Алгоритм поиска в пространстве состояний в формальном виде выглядит следующим образом:
G:={S}; T:={S}; // - вначале пространство решений G и дерево решений T состоит из одной начальной вершины S.
OPEN:={S}; // - список вершин, которые требуется раскрыть.
CLOSED:=; // - список уже раскрытых вершин.
while true do begin // - начинаем бесконечный цикл.
if Null (OPEN) then return (NO); // - если список OPEN пуст, то ответ отрицательный
n:=First (OPEN); // - берём за n первую вершину в списке OPEN.
OPEN:= Tail (OPEN); // - список OPEN без первой вершины.
ADD (n, CLOSED); // - добавляем вершину n в список CLOSED.
if Term (n) then return (YES, T); // - если вершина терминальная, то ответ утвердительный с деревом решений T. При этом в случае необходимости мы можем продолжить поиск.
M={Mi}:=раскрыть (n); // - получаем в M список вершин, получившихся при раскрытии вершины n.
for mM do begin
ADD (G, n, m); // - добавляем дуги (n, m) в пространстве решений.
if (not (mOPEN)) and (not (mCLOSED)) then begin
ADD (T, n, m); // - добавляем правило (n, m) к дереву решений.
end;
else begin
Rebuild (T); // - перестраиваем дерево решений.
end;
end;
OPEN:=Reorder (OPEN); // - переупорядочиваем список OPEN
end.
Примечание. 1: Процедура переупорядочивания, то есть Reorder иногда зависит от конкретной задачи. В этом случае, алгоритм называется информированным. Существует три класса информированных алгоритмов: A, A*, OA*. Неинформированные алгоритмы бывают двух классов: поиск в ширину, поиск в глубину. В случае поиска в ширину верхняя вершина в списке OPEN одна из самых ближних к начальной, а при поиске в глубину – одна из самых дальних от начальной. Тип поиска в пространстве состояний полностью соответствует соответствующему типу обхода графа (см. []).
2. Процедура Rebuild может отсутствовать. Она обязательна в случаях поиска оптимального решения.
Задача поиска в пространстве состояний может ставиться в четырех различных вариациях:
-
Определить существует ли решение вообще?
-
Найти любое решение задачи.
-
Найти всевоможные решения задачи.
-
Найти из множеств решений оптимальное в каком-либо смысле. В простейшем случае под оптимальным понимается решение, которому соответствует минимальное количество ребер от начальной до терминальной вершины. В случае OL-опровержения, таким образом, оптимальность означает минимизацию количества проведенных резолюций. В более сложных случаях могут вводиться весовые коэффициенты дуг.
Приведенный алгоритм с незначительными модификациями применим для решения любой из четырех задач.