276 Гл

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

flights[i].to == to && !flightsti].skip)

flights[i].skip = true; предотвращает повторное использование dist = flights[i].distance; return true;

return false; не найден

Версия восхождения на гору .

При заданном from находит самый длинный рейс из from.

Возврашает true, если он найден.

и false - в противном случае.

bool Search: .-find(string from, Flightlnfo &f)

int pos = -1; int dist =0;

for (unsigned i=0; i < flights.sizeO ; i++) {

if(flights[i].from == from && !flights[i].skip) { Использует самый длинный рейс, if(flights[i].distance > dist) { pos = i;

dist = flights[i].distance;

if(pos != -1) { f = flights[pos];

flights[pos].skip = true; предотвращает повторное использование return true;

return false;

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

int dist; Flightlnfo f;

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

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

return;

Пробует другой рейс. If(find(frcm, f)) {

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

findroute(f.to, to);

else if(!btstack.emptyO) {

Возвращается и проверяет другой рейс, f = btStack.topO; btStack.popO; findroute(f.from, f.to);

int mainO { char to[40], fram[40]; Search ob;

Добавляет сведения о рейсах в базу, ob.addflight( New York , Chicago , 900); ob.addflight( Chicago , Denver , 1000); ob.addflight( New York , Toronto , 500); ob.addflight( New York , Denver , 1800); ob.addflight( Toronto , Calgary , 1700); ob. addflight( Toronto , Los Angeles . 2500);

278 Глава?

ob.addflight( Toronto , Chicago , 500); ob.addflight( Denver , Urbana , 1000); ob.addflight( Denver , Houston , 1000); ob.addflight( Houston , Los Angeles , 1500); ob.addflight( Denver , Los Angeles , 1000);

Получает названия пунктов отправления и назначения, cout From? ;

cin.getline(from, 40); cout To? ;

cin.getline(to. 40);.

Проверяет, есть ли маршрут между from и to. ob.findroute(from, to);

Если маршрут существует, отображает его. if(ob.routefound())

ob.routeO; *

return 0;

Выполнение программы приводит к следующему рещению: From? New York То? Los Angeles

New York to Denver to Los Angeles Distance is 2800

Очень хорошее решение! Маршрут содержит минимальное число пересадок (только одну) и является самым коротким. Таким образом, найден наилучший возможный маршрут.

Но если бы не существовало рейса между Денвером и Лос-Анджелесом, решение не было бы таким хорошим. Пришлось бы лететь из Нью-Йорка в Денвер, потом в Хьюстон и наконец в Лос-Анджелес, преодолевая расстояние в 4300 миль! В этом случае решение взбирается на ложную вершину , потому что перелет в Хьюстон не приближает нас к Лос-АнджелесУ-На рис. 7.10 показаны найденное решение и ложная вершина.