Применение оценочных функций при эвристическом поиске

Различные стратегии управления поиском в пространствах состояний

Общая схема задачи ИИ включает в себя 3 компонента: пространство состояний, набор разрешенных ходов и стратегию управления поиском. Существует 2 основных типа стратегий:

· безвозвратный поиск;

· проблемный поиск.

В безвозвратном режиме управления правило, прикрепленное к текущему состоянию, используется необратимо, другое правило к этому состоянию не может быть применено. Состояние включается в решение раз и навсегда, вместо дерева поиска — лишь одна ветвь.

В пробном режиме управления резервируется возможность возврата, т.е. применения к состоянию разных правил, и, соответственно, поиск решения при просмотре вершин порождает дерево.

Различается два типа проблемных решений управления.

Если для продолжения нужно выбрать один путь из всего множества путей-кандидатов, и этот путь выбирается по заранее заданной схеме, то это неинформированный поиск.

Если этот выбор осуществляется из эвристических соображений, то это эвристический, или информированный поиск.

Все рассмотренные нами виды поиска: поиск в глубину, поиск в ширину — относятся к неинформированному поиску. При неинформированном поиске дерево растет во всех направлениях, в результате чего просматривается много вершин. Эвристический поиск на каждом шаге выбирает для продолжения путь, наиболее перспективный с точки зрения достижения цели. За счет этого удается сфокусировать рост дерева в направлении, близком к целевой вершине.

Для многих задач имеется возможность использовать информацию, относящуюся к предметной области задачи, для управления поиском.

Рассмотрим, например, такую задачу. Имеется шахматная доска
n*n, где n — очень большое число. Требуется перевести коня из левого верхнего угла в правый нижний за минимальное число ходов. Очевидно, что разумной эвристикой будет движение вдоль главной диагонали. Но эвристическая информация должна иметь числовой вид.

Построим оценочную функцию f(u), принимающую на вершинах графа состояний действительные значения. Таким образом, f(u) — оценка перспективности вершины u. Договоримся строить f таким образом, чтобы вершина с меньшим значением f с большей вероятностью находилась на минимальном пути к целевой вершине.

Определим f так, чтобы ее значение f(u) для любой вершины u оценивало сумму стоимостей минимального пути от исходной вершины s к вершине u + стоимость минимального пути от s до t при условии, что он проходит через вершину u.

Определим функцию f*(u) как стоимость минимального пути от s до u + стоимость минимального пути от u до t:

f*(u)=g*(u)+h*(u).

Мы хотим, чтобы наша оценочная функция f(u) была оценкой f*(u) (стоимости настоящего минимального пути от s до t через u). Тогда

f(u)=g(u)+h(u), где

g(u) — стоимость уже пройденного пути от s до u (не обязательно минимального!),

h(u) — значение эвристики вершины u.

Таким образом, g(u) есть оценка g*(u) и g(u)≥g*(u); h(u) есть оценка пути, который придется пройти от u до t, и возможны два варианта этой оценки:

h(u)≤h*(u) и h(u)>h*(u).

Эвристики первого типа называются «малыми», эвристики второго типа — «большими».

Как мы увидим далее, эвристики «малого» типа гарантируют минимальность решения, если удается завершить поиск за реальное время. Эвристики «большого» типа не гарантируют того, что решение будет найдено, но если оно будет найдено, то за наименьшее время, так как «большие» эвристики очень сильно фокусируют поиск в направлении целевой вершины.

Задача о поиске кратчайшего пути

На рис. 6 показан пример поведения конкурирующих процессов. Дана карта городов с расстояниями между ними, задача состоит в том, чтобы найти кратчайший маршрут из стартового города s в целевой город t. В качестве оценки стоимости остатка маршрута из города X до цели мы будем использовать расстояние по прямой расст(X, t) от X до t. Таким образом,

f(X) = g(X) + h(X) = g(X) + расст(X, t)

Мы можем считать, что в данном примере процесс поиска с предпочтением состоит из двух процессов. Каждый процесс прокладывает свой путь — один из двух альтернативных путей: Процесс 1 проходит через а, Процесс 2 — через е. Вначале Процесс 1 более активен, поскольку значение f вдоль выбранного им пути меньше, чем вдоль второго пути. Когда Процесс 1 достигает города с, а Процесс 2 все еще находится в е, ситуация меняется:

f(c) = g(c) + h(c) = 6 + 4 = 10

f(e) = g(e) + h(e) = 2 + 7 = 9

Поскольку f(e) < f(c), Процесс 2 переходит к f, а Процесс 1 ждет. Однако

f(f) = 7 + 4 = 11

f(c) = 10

f(c) < f(f)

Поэтому Процесс 2 останавливается, а Процессу 1 дается разрешение продолжать движение, но только до d, так как f(d) = 12 > 11. Происходит активация процесса 2, после чего он, уже не прерываясь, доходит до цели t.

Рисунок 6. Поиск кратчайшего маршрута из s в t

(а) Карта со связями между городами; связи помечены своими длинами; в квадратиках указаны расстояния по прямой до цели t.

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

1.4.3. А-алгоритм и А*-алгоритм

Опр. 1. Информированный поиск с оценочной функцией f(u)=g(u)+h(u), где h(u) — эвристика вершины u, называется А-алгорит­мом.

Опр. 2. А-алгоритм с эвристической функцией h(u)≤h*(u) для любой u называется A*-алгоритмом.

Итак, эвристический поиск действует следующим образом. В каждый момент имеется несколько путей-кандидатов в решение.

Концевая вершина каждого пути оценивается согласно функции f, и для продолжения выбирается путь, оканчивающийся вершиной с минимальной f-оценкой.

Покажем, что поиск в ширину есть частный случай A-алгоритма. Поиск в ширину — это неинформированный поиск, следовательно, h(u)≡0 для любой u. Смысл g(u) — расстояние, пройденное от s до u. Следовательно, g(u) — это уровень или количество ребер от вершины s до вершины u. Как известно, поиск в ширину всегда находит минимальный путь, так как просматривает большое количество вершин пространства состояний. Это наводит на мысль, что использование «малых» эвристик будет давать минимальные решения с просмотром большого количества вершин, в то время как использование «больших» эвристик будет очень сильно фокусировать поиск без всяких гарантий, что поиск «не пройдет мимо» целевой вершины.

Дадим точные определения.

Опр. 3. Пусть A₁ и A₂ — два варианта A*-алгоритма, использование эвристические функции h₁ и h₂. Назовем A₂ более информированным, чем A₁, если для всех нецелевых вершин h₂(u)≥h₁(u) и для всех целевых h₁(u)=h₂(u)≡0.

Теорема 1.

Если A₁ и A₂ — варианты A* — алгоритма, и A₂ более информирован, чем A₁, то A₂ просмотрит вершин не больше чем A₁.

Теорема 2.

Если A1 является A* — алгоритмом с h(u)≤h*(u) для всех вершин, то A1 находит минимальное решение.

Не будем рассматривать строгое доказательство этих теорем, но дадим неформальное доказательство того, что «большие» эвристики сильно фокусируют поиск в направлении целевой вершины.

Пусть у нас имеется A-алгоритм с эвристикой h(u)>>g(u). Пусть на каком-то шаге имеются два пути-кандидата, оканчивающимися вершинами u₁ и u₂, причем вершина u₁ более «продвинута» в направлении целевой вершины (рис. 7):

Рисунок 7. Фокусировка дерева поиска с помощью «большой эвристики»

Так как u₁ лежит дальше от начала поиска, то g(u₁)>g(u₂). Соответственно, оценка расстояния от вершины u₁ до t меньше соответствующей оценки для u₂: h(u₁)<h(u₂).

Так как h — «большая» эвристика, то она сильно убывает в направлении целевой вершины, т.е.:

h(u₂)-h(u₁)>>g(u₁)-g(u₂)

Таким образом получаем, что

g(u₂)+h(u₂)>>g(u₁)+h(u₁),

то есть более «продвинутые» пути всегда будут иметь меньшие f-оценки, и А-алгоритм никогда не вернется к пути, оканчивающемуся вершиной, близкой к началу поиска.

Дата добавления: 2015-06-27