- •Данные и знания
- •При обработке на эвм, знания трансформируются алогично данным
- •Существует несколько способов получения слотов значений во
- •Формальные логические модели
- •Лекция №2
- •Вывод на знаниях
- •Стратегия управления выводом
- •Стандартные функции
- •Если мы определяем лисп – функцию
- •Символьные данные
- •Лекция №4 функции в языке лисп
- •Математическая логика в лисПе
- •Параметры
- •Функции для обработки списков
- •Предикаты
- •Лекция №5
- •Построение списков
- •Полный перебор
- •Направление поиска
- •Программирование методов поиска
- •Поиск в глубину, в ширину и по наилучшему варианту
- •Лекция №7 макросы
- •Макрос не вычисляет аргументы
- •Макрос вычисляется дважды
- •Контекст вычисления макроса
- •Пример отличия макроса от макроса
- •Рекурсивные макросы и продолжающиеся вычисления
- •Тестирование макросов
- •Обратная блокировка разрешает промежуточные вычисления
- •Лекция №8
- •Сопоставление с образцом и распознавание образцов
- •Распознавание списочных образцов
- •Условия сопоставимости
- •Использование переменных в образце
- •Сопоставление с переменной образца
- •Лекция № 9
Полный перебор
В области искусственного интеллекта уже с 50-х годов интенсивно исследуются различные методы поиска.
Основным типом поиска является полный перебор (exhaustive / bling search), в котором решение проблемы (последовательность операций) ищется систематическим опробование всех вариантов. Если решение существует, то с помощью полного перебора его всегда можно найти.
Направление поиска
Прямой поиск (forward chaining, data driven search)
Обратный поиск (backward chaining, goal driven search)
Двунаправленный поиск (bi-directional search).
Программирование методов поиска
Рассмотрим поиск решения проблем на основе продукции на простом примере. Рис 6.1. изображает множество городов и имеющихся между ними морских коммуникаций. Наша цель состоит в написании программы, которая ищет маршруты между двумя произвольными городами.
Задача приводит к следующему пространству поиска:
Состояниями пространства являются города;
Операторами являются продукции, отображающие коммуникации. Таким образом, операторы отображают переход из одного состояние в другое.
Пространством поиска является сеть, состоящая из различных городов и коммуникации между ними.
Состояния пространства поиска можно представить просто в виде названия города. Продукции можно изображать в виде пары состояний:
(начальный – город конечный - город)
или в словесном виде: «Если находишься в начальном городе Х, то можешь переместиться в конечный город Y»
Рис 6 .1. Города и коммуникации между нами.
Продукции, соответствующие пространству поиска изображённому на рисунке записаны далее:
(setq *producz*
'((helsinki stokgolm)
(helsinki tallinn)
(helsinki leningrad)
(stokgolm helsinki)
(tallinn helsinki)
(leningrad viborg)
(viborg helsinki)))
Функция МАРШРУТ ищет путь между двумя городами:
(defun marsh(begin end order)
(search1 end
(primenim begin)
(list begin)
order ))
Функция ПРИМЕНИМЫ возвращает продукцию , применимые в данной ситуации:
(defun primenim (sostoian)
(mapcan #'(lambda (rule)
(if (eq sostoian (car rule))
(list rule) nil))
*producz*))
Рассматриваемая далее функция ПОИСК в параметре ПЛАН содержит потенциально применимые в текущей момент продукции. Искомое конечное состояние сохраняется в параметре КОНЕЦ, а маршрут строится в параметре РЕШЕНИЕ.
Если конечный город первого правила и списка ПЛАН совпадает с конечным состоянием, то поиск удался и шаг за шагом сформированный в параметре РЕШЕНИЕ маршрут из состояний можно выдать в качестве решения. Однако список нужно сначала перевернуть, поскольку он строился в обратном порядке. Функция РЕШЕНИЕ состоит из исследованных функцией ПОИСК городов в порядке их прохождения и необязательно отражает маршруты между городами.
(defun search1 (end plan reshen order)
(cond
((null plan ) nil)
((eq end (second (car plan)))
(reverse (cons end reshen)))
((member (second (car plan)) reshen)
(search1 end (cdr plan)
reshen order))
((search1 end (funcall order plan)
(cons (second (car plan)) reshen)
order))
(t (search1 end (cdr plan)
reshen order))))