- •Содержание
- •Введение
- •Глава 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. Функции ввода-вывода.
- •Список используемых источников
- •Перечень используемых сокращений
7.20. Решение задачи о волке, козе и капусте
В заключение приведем пример решения на Прологе известной задачи о волке, козе и капусте. Данная задача была подробно описана в главе 3, посвященной продукционным моделям. Для того чтобы решить задачу на Прологе, ее следует фактически представить на языке ЛППП. Тогда получим задачу на запрос класса C. При решении используется поиск в пространстве состояний, но преимущество Пролога в том, что поиск берет на себя Turbo Prolog, а нам остается только задать правила, факты и цель.
Состояние представляется тройкой wgc(B, L, R), где В – местонахождение лодки (левый или правый берег), L – список находящихся на левом берегу, R – список находящихся на правом берегу. Начальным и конечным состояниями являются:
w – волк, g – коза, c – капуста,
B – местонахождение лодки (лево или право),
L – список находящихся на левом берегу,
R – список находящихся на правом берегу.
Первоначальное состояние: Wgc (left(wolf, goat, cаbbage), []).
Конечное состояние: Wgc (right, [], (wolf, goat, cabbage)).
Использование двух списков упрощает описание переходов. Для проверки зацикливания удобно сохранять списки обитателей в отсортированном виде: волк всегда будет в списке перед козой и оба перед капустой. Переходы между состояниями – это перевозка предметов с одного берега на другой, и их можно определить с указанием кого везем. Того, кого везем, будем называть грузом (Cargo). Ситуация, когда фермер едет в лодке один, определяется грузом Alone.
Все возможные переходы классифицируются в три предложения:
-
перевозки слева направо,
-
перевозки справа налево,
-
одиночное плавание в любом направлении.
Для каждого из указанных переходов определим предикат или процедуру:
Update_bоat – изменяет положение лодки,
Update_banks – изменяет состав предметов на берегах.
Предикат select дает описание процедур перемещения, предикат Update_banks поддерживает список обитателей в упорядоченном виде и облегчает проверку на зацикливание. Проверка допустимости переходов делается двумя предикатами:
Legal – легальный,
Illegal – нелегальный.
Существуют ограничения: волк и коза, также как коза и капуста, не могут в отсутствие фермера находится на одном берегу.
Программа, вычисляющая последовательность необходимых перевозок выглядит следующим образом:
domains
str=string
lst=string*
state=wgc(str, lst, lst)
history=state*
moves=string*
predicates
solve_dfs(state, history, moves)
initial_state(state)
final_state(state)
move(state, string)
member(string, lst)
member1(state, history)
update(state, string, state)
update_boat(string, string)
update_bank(string, string, lst, lst, lst, lst)
select(string, lst, lst)
insert(string, lst, lst)
precedes(string, string)
legal(state)
illegal(lst)
test
clauses
test:-
initial_state(State),
solve_dfs(State, [State], Moves), write(Moves).
solve_dfs(State, History, []):–final_state(State).
solve_dfs(State, History, [Move|Moves]):–move(State, Move), update(State, Move, State1), legal(State1), not (member1(State1, History)), solve_dfs(State1, [State1|History], Moves).
initial_state(wgc(left, [wolf, goat, cabbage], [])).
final_state(wgc(right, [], [wolf, goat, cabbage])).
move(wgc(left, L, R), Cargo):–member(Cargo, L).
move(wgc(right, L, R), Cargo): –member(Cargo, R).
move(wgc(B, L, R), alone).
update(wgc(B, L, R), Cargo, wgc(B1, L1, R1)): – update_boat(B, B1), update_bank(Cargo, B, L, R, L1, R1).
update_boat(left, right).
update_boat(right, left).
update_bank(alone, B, L, R, L, R).
update_bank(Cargo, left, L, R, L1, R1): –select(Cargo, L, L1), insert(Cargo, R, R1).
update_bank(Cargo, right, L, R, L1, R1): –select(Cargo, R, R1), insert(Cargo, L, L1).
insert(X, [Y|Ys], [X,Y|Ys]): –precedes(X, Y).
insert(X, [Y|Ys], [Y|Zs]): –precedes(Y, X), insert(X, Ys, Zs).
insert(X, [], [X]).
precedes(wolf, X).
precedes(X, cabbage).
legal(wgc(left, L, R)): –not(illegal(R)).
legal(wgc(right, L, R)): –not(illegal(L)).
illegal(L): –member(wolf, L), member(goat, L).
illegal(L): –member(goat, L), member(cabbage, L).
select(X, [X|Xs], Xs).
select(X, [Y|Ys], [Y|Zs]): –select(X, Ys, Zs).
member(X, [X|Xs]).
member(X, [Y|Ys]): –member(X, Ys).
member1(X, [X|Xs]).
member1(X, [Y|Ys]): –member1(X, Ys).