ПОИСК В ПРОСТРАНСТВЕ СОСТЯНИЙ

Методы решения задач Представление задач в пространстве состояний

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

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

При подходе к решению задачи с использованием пространства состояний задача рассматривается как тройка (SI, O, SG), где SI – начальное состояние; O – конечное множество операторов, действующих на не более чем счетном множестве состояний; SG – целевое состояние.

Для представления задачи в пространстве состояний необходимо определить форму описания состояний задачи и описание начального состояния; множество операторов и их воздействий на описания состояний; множество целевых состояний или же описание их свойств

Алгоритмы поиска решения в пространстве состояний Поиск в пространстве состояний – процесс постепенного раскрытия вершин и проверки свойств порождаемых вершин. В ходе процесса поиска должны сохраняться указатели от всех возникающих дочерних вершин к их родительским. Эти указатели позволят восстановить путь к начальной вершине после того, как будет построена целевая вершина. Вершины и указатели, построенные в процессе поиска, образуют поддерево графа-пространства состояний. Это поддерево называется деревом поиска.

Основные характеристики поиска в пространстве состояний использование эвристической информации; порядок раскрытия (перебора) вершин; полнота просмотра пространства состояний; направление поиска.

Поиск в ширину Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open. Шаг 2. Если список Open пуст, то завершить поиск и выдать сообщение о неудаче, в противном случае перейти к следующему шагу. Шаг 3. Выбрать первую вершину из списка Open (назовем ее n) и перенести ее в список раскрытых вершин Closed. Шаг 4. Раскрыть вершину n, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели к n. Шаг 5. Проверить, нет ли среди дочерних вершин целевых. Если хотя бы одна - целевая, то завершить поиск и выдать решение задачи с использованием указателей. Иначе перейти к шагу 2.

Поиск в ширину

Алгоритм поиска в ширину Ш1. Поместить начальную вершину в список нераскрытых вершин Open. Ш2. Если список Open пуст, то завершить поиск и выдать сообщение о неудаче, иначе перейти к шагу 3. Ш3. Выбрать первую вершину из списка Open (назовем ее n) и перенести ее в список раскрытых вершин Closed. Ш4. Раскрыть вершину n, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели, к родительской вершине n. Ш5. Проверить, нет ли среди дочерних вершин целевых. Если есть хотя бы одна целевая вершина, то завершить поиск и выдать решение задачи, получающееся просмотром указателей назад от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

Поиск в глубину Глубина вершины в дереве поиска: глубина корня равна нулю; глубина некорневой вершины на единицу больше глубины ее родительской вершины

Алгоритма ограниченного поиска в глубину (D - граничная глубина) 1. Поместить начальную вершину в список нераскрытых вершин Open. 2. Если список Open пуст, то завершить поиск и выдать сообщение о неудаче, иначе – шаг Выбрать первую вершину из списка Open (n) и перенести ее в список раскрытых вершин Closed. 4. Если глубина вершины n равна граничной глубине D, то перейти к шагу 2, иначе перейти к шагу Раскрыть вершину n, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине n. 6. Если среди дочерних есть хотя бы одна целевая вершина, то завершить поиск и выдать решение задачи с использованием указателей. Иначе перейти к шагу 2. Note. Если целевая вершина располагается ниже граничной глубины, она обнаружена не будет.

Поиск в глубину

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

Вопрос эффективности Алгоритмы слепого перебора являются неэффективными методами поиска решения В случае нетривиальных задач число порождаемых вершин велико: если L – длина решающего пути, B – количество дочерних вершин у каждой вершины, то для нахождения решения надо исследовать B L путей из начальной вершины. => комбинаторный взрыв.

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

Эвристический поиск Идея - с помощью эвристической информации оценивать перспективность нераскрытых вершин пространства состояний с точки зрения достижения цели и выбирать для продолжения поиска наиболее перспективную вершину. Реализация - вводится эвристическая оценочная функция Est(V) (эвристика). Эта функция определяется на множестве вершин пространства состояний и принимает числовые значения. Est(V) оценивает перспективность раскрытия вершины (иногда – как вероятность ее расположения на решающем пути). Обычно – чем меньшее Est(V), тем более перспективна вершина. Вершины раскрываются в порядке увеличения (точнее, неубывания) значения оценочной функции.

Алгоритм эвристического поиска 1. Поместить начальную вершину в список нераскрытых вершин Open и вычислить ее оценку. 2. Если список Open пуст, то завершить поиск и выдать сообщение о неудаче, иначе перейти к шагу Выбрать из списка Open вершину с минимальной оценкой (среди вершин с одинаковой минимальной оценкой выбирается любая) и перенести (назовем ее n) в список Closed. 4. Если n – целевая вершина, то завершить поиск и выдать решение задачи, используя указатели, иначе перейти к шагу Раскрыть вершину n, построив все ее дочерние вершины. Если таких вершин нет, то перейти к шагу 2, в ином случае – к шагу Для каждой дочерней вершины вычислить оценку, поместить все дочерние вершины в список Open и построить указатели, ведущие от этих вершин к родительской вершине n. Перейти к шагу 2.

Замечания 1. Поиск в глубину можно рассматривать как частный случай эвристического поиска с оценочной функцией Est(V) = d(V), а поиск в ширину – с оценочной функцией Est(V) = 1/d(V), где d(V) – глубина вершины V. 2. Чтобы использовать рассмотренный алгоритм эвристического поиска на произвольных графах- пространствах состояний, учитывать повторного появления дочерних вершин, которые уже имеются либо в списке Open, либо в Closed. Так как значение оценочной функции для вновь построенной дочерней вершины, входящей в список Open или Closed, может понизиться, то надо корректировать старую оценку вершины, заменяя ее на новую, меньшую. Если вновь построенная вершина с меньшей оценкой входит в список Closed, необходимо вновь поместить ее в список Open, но с меньшей оценкой. Потребуется также изменить направления указателей от всех вершин списков Open и Closed, оценка которых уменьшилась, направив их к вершине n.

Пример Игра в «8» Как оценить перспективность вершины? => т.е. Est(V)=???

Est1(V) = d(V) + k(V) где: d(V) – глубина вершины V, или число ребер дерева на пути от этой вершины к начальной вершине; k(V) – число фишек позиции-вершины V, стоящих не на «своем» месте (фишка стоит не на «своем» месте, если ее позиция отлична от позиции в целевом состоянии).

Эвристический поиск Est1(V) = d(V) + k(V) d(V) – глубина вершины V; k(V) – число фишек позиции- вершины V, стоящих не на «своем» месте

Оценка эффективности Эффективность алгоритмов поиска может быть оценена при помощи такого показателя, как целенаправленность: P = L / N, где L –глубина целевой вершины, N – общее число вершин, построенных в ходе перебора. Р=1, если строятся только вершины решающего пути, в остальных случаях P<1. Алгоритм эвристического поиска с хорошо подобранной оценочной функцией находит решение задачи быстрее алгоритмов слепого перебора. Подбор удачной эвристической функции – наиболее трудный момент при формализации задачи.

Пример Опять игра в «8» Еще одна эвристика – Est2(V)

Est2(V) = d(V) + s(V) d(V) то же, что и для функции Est1 s(V): для каждой из восьми фишек находим сумму двух расстояний – по вертикали и горизонтали – между текущим и целевым состояниями, а затем вычисляем сумму s(V) таких расстояний для всех восьми фишек. s(V) выражает «суммарное расстояние» всех фишек от их целевого положения.

Est2(V) = d(V) + s(V) Est2=0 Est2=?

Допустимость алгоритма эвристического поиска Гарантируют ли алгоритмы эвристического поиска нахождение решающего пути за конечное число шагов в тех случаях, когда решение существует?

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

Допустимость алгоритма эвристического поиска Можно ли найти условия для эвристических оценочных функций, которые гарантируют нахождение решения при условии его существования?

Допустимость алгоритма эвристического поиска Определим на множестве дуг пространства состояний функцию стоимости: с(VA, VB) = стоимость дуги-перехода от вершины VA к вершине VB. Стоимость пути = сумма стоимостей входящих в путь дуг. Цель поиска - не просто нахождение решающего пути, а нахождение оптимального решающего пути – решающего пути с минимальной стоимостью

Специальный вид оценочной функции Est(V) = g(V) + h(V) где –g(V) – оценка оптимального пути от начальной вершины до вершины V, – h(V) – оценка оптимального пути от вершины V до целевой вершины.

А-алгоритм Разновидность алгоритма эвристического поиска, применяемого для поиска оптимального решающего пути и использующего при этом оценочную функцию указанного выше вида

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

Теорема о допустимости А-алгоритма Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину А-алгоритм, использующий некоторую эвристическую функцию вида Est(V) = g(V) + h(V), где g(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, а h(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину, является допустимым, если h(V) h*(V) для всех вершин V пространства состояний. А-алгоритм эвристического поиска с функцией h(V), удовлетворяющей этому условию, получил название А*-алгоритма