Представление знаний в интеллектуальных системах
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
?ля того, чтобы построить требуемый план, мы должны отыскать последовательность ходов, реализующую заданную трансформацию.
Эту задачу можно представлять себе как задачу выбора среди множества возможных альтернатив. В исходной ситуации альтернатива всего одна: поставить кубик С на стол. После того как кубик С поставлен на стол, мы имеем три альтернативы:
поставить А на стол или
поставить А на С, или
поставить С на А. (Рис.)
Ясно, что альтернативу "поставить С на стол" не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.
Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:
(1) Проблемные ситуации.
(2) Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.
Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний.
3.Преобразование унарных предикатов в бинарные. Примеры. Преобразование m-арных предикатов в произведение бинарных.
Преобразование унарных предикатов в бинарные
Унарный предикат проверяет некоторое свойство одного аргумента. Типичный пример - функция, используемая в качестве критерия поиска первого простого числа.
Бинарные предикаты обычно сравнивают некоторое свойство двух аргументов. Например, чтобы отсортировать элементы по нестандартному критерию, программист передает алгоритму простую предикатную функцию.
Унарный предикат состоит из предикатного имени и значения своего единственного аргумента. Следовательно, его формат такой: Предикатное_имя (значение_аргумента). Значение аргумента есть конкретизация предикатного имени или переменной. Например, Человек (Сократ) указывает, что имя собственное Сократ - конкретизация имени совокупности человек, а Человек (х) указывает, что х - человек (не что-либо иное). Фразу Сократ - человек можно представить бинарным предикатом Конкр (Сократ, человек).
Преобразование m-арных предикатов в произведение бинарных
Фразу Жак посылает книгу Мари нетрудно представить тернарным (т.е. с тремя аргументами) предикатом:
Посылка (Жак_2, Мари_4, Книга_22).
Определив новые предикаты, можно представить эту фразу произведением (конъюнкцией) бинарных предикатов:
Отправитель (Посылка, Жак_2)
Получатель (Посылка, Мари_4)
Объект (Посылка, Книга_22).
Данная логическая формула читается так: отправитель посылки - Жак, получатель посылки - Мари и объект посылки - книга.
Этот пример подсказывает правило преобразования m-арных предикатов (с m аргументами) в эквивалентное произведение бинарных предикатов. Всякий m-арный предикат состоит из предикатного имени и m значений аргументов:
Предикатное_имя(значение_1, значение_2, ..., значение_m).
Например, предикат для описания посылки некоторого объекта отправителем получателю может иметь следующий формат:
Посылка (отправитель, получатель, объект).
Функция отправитель посылки учитывается первым аргументом, функция получатель посылки - вторым, функция объект посылки - третьим. Первоначально выбранный порядок аргументов для соответствия функция - аргумент может быть произвольным, но должен сохраняться неизменным. Функциональную организацию m-арного предиката можно представить так:
Предикатное_имя (функция_1, функция_2, ..., функция_т).
При записи m-арного предиката через бинарные предикаты используется специальное соглашение, позволяющее сохранить и явно указать соответствующие функциональные отношения. Каждая функция становится именем бинарного предиката, первый аргумент которого является именем исходного m-арного предиката, а второй - значением относящегося к этой функции аргумента. Функциональная организация исходного m-арного предиката и значения его аргументов представляются произведением бинарных предикатов:
Функция_1 (предикатное_имя, значение_1) Функция_m (предикатное_имя, значение_m).
4.Основные стратегии решения задач. Поиск в ширину
Основные стратегии решения задач
Общая схема для представления задач называется пространством состояний. Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"), а решение задачи сводится к поиску пути в этом графе. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. Две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.
Поиск в ширину
В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует
Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоят в том, что нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель
в ширину (Пути, Решения)
истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот