Поиск в ширину
С
огласно
этой стратегии все узлы графа уровня
(К+1) раскрываются после того, как
построены все узлы уровня К. При К=0
имеем узел с начальным состоянием:
При поиске в ширину рассматриваются вначале все пути, длина которых равна 1, затем все пути, дина которых равна 2.
В итоге просматриваются все пути длиной К, ведущие из начального узла во все остальные.
В общем случае при глубине поиска К и числе ветвей L порядок всех узлов – О(Lк). Это число называется экспоненциальной оценкой сложности. При L=K=10 время просмотра всех узлов со скоростью 1000 узлов в секунду — 128 дней.
Экспоненциальная оценка сложности приводит в итоге к явлению, которое получило название комбинаторный взрыв.Это серьезная проблема. Она возникает, в частности, при попытке перебора всех вариантов позиций при игре в шахматы.
Ясно, что человек-шахматист решает задачу выбора очередного хода каким-то другим способом. Он использует свой опыт, воображение, аналитические способности, знания теории шахматной игры, что в итоге позволяет значительно более экономно, чем с помощью грубого перебора всех вариантов, выбрать нужный ход.
Пространство состояний при решении таких практических задач как распознавание речи, выбор конфигурации компьютерной системы или планирование последовательности операций настолько велико, что его невозможно проанализировать рассмотренными выше общими методами за обозримый промежуток времени. В связи с этим напрашивается вполне естественный вывод — необходим некоторый способ направленного поиска.
Пример.
Метод поиска решения «в глубину»
АЛГОРИТМ (обозначения)
dfs (goal, current, pending) – функция трех аргументов
goal – объект поиска (цель)
current – текущий узел на графе, в самом начале узел исходного состояния (одна буква)
pending – список узлов, претендующих на обработку (в самом начале пустой)
ОБОЗНАЧЕНИЯ:
Символ «:=» – присвоение;
Функция “expand” формирует узлы, следующие за аргументом этой функции;
Знак «+» – слияние двух списков, т.е.; (abc)+(def)=(abcdef);
() – означает пустой список;
first и rest – функции, выделяющие начало и оставшуюся часть списка; first(abc)=a rest(abc)=(bc).
АЛГОРИТМ
dfs(goal, current, pending)
{
if current=goal, then succes;
else
{
pending:=expand(current)+pending;
if pending=() then fail;
else dfs(goal, first(pending), rest(pending));
}
}
ЗАДАНИЕ 1. Найти все «производные» слова от слова AEROPORT (язык русский, алфавит латинский)
Вариант 1: goal = RAPORT
Вариант 2: goal = (ORT ROT PAT PORT TORT RAPORT AEROPORT)
Критерий выч. затрат – число шагов на графе.
ЗАДАНИЕ 2. Разработать аналогичный алгоритм для поиска в ширину.
Указание: нужно изменить только одно выражение в функции dfs.
Рассмотрим процесс поиска на конкретном примере. Пусть имеем карту дорог (рис. 2), по которой мы хотим изучить маршрут движения из одного конкретного города в другой.
Система, построенная на основе знаний об этой карте дорог, должна поработать с картой и спланировать наше путешествие, например из города «А» в город «F».
При решении представленной задачи компьютер преобразует исходную карту и представит ее в виде дерева поиска, которое без учета циклов будет иметь вид рис. 3.
Рис. 2. Карта дорог
Дерево поиска показывает все возможные варианты выбора при движении из «А» (начальное состояние), а также и все варианты выбора в каждом из промежуточных пунктов (состояний).
Место, откуда начинается поиск, находится в вершине дерева поиска.
Все дороги, начинаясь в «А», либо приводят в тупик, либо заканчиваются в «F».
Рис.3. Дерево поиска
Задача компьютера состоит в том, чтобы найти подходящую дорогу из вершины дерева к конечному состоянию (цели) в его нижней части.
Человек при взгляде на дерево поиска сразу же выберет подходящую дорогу, но компьютер на это не способен. Какую стратегию поиска применит компьютер?
Рассмотрим пример, который заставит нас думать как компьютер.
Мы находимся в темной комнате, на стене которой дерево поиска, а у нас фонарик, который освещает всего два соседних пункта.
Нам известно, где расположена вершина дерева, откуда надо начать поиск. Как наиболее эффективно перемещать луч фонарика, чтобы найти маршрут до «F»?
При отсутствии какой-либо дополнительной информации компьютер для поиска использует стратегию «грубой силы». При этом программа поиска осуществляет поиск цели, идя от состояния к состоянию, и систематически исследуя все возможные пути.
Для определения каждого последующего шага применяется некая простая механическая стратегия, которая имеет две разновидности: поиск в глубину и поиск в ширину.