кгтинг 7.3. Нахождение маршрута.при помощи метода эвристичессого поиска ргрёмума

♦include <iostreain> ♦include <stack> ♦include <string> ♦include <vector>

using namespace std; /

Информация о рейсе.

struct Flightlnfo (

string from; пункт отправления

string to; пункт назначения

int distance; расстояние между from и to

bool skip; используется при возврате или откате

FlightlnfoO { from = to = ; distance = 0; skip = false;

Flightlnfo(string f, string t, int d) {

f = flights[pos];

flightstpos].skip = true; прелотврашает повторное использование return true;

return false;

Метод find о теперь просматривает всю базу данных в поисках рейса в самый удаленный от места отправления пункт назначения.

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

274 Глава}

from = f ; to = t; distance = d; skip = false;

Эта версия находит маршрут

с помощью эвристики поиска экстремума.

class Search {

Этот вектор содержит информацию о рейсе.

vector<PlightInfo> flights;

Этот стек используется при откате. stack<FlightInfo> btStack;

Если есть рейс между from и to,

запоминает расстояние в переменной dist.

Возвращает true, если рейс существует, и

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

bool match(string from, string to, int &dist);

Версия поиска экстремума или метода восхождения на гору.

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

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

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

bool find(string from, Flightlnfo &f);

public:

Помещает рейсы в базу дан

void addflight(string from, string to, int dist) { flights.push back(FlightInfo(from, to, dist));

Показьшает маршрут и общую длину, void route();

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

II возвращает true, если маршрут найден, tool routefoundo

return btstack.size О != 0;

Показьшает маршрут и общую длину.

void Search::route()

stack<FlightInfo> rev; irit dist = 0; Flightlnfo f;

Меняет порядок стека на противоположный для вывода маршрута. . while(!btstack.ernpty()) { f = btStack.topO ; rev.push(f); btStack.popO ;

Отображает маршрут. WhileOrev.emptyO) {

f = rev.topO ;

rev.popO ;

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

cout f.to endl;

cout Distance is dist endl;

Ч Если есть рейс между from и to,

Ч запоминает длину рейса в dist.

Ч Возвращает true, если рейс существует,

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

bool Search::match(string from, string to, int &dist) {