--&!Seaj

Для большей ясности на рис. 7.5 этот граф представлен в виде дерева. В ос тавшейся части главы будем ссылаться именно на эту графическую верси} расписания. На рис. 7.5 наша цель, Лос-Анджелес, обведена. Отметим так же, что для упрощения структуры графа названия некоторых городов повто> ряются. Таким образом, на рис. 7.5 представлено не бинарное дерево, а про! сто наглядная графическая структура, напоминающая дерево.

Д(ВНвер (Лос-Анджелес) Чикаго Калгари (Лос-Анджелес)

(Лос-Анджелес) Хьюстон Эрбана

(Лос-Аиджелес)

Теперь мы готовы к разработке различных способов поиска, которые буДУ находить маршруты из Нью-Йорка в Лос-Анджелес.

При описании методов поиска любой прямой рейс называется рейсом, а рейс с пересадками - маршрутом. - Пер.

(Структура Flightlnfo и класс Search

pfi написании профаммы поиска маршрута из Нью-Йорка в Лос-ДJджeлec нам потребуется база данных, содержащая информацию о рейсах 1С0Мпании. Каждый элемент базы должен включать в себя пункты отправления и назначения, расстояние между ними и флаг, помогающий при возвра-JC или откате. Эти сведения содержатся в структуре Flightlnfo, приведенной далее..

Информация о рейсе, struct Flightlnfo {

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

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

int disteuice; расстояние от from до to

bool skip; используется при возврате или откате (бектрекинге)

FlightlnfoO [ from = ; to = ; distance = 0; slcip = false;

Flightlnfo(string f, string t, int d) { from = f; to = t; distance = d; skip = false;

Приведенная структура будет использоваться во всех вариантах поиска, описанных в этой главе.

Варианты поиска с использованием методов искусственного интеллекта инкапсулированы в классе search. Конкретная реализация этого класса будет **еняться при переходе от одного способа поиска к другому. Однако у всех У них общий каркас, приведенный далее.

/ Класс для поиска с использованием методов искусственного интеллекта, lass Search {

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

vector<Fligiitlnfo> flights;

254 {j]aBQj

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

Если есть рейс от from и до to,

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

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

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

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

При заданном from ищет любой рейс. Возвращает true, если рейс найден, и false - в противном случае, bool find(string from, Flightlnfo &f);

public:

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

void addflight(string from, string to, int dist) { flights.pushbaclc(Flightlnfo(from, to, dist));

Показывает маршрут и общее расстояние, void route();

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

Возврашает true, если маршрут был найден, bool routefoundO {

return ! btStaclc. enpty ();

В классе search объявлены две переменные-экземпляра со спецификатором доступа private. Первая - вектор объектов типа Fiightmfo, названный flights и содержащий данные о рейсах (напоминаю, что вектора