4 Информ поиск

1. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

Лекция №4 Эвристические методы поиска

2. Основная идея

эвристического поиска
состоит в том, что каждой вершине х,
генерируемой в процессе поиска, ставится
в соответствие некоторая оценка f(x)
стоимости пути от начальной вершины к
целевой, проходящего через заданную
вершину; если таких путей несколько, то
каждому из них соответствует свое f(x);
наиболее перспективной считается
вершина с минимальной оценкой.

3. Оценка состояния

Начальное
состояние
g(x)
Текущее
состояние
f(x)=g(x) – алгоритм равных цен
f(x)=h(x) – жадный алгоритм
f(x)=g(x)+h(x) – А-алгоритм
h(x)
Целевое
состояние

4. А* алгоритм

5. Реализация процедуры раскрытия вершин

6. Пример поиска

7. Модификации А*-алгоритма

направленные на снижение потребностей
в памяти:
IDA*
RBFS
SMA*

8. Iterative Deepening A* – IDA*

Простейший способ сокращения
потребностей в памяти для поиска А*
состоит в применении идеи итеративного
углубления в контексте эвристического
поиска. В методе IDA*, в отличие от
итеративного поиска в глубину, поиск
ограничивается не текущим пределом
глубины, а текущим пределом значений
оценок узлов (т.е. эвристических fзначений узлов)

9. Пример IDA*

Bound=f(s)=6
Выполнить поиск в глубину, ограниченный
значением f<=6. На этом этапе поиска
развертывается узел s, формируются узлы a и e и
обнаруживаются следующее:
f(a)=7 > Bound
f(e)=9 > Bound
NewBound=min{7, 9}=7
Выполнить поиск в глубину, ограниченный
значением f<=7, начиная с узла s. Узлами с fзначениями, непосредственно превышающими
этот предел, являются b и e.
NewBound=min {f(b), f(e)} = min {8, 9}=8.
В последующем предел Bound изменится
следующим образом: 9 (f(e)), 10 (f(c)), 11 (f(f)). Для
каждого из этих значений выполняется поиск в
глубину. При выполнении поиска в глубину со
значением Bound=11 возникает ситуация
«решение найдено».

10. Recursive Best-First Search (RBFS)

Различие между алгоритмами А* и RBFS
состоит в том, что первая обеспечивает
хранение в памяти всех ранее
сформированных узлов, а последняя
предусматривает хранение только
текущего пути поиска и одноранговых
узлов вдоль этого пути.

11. Пример RBFS

12. Simplified MA* (SMA)

Алгоритм SMA* действует полностью
аналогично А*, развертывая наилучшие
листовые узлы до тех пор, пока не будет
исчерпана доступная память. С этого момента
он не может добавить новый узел к дереву
поиска, не уничтожив старый. В алгоритме
SMA* всегда уничтожается наихудший
листовой узел (тот, который имеет
наибольшее f-значение). Как и в алгоритме
RBFS, после этого в алгоритме SMA*
значение забытого (уничтоженного) узла
резервируется в его родительском узле.

13. Эвристика

(др.-греч. ευρίσκω «отыскиваю»,
«открываю») — наука, изучающая
творческую деятельность, методы,
используемые при открытии новых
концептов, идей и взаимосвязей между
объектами и совокупностями объектов, а
также методики процесса обучения.
Эвристические методы (другое название
эвристики) позволяют ускорить процесс
решения задачи.

14. Примеры эвристических оценок для игры «Пятнашки»

Количество фишек, стоящих не на своем
месте
Сумма расстояний всех фишек до своих
целевых позиций

15. Критерий эффективности эвристической функции

Если общее количество узлов,
вырабатываемых в процессе поиска А*
решения конкретной задачи, равно N, а
глубина решения равна d, то b* представляет
собой эффективный коэффициент
ветвления, который должно иметь
однородное дерево с глубиной d для того,
чтобы в нем содержалось N+1 узлов.