Поиск в пространстве состояний:стратегии информированного (эвристического) поиска

Лекция 3 Поиск в пространстве состояний: Стратегии информированного (эвристического) поиска Поиск «сначала лучший» (Best-First Search – BFS) • Методы «слепого» поиска в большинстве случаев неэффективны, т. к. • … • Эффективность поиска может быть повышена за счет использования дополнительных специфичных для данного класса задач знаний – эвристик • Эти знания: • должны позволять оценивать желательность раскрытия той или иной вершины в дереве поиска; • их естественно представить оценочной функцией, которая возвращает число, отражающее предпочтительность раскрытия вершин; • BFS (Best-First Search) – поиск, при котором первой раскрывается вершина с максимальной оценкой Реализация BFS через обобщенный поиск • В обобщенном алгоритме поиска единственным местом, где можно использовать дополнительные знания об особенностях задачи является функция построения очереди: Queueing-Fn(Queue, Elements) • Пусть: Eval-Fn – функция оценки; Queuing-Fn – функция, упорядочивающая вершины в соответствии с Eval-Fn Тогда BFS поиск на базе обобщенного поиска General-Seach реализуется следующим образом: function BFS (problem, Eval-Fn) returns a solution sequence return GENERAL-SEARCH (problem, Queuing-Fn) • Название BFS – строго говоря неточно, т. к. оценочная функция не гарантирует абсолютно лучшего, оптимального выбора вершины для раскрытия, а лишь определяет вершину, которая представляется лучшей с точки зрения скорейшего достижения целевого состояния Жадный поиск (Greedy Search) • Жадный поиск – первой раскрывается вершина, состояние которой оценивается как ближайшее к целевому состоянию • Обозначим h(n) – оценочная стоимость самого дешевого пути из состояния вершины n в целевое состояние • h(n) – эвристическая функция • Тогда реализация жадного поиска на основе BFS : function GREEDY-SEARCH (problem) returns a solution or failure return BFS (problem, h) Жадный поиск. Пример В транспортных задачах (поиск путей на графе) в качестве h(n) часто используют расстояние по прямой - hSLD Жадный поиск: пример Шаги жадного поиска для Бухареста. В качестве эвристической функции используется hSLD – расстояние по прямой до Бухареста Эффективность жадного поиска Жадный поиск: • НЕ оптимален; • НЕ полон; • Временная сложность O(bm), m – максимальная глубина пространства поиска; • Емкостная сложность O(bm), (все вершины сохраняются в памяти); • аналогичен поиску в глубину; • как правило находит решение (если оно существует) быстро, хотя оно не всегда является оптимальным; • в конкретных задачах при наличии хорошей эвристической функции емкость и/или время могут быть существенно сокращены Поиск A* • Жадный поиск стремится минимизировать оценочную стоимость пути до цели h(n), что позволяет в ряде случаев повысить эффективность поиска, однако не является ни оптимальным, ни полным • С другой стороны поиск по критерию стоимости использует минимальную стоимость пути до текущего состояния g(n) и является полным и оптимальным, однако часто оказывается неэффективным • Естественно совместить эти два подхода или стратегии, чтобы использовать их преимущества • Введем аддитивную оценочную стоимость: f(n) = g(n) + h(n), f(n) – оценочная стоимость наиболее дешевого пути, проходящего через n Поиск A* • Эвристика h(n) является допустимой (admissible), если она никогда не переоценивает реальное значение (в задачах минимизации) • в задачах максимизации эвристика h(n) допустима, если она никогда не недооценивает реальное значение • Поиск BFS, использующий функцию f (n) = g(n) + h(n), где h(n) является допустимой называется поиском A* • Реализация поиска A* на основе BFS : function A*-SEARCH (problem) returns a solution or failure return BFS (problem, g+h) Поиск A*. Пример Поиск A* в задаче поиска пути до Бухареста: Поиск A*. Пример Шаги поиска A* для пути в Бухарест. Вершины помечены f = g + h. Значения h – расстояние по прямой до Бухареста. Монотонность эвристик • f(n) монотонна, если для каждой вершины n и каждого ее последователя n‘, сгенерированного любым действием a, оценочная стоимость достижения цели из n не больше чем стоимость c(n, a, n’) шага достижения n’ плюс оценочная стоимость достижения цели из n’: f(n) ≤ c(n, a, n’) + f(n’) • Иначе говоря, монотонная f(n) никогда не убывает вдоль пути из корня к цели • Пример. Пусть g(n) = 3, h(n) = 4, т. е. f(n) = 7 g(n’) = 4, h(n’) = 2, т. е. f(n’) = 6 Имеем нарушение монотонности. n f(n) = 3 + 4 = 7 n’ f(n’) = 4 + 2 = 6 Для восстановления используется прием – выравнивание максимального пути: f(n’ ) = max(f(n), g(n’ ) + h(n’ )) • Если эвристика монотонна, то она является допустимой!!! Представление поиска A* контурами A* поиск с монотонной эвристикой можно интерпретировать как поиск по контурам, которые фокусируются в направлении целевой вершины: Контуры для f = 380, f = 400 и f = 420, для исходной точки Arad. Вершины внутри контуров имеют f-стоимость меньше чем значение контура Поиск A* A* поиск фокусируется в направлении целевой вершины. Пусть f * - стоимость оптимального пути, тогда поиск A*: - раскрывает все вершины, у которых f(n) < f * - может раскрывать некоторые вершины, у которых f(n)= f * A* поиск является полным, так как по мере расширения контура с возрастанием f , неизбежно достигается контур, у которого f равна стоимости f * пути к целевому состоянию. A*-поиск является оптимально эффективным – никакой другой алгоритм не гарантирует нахождения оптимальных вершин эффективнее, чем A* поиск Полнота поиска A* • Поскольку A* раскрывает вершины в порядке возрастания f, он рано или поздно должен достичь целевого состояния. • Это справедливо, если число узлов с f(n)  f * не бесконечно • число узлов с f(n)  f * может быть бесконечно, если: • существует узел с бесконечным коэффициентом ветвления • существует путь с конечной стоимостью пути, но бесконечным числом узлов в нем • Итак, A* является полным на графах с конечным коэффициентом ветвления при наличии некоторой положительной константы , такой что стоимость каждого оператора не меньше  Доказательство оптимальности поиска A* Пусть G – оптимальное целевое состояние и f(G) = f * = g(G). Пусть G2 – субоптимальное целевое состояние, т.е. f(G2) = g(G2) > f *. Предположим противное: A* выбрал из очереди G2 (тогда A* завершится с субоптимальным решением) Рассмотрим ситуацию, когда алгоритм мог бы (гипотетически!) достичь целевое состояние G2 (субоптимальное) раньше, чем G (оптимальное): n – вершина, которая в текущий момент является листом на оптимальном пути к G Если n не выбрана для раскрытия раньше G2, то f (n)  f (G2) Поскольку h является допустимой, f * = f(G)  f (n). Таким образом, f *  f (G2). Поскольку h(G2)=0, имеем f *  g(G2) – противоречие! Сложность A* В общем случае: • Временная - O(bd) • Емкостная - O(bd) • Суб-экспоненциальный рост при |h(n) - h*(n)|  O(log h*(n)) • для большинства практических эвристик ошибка, к сожалению, по крайней мере пропорциональна стоимости пути A* является оптимально эффективным для любой заданной h-функции среди алгоритмов расширяющих пути поиска от корня. Т.е никакой другой оптимальный алгоритм не гарантирует раскрытия меньшего числа вершин. • Интуитивно ясно: любой алгоритм, который не раскрывает все вершины в контурах между корнем и контуром цели рискует пропустить оптимальное решение Эвристики h(n) для A* Пример головоломки 8-ка 5 4 6 1 8 8 7 3 2 7 1 Исходное состояние 2 3 4 6 5 Целевое состояние Эвристики: • h1 - число фишек, находящихся в неверной позиции • h2 сумма Манхэттенских расстояний фишек от их целевых позиций • h2 доминирует над h1: n, h2(n)  h1(n) Эвристики h(n) для A* Сравнение стоимости поиска и эффективного коэффициента ветвления для поиска с итеративным углублением и поиска A* с h1 и h2. Данные усреднены по 100 примерам 8-ки, для решений различной глубины Эффективный коэффициент ветвления (effective branching factor) – среднее число преемников узла в дереве поиска после применения эвристик. Характеризует качество используемой эвристической функции. Всегда лучше использовать эвристику h(n) с большими значениями, при условии что она не делает переоценки, т.к. A* раскрывает все вершины с f(n) < f *