Модели эвристического поиска решений

⇐ ПредыдущаяСтр 27 из 32Следующая ⇒

Модели эвристического поиска решений основаны на представлении задачи в пространстве состояний. Некоторая начальная вершина этого пространства соответствует начальному состоянию. Вершины, непосредственно следующие за данной, получаются в результате применения операторов (правил, продукций, алгоритмов), которые применимы в состоянии, ассоциированном с данной вершиной. Определение всех непосредственно следующих вершин для вершины х называется раскрытием вершины х. Обозначим операцию раскрытия вершины как Г(х). Под Г(х) будем понимать множество вершин, непосредственно следующих за вершиной х; коротко назовем вершину уÎ Г(х) потомком вершины х.

Выделим некоторую целевую вершину, соответствующую конечному состоянию.

В приведенных терминах задача формулируется следующим образом:

Заданы начальное S₀ и конечное S_e состояние задачи, а также множество операторов Y.

Найти цепочку операторов , осуществляющую переход . Иначе говоря, требуется найти последовательность вершин S₀, S₁, ..., S_e, порождаемых соответствующими операторами, такую что S_i Î Г(S_i_-1).

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

Стратегия поиска в глубину

Определим глубину вершины в дереве поиска следующим образом:

Глубина корня дерева равна 0.

Глубина вершины х, не являющейся корнем, равна глубине вершины у, такой, что x Î Г(y), сложенной с единицей.

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

(1) Поместить начальную вершину в список, называемый ОТКРЫТ.

(2) Если список ОТКРЫТ пуст, то неудача всего алгоритма, иначе следующий шаг.

(3) В списке ОТКРЫТ взять вершину a с максимальным значением глубины и пронести ее в список ЗАКРЫТ.

(4) Если глубина a равна граничной глубине, то перейти к п. (2), иначе - следующий шаг.

(5) Раскрыть вершину a. Поместить каждую вершину b Î Г(a) в список ОТКРЫТ, если b не принадлежит ни списку ОТКРЫТ, ни списку ЗАКРЫТ.

(6) Если в Г(a) есть целевая вершина, то конец, иначе перейти к п. (2).

Для иллюстрации стратегии поиска в глубину обратимся к задаче отыскания маршрута, связывающего произвольные две вершины в графе. Рассмотрим граф, показанный на рис. 3.7. Пусть требуется найти маршрут, ведущий из вершины 1 в вершину 7. Начальная вершина 1 образует исходный список ОТКРЫТ = {1}.

Далее находим:

В скобках рядом с номером вершины помечено значение глубины вершины в графе. Полагаем ОТКРЫТ = , ЗАКРЫТ = .

Выбираем для раскрытия вершину 2:

Г(2) = {3, 4, 6}.

Поскольку вершина 4 уже фигурирует в списке ЗАКРЫТ, то устанавливаем:

ОТКРЫТ = {4⁽¹⁾, 3⁽²⁾, 6⁽²⁾}; ЗАКРЫТ = {1⁽⁰⁾, 2⁽¹⁾}.

Выбираем в списке ОТКРЫТ вершину с максимальной глубиной, например, 3, и находим

Г(3) = {4}.

Вершина 4 не включается в список ОТКРЫТ, т.к. она там присутствует. Устанавливаем

ОТКРЫТ = {4⁽¹⁾, 6⁽²⁾}; ЗАКРЫТ = {1⁽⁰⁾, 2⁽¹⁾, 3⁽²⁾}.

Выбираем для раскрытия вершину 6:

Г(6) = {1, 5}

Полагаем

ОТКРЫТ = {1⁽¹⁾, 5⁽³⁾}; ЗАКРЫТ = {1⁽⁰⁾, 2⁽¹⁾, 3⁽²⁾, 6⁽²⁾}.

Далее аналогичнонаходим

Г(5) = {3, 8};

ОТКРЫТ = {4⁽¹⁾, 8⁽⁴⁾};

ЗАКРЫТ = {1⁽⁰⁾, 2⁽¹⁾, 3⁽²⁾, 5⁽³⁾, 6⁽²⁾}.

Г(8) = {6, 9}

ОТКРЫТ = {4⁽¹⁾, 9⁽⁵⁾};

ЗАКРЫТ = {1⁽⁰⁾, 2⁽¹⁾, 3⁽²⁾, 5⁽³⁾, 6⁽²⁾, 8⁽⁴⁾}.

Наконец, Г(9) = {7}: Конечная вершина достигнута. Искомый маршрут определяется в обратном порядке через множества Г(a). Так, конечная вершина 7 принадлежит Г(9). Следовательно, вершина 9 должна быть предпоследней вершиной маршрута. Устанавливаем, что 9Î Г(8). Таким образом, вершина 8 должна предшествовать вершине 9 и т.д. Окончательный список вершин, образующий маршрут из вершины 1 в вершину 7 таков: < 1, 2, 6, 5, 8, 9, 7> (рис.3.8).

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

⇐ Предыдущая 22 23 24 25 262728 29 30 31 Следующая ⇒