01:551 Интеллектуальный поиск Вывод знаний 1. © Муромцев Д.И. Лекция 7 01:552 Поиск в пространстве состояний (state space search) Пространством состояний. - презентация

1 01:551 Интеллектуальный поиск Вывод знаний 1

2 © Муромцев Д.И. Лекция 7 01:552 Поиск в пространстве состояний (state space search) Пространством состояний называется множество всех возможных состояний среды, достижимых из начального состояния посредством применения знаний из БЗ. Гарантирует ли процесс поиска нахождение решения? Является ли поиск конечным, или в нем возможны зацикливания? Является ли найденное решение оптимальным? Как процесс поиска зависит от времени выполнения и используемой памяти? Как можно наиболее эффективно упростить поиск? Как наиболее эффективно использовать язык представления знаний?.

3 © Муромцев Д.И. Лекция 7 01:553 Понятие задачи поиска

4 © Муромцев Д.И. Лекция 7 01:554 Дерево поиска

5 © Муромцев Д.И. Лекция 7 01:555 Критерии структурированности задачи поиска Начальное состояние. В общем случае определение начального состояния может потребовать выполнение специальной процедуры для сбора необходимых данных. Описание возможных действий при решении задачи. Проверка цели. Чаще всего цель задается явно, в виде множества целевых состояний. Но возможно, что в некоторых случаях цель описывается на абстрактном уровне и для проверки является ли текущее состояние целевым необходимо выполнять процедуру сопоставления. Например, в шахматах цель состоит в достижении состояния «мат», но поставить мат можно множеством способов. Оценка стоимости пути. Выбор кратчайшего пути связан с оценкой расстояния, которое необходимо преодолеть для достижения цели. В реальных задачах стоимость пути поиска может рассчитываться в зависимости от многих факторов. Например, в шахматной партии при выборе очередного хода учитывается не только количество и расположение фигур, но и возможная стратегия противника. Таким образом, имеют место неявные факторы, которые невозможно просчитать заранее, но необходимо учитывать при оценке стоимости того или иного хода.

6 © Муромцев Д.И. Лекция 7 01:556 Стратегии поиска (search strategy) Оценка стратегий: возможность достижения цели, оптимальность найденного решения и скорость поиска. Критерии выбора стратегий: Полнота перебора. Стратегия называется полной, если она гарантирует нахождение целевого состояния, если оно существует в заданном пространстве. Время поиска. Оценивается общее время, необходимое на поиск решения в зависимости от общего числа возможных состояний. Требуемый объем памяти. Оценивается необходимый для работы алгоритма объем памяти. Оптимальность. Стратегия будет оптимальной, если найденное решение удовлетворяет заданным критериям оптимальности. При этом решение не обязательно должно быть наилучшим. Минимальность. Стратегия называется минимальной, если она гарантирует нахождение наилучшего решения.

7 © Муромцев Д.И. Лекция 7 01:557 Классы стратегий поиска слепой или неинформированный поиск, направленный поиск. Первая группа стратегий осуществляет обычный перебор состояний, пока не будет найдено целевое. Основными представителями являются стратегия поиска в ширину и стратегия поиска в глубину. Стратегии направленного поиска основаны на использовании доступной или дополнительной информации, ограничивающий выбор альтернативных состояний из тех, которые ведут к цели и, возможно, наикратчайшим путем. Подобные стратегии также называют эвристическим поиском, так как они применяют для получения решения некоторые специфические для данной задачи знания.

8 © Муромцев Д.И. Лекция 7 01:558 Стратегия поиска в глубину (depth-first)

9 © Муромцев Д.И. Лекция 7 01:559 Реализация поиска в глубину С помощью стека или очереди LIFO (Last-In-First-Out). Рекурсивный вызов функции поиска для каждой из дочерних вершин дерева поиска. Поиск в глубину требует сравнительно небольших объемов памяти для своей работы, так как необходимо хранить только единственный путь от вершины, соответствующей начальному состоянию, до вершины текущего состояния. Для дерева поиска с коэффициентом ветвления n и глубиной m необходимо хранить в памяти только nm + 1 вершин. Сократить использование памяти можно, если использовать поиск с возвратами, запоминается информация о том, какой потомок должен быть рассмотрен следующим для текущей вершины. В памяти храниться ссылка только на одного потомка, а не на всех. Следовательно, оценка памяти сокращается с nm до m.

10 © Муромцев Д.И. Лекция 7 01:5510 Недостатки поиска в глубину Недостатком стратегии поиска в глубину является вероятность более длительной работы из-за необходимости просматривать на значительную глубину ветви, которые оказываются тупиковыми. Если пространство поиска имеет бесконечные ветви, то алгоритм в принципе не сможет отыскать решение. В этом смысле стратегия поиска в глубину является не полной. Преодолеть проблему бесконечной глубины ветвей дерева можно с помощью стратегии поиска с ограничением глубины. Эта стратегия предполагает просмотр ветвей на расстояние не глубже чем l вершин. Такой подход дает хороший результат, если известно, что решение существует и находится в пределах заданной глубины поиска. Более совершенной является стратегия поиска в глубину с итеративным углублением.

11 © Муромцев Д.И. Лекция 7 01:5511 Стратегия поиска в ширину (breadth-first) Стратегия поиска в ширину является полной и минимальной, так как в процессе поиска рассматриваются все пути, ведущие из начального состояния в целевое.

12 © Муромцев Д.И. Лекция 7 01:5512 Реализация поиска в глубину Реализуется с помощью очереди FIFO (First-In-First-Out). Для дерева поиска с коэффициентом ветвления n и глубиной m и наихудшем расположении целевой вершины – в самом низу дерева требуется n + n2 + n3 + … + (nm+1 - n) итераций. ГлубинаКоличество вершинВремя работыТребуемая память ,11 секунды1 мегабайт секунд106 мегабайт минут10 гигабайт час1 терабайт суток101 терабайт лет10 петабайт года1 экзабайт предполагалось, что в секунду может быть рассмотрено вершин, и для хранения каждой вершины требуется 1 килобайт памяти

13 © Муромцев Д.И. Лекция 7 01:5513 Поиск на основе данных (data- driven search) Также называют прямой цепочкой вывода (forward chaining). Все или большинство данных заданы в пространстве задачи. Например, задача интерпретации состоит в выборе этих данных и в представлении их для использования в системах интерпретации более высокого уровня. Существует большое количество потенциальных целей, но всего лишь несколько способов представления и применения исходных фактов. Сформировать цель или гипотезы очень трудно в силу избыточности исходных данных или большого числа конкурирующих гипотез.

14 © Муромцев Д.И. Лекция 7 01:5514 Поиск от цели (goal-directed strategy) Называют также обратной цепочкой вывода (backward chaining). Цель поиска явно присутствует в постановке задачи или может быть легко сформулирована. Имеется слишком большое число правил, которые на основе исходных фактов продуцируют возрастающее число заключений или целей. Своевременный отбор целей позволяет отсеять множество тупиковых ветвей, что сокращает пространство поиска. Исходные данные не приводятся в задаче, но подразумевается, что они должны быть известны или могут быть легко получены.

15 © Муромцев Д.И. Лекция 7 01:5515 Двунаправленный поиск Сложности при реализации двунаправленного поиска связаны с эффективным построением пространства поиска и функциями определения потомков, а также с проверкой принадлежности вершин одного дерева к другому. Эта проверка может быть выполнена с помощью хэш-таблицы с постоянной оценкой по времени mn/2.

16 © Муромцев Д.И. Лекция 7 01:5516 Обратный поиск в продукционных системах Осуществляется поиск на «И/ИЛИ» дереве, формируемом на основании множества правил. И/ИЛИ дерево является разновидностью «И/ИЛИ» графа, которые позволяют отражать логические связи, определенные логическими операторами. «И/ИЛИ» граф является частным случаем гиперграфа. Гиперграф является направленным графим, состоящим из множества вершин N и множества гипердуг H. Гипрердуга задается упорядоченной парой, в которой первый элемент является отдельной вершиной из множества N, а второй – подмножеством множества H.

17 © Муромцев Д.И. Лекция 7 01:5517 Пример И/ИЛИ деревьев «И/ИЛИ» дерево для обратной стратегии поиска формируется следующим образом: альтернативные правила представлены с помощью вершин «ИЛИ», литералам и переменным входящим в часть «Если» каждого отдельного правила сопоставляется вершина «И».