Анализ поиска в глубину

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

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

Протиюположным поиску в длину можно считать поиск в ширину (breadth-first search). Этот метод проверяет все узлы одного уровня, прежде чем перейти к исследованию узлов, лежащих на следующем более глубоком уровне. На рис. 7.8 показан ход поиска в ширину цели С.

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

f = rev.topO ; rev.pop О ;

cout f.from to ; dist += f.distance;

cout f.to endl;

cout Distance is dist endl;

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

Рис. 7.8. Обход дерева поиском в ширину цели С

Для того чтобы заставить класс search выполнять поиск в ширину, следует внести изменения в функцию findrouteO, как показано в листинге 7.2.

Листинг7.2.Реализация поиска в ширину

Определяет, есть ли маршрут между from и to. void Search::findroute(string from, string to) {

int dist; Flightlnfo f;

стек нужен при поиске в ширину.

stack<FlightInfo> resetStck;

Проверяет, есть ли рейс до пункта назначения, if(match(from, to, dist)) {

btStack.push(FlightInfo(from, to, dist));

return;

Далее следует первый фрагмент изменений

для поиска в ширину. В нем проверяются все рейсы

из заданного узла.

while(find(from, f)) {

resetStck.push(f);

if(match(f.to, to, dist)) { resetStck.push(Flightlnfo(f));

Следует внести в функцию два изменения. Во-первых, никл for проверяет все рейсы из пункта отправления (from) для того, чтобы выяснить, не соединен ли какой-нибудь из них с рейсом до цели. Во-вторых, если цель не найдена, поля skip этих соединяющих рейсов очищаются с помощью новой

функции resetSkipO, КОТОруЮ НуЖНО ДОбЗВИТЬ В КЛасС Search. РсЙСЫ,

в которых нужна переустановка полей skip, запоминаются в собственном стеке resetstack локальной переменной функции findroute о. Подобная Переустановка необходима, чтобы эти рейсы можно было включать в альтернативные пути.

Далее приведена функция resetskip ().

Переустановка полей skip в векторе flights.

oid Search::resetskip(Flightlnfo f) {

for(unsigned i=0; i < flights.sizeO; i++) if(flights[i].from == f.from &&

btStack.push(Flightlnfo(frcOT, f.to, f.distance)); btstack.push(FlightInfo(f.to, to, dist)); return;

В следующем фрагменте переустанавливаются поля skip, установленные в предшествуоцем цикле while. Это изменение, необходимое для поиска в ширину. vHnile (! resetStck. empty ()) f

resetSkip(resetStck.top());

resetStck.pop 0;

Проверяет следующий рейс, if(find(from, f)) {

btstack.push(Flightlnfo(from, to, f.distance));

findroute(f.to, to);

else if (!btstack.empty0) {

Откат и проверка другого рейса, f = btStack.topO; btstack. pop О; findroute(f.from, f.to);