Стратегия поиска в глубину
Определим глубину вершины в дереве поиска следующим образом:
Глубина корня дерева равна 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(1), 3(2), 6(2)}; ЗАКРЫТ = {1(0), 2(1)}.
Выбираем в списке ОТКРЫТ вершину с максимальной глубиной, например, 3, и находим
Г(3) = {4}.
Вершина 4 не включается в список ОТКРЫТ, т.к. она там присутствует. Устанавливаем
ОТКРЫТ = {4(1), 6(2)}; ЗАКРЫТ = {1(0), 2(1), 3(2)}.
Выбираем для раскрытия вершину 6:
Г(6) ={1, 5}
Полагаем
ОТКРЫТ = {1(1), 5(3)}; ЗАКРЫТ={1(0), 2(1), 3(2), 6(2)}.
Далее аналогичнонаходим
Г(5) = {3, 8};
ОТКРЫТ = {4(1), 8(4)};
ЗАКРЫТ = {1(0), 2(1), 3(2), 5(3), 6(2)}.
Г(8) = {6, 9}
ОТКРЫТ = {4(1), 9(5)};
ЗАКРЫТ = {1(0), 2(1), 3(2), 5(3), 6(2), 8(4)}.
Наконец, Г(9) = {7}: Конечная вершина достигнута. Искомый маршрут определяется в обратном порядке через множества Г(a). Так, конечная вершина 7 принадлежит Г(9). Следовательно, вершина 9 должна быть предпоследней вершиной маршрута. Устанавливаем, что 9ÎГ(8). Таким образом, вершина 8 должна предшествовать вершине 9 и т.д. Окончательный список вершин, образующий маршрут из вершины 1 в вершину 7 таков: <1, 2, 6, 5, 8, 9, 7> (рис.3.8).
Рассмотренный алгоритм не использует каких-либо дополнительных предположений относительно свойств вершин - состояний. В частности, например, знание некоторых свойств, которыми должна обладать конечная вершина - состояние, позволило бы не раскрывать те вершины, которые в силу этих свойств не могут принадлежать результирующему маршруту (см. раздел 2.2). Это свойство используется различными стратегиями перебора с отсечениями.
Дата добавления: 2016-03-05; просмотров: 628;