Противоположным поиску в длину можно считать поиск в ширину (breadth-first search). Этот метод проверяет все узлы одного уровня, прежде чем перейти к исследованию узлов, лежащих на следующем более глубоком уровне. На рис. 7.8 показан ход поиска в ширину цели С.
Несмотря на то, что представление пространства поиска в виде бинарного Дерева облегчает описание действий при поиске в ширину, многие пространства поиска, и, в частности, наш пример с рейсами, не являются бинарными Деревьями. Следовательно, в этом случае определение "ширины" немного субъективно и зависит от конкретной задачи. Что касается примера о рейсах самолетов, при поиске в ширину проверяется, не соединен ли любой рейс Из пункта отправления с рейсом до нужного пункта назначения. Другими словами, прежде чем перейти на следующий уровень, просматриваются Пункты назначения всех рейсов, вылетающих из пункта отправления.
Для того чтобы заставить класс search выполнять поиск в ширину, следует внести изменения в функцию findrouteo, как показано в листинге 7.2.
Листинг 7.2. Реализация поиска в ширину ;t
// Определяет, есть ли маршрут между from и to. void Search::findroute(string from, string to) {
int dist; Flightlnfo f;
// Этот стек нужен при поиске в ширину. stack<FlightInfo> resetStck;
// Проверяет, есть ли рейс до пункта назначения, if (match (from, to, dist)) {
btStack.push(Flightlnfo(from, to, dist));
return;
}
// Далее следует первый фрагмент изменений
// для поиска в ширину. В нем проверяются все рейсы
//из заданного узла.
while(find(from, f)) {
resetStck. push (f); (
if(match(f.to, to, dist)) { resetStck.push(Flightlnfo(f));
btStack.push(Flightlnfo(from, f.to, f.distance)); btStack.push(FlightInfo(f.to, to, dist)); return;
}
}
// В следующем фрагменте переустанавливаются поля skip, // установленные в предшествующем цикле while. // Это изменение, необходимое для поиска в ширину, while(!resetStck. empty()) {
resetSkip(resetStck.top());
resetStck.pop();
}
// Проверяет следующий рейс, if (find (from, f)) {
btStack.push(Flightlnfo(from, to, f.distance));
findroute(f.to, to);
}
else if (!btStack.emptyO) {
// Откат и проверка другого рейса.
f = btStack.top О;
btStack.pop();
findroute(f.from, f.to);
}
}
Следует внести в функцию два изменения. Во-первых, цикл for проверяет все рейсы из пункта отправления (from) для того, чтобы выяснить, не соединен ли какой-нибудь из них с рейсом до цели. Во-вторых, если цель не найдена, поля skip этих соединяющих рейсов очищаются с помощью новой функции resetskipO, которую нужно добавить в класс search. Рейсы, в которых нужна переустановка полей skip, запоминаются в собственном стеке resetstack локальной переменной функции findrouteO. Подобная Переустановка необходима, чтобы эти рейсы можно было включать в альтернативные пути.
Далее приведена функция resetskip ().
Il Переустановка полей skip в векторе flights.
void Search::resetSkip(Flightlnfo f) {
for(unsigned i=0; i < flights.size(); i++) if(flights[i]-from == f.from &&
flights[i].to == f.to) flights[i].skip = false;
}
Для тестирования поиска в ширину замените функцию findrouteO в листинге 7.1 и добавьте функцию resetskipo. Далее приведен вывод решения найденного программой поиска в ширину.
From? New York To? Los Angeles
New York to Toronto to Los Angeles Distance is 3000
|
