Информация о рейсах из расписания компании XYZ может быть представлена в виде направленного графа, показанного на рис 7.4. Направленный граф — это граф, в котором линии, соединяющие узлы, содержат стрелку, задающую направление движения. В направленном графе нельзя перемешаться в направлении, противоположном указанному стрелкой.
Для большей ясности на рис. 7.5 этот граф представлен в виде дерева. В 0с тавшейся части главы будем ссылаться именно на эту графическую верси^ расписания. На рис. 7.5 наша цель, Лос-Анджелес, обведена. Отметим так же, что для упрощения структуры графа названия некоторых городов повторяются. Таким образом, на рис. 7.5 представлено не бинарное дерево, а пр0. сто наглядная графическая структура, напоминающая дерево.
Теперь мы готовы к разработке различных способов поиска, которые будУ1" находить маршруты1 из Нью-Йорка в Лос-Анджелес.
Структура Flightlnfo и класс Search
цри написании программы поиска маршрута из Нью-Йорка в Лос-днджелес нам потребуется база данных, содержащая информацию о рейсах компании. Каждый элемент базы должен включать в себя пункты отправления и назначения, расстояние между ними и флаг, помогающий при возвра-fe или откате. Эти сведения содержатся в структуре Flightlnfo, приведенной далее..
ц информация о рейсе, struct Flightlnfo {
string from; // пункт отправления
string to; // пункт назначения
int distance; // расстояние от from до to
bool skip; // используется при возврате или откате (бектрекинге)
FlightlnfoO ( from = " " ; to = "n; distance = 0; skip = false;
}
Flightlnfo(string f, string t, int d) { from = f; to = t; distance = d; skip = false;
}
);
Приведенная структура будет использоваться во всех вариантах поиска, описанных в этой главе.
Варианты поиска с использованием методов искусственного интеллекта инкапсулированы в классе search. Конкретная реализация этого класса будет Меняться при переходе от одного способа поиска к другому. Однако у всех У них общий каркас, приведенный далее.
II Класс для поиска с использованием методов искусственного интеллекта. cUss Search {
// Этот вектор содержит информацию о рейсе.
vector<FlightInfo> flights;
II Этот стек используется для возврата. stack<FlightInfo> btStack;
// Если есть рейс от from и до to,
// то в dist запоминается расстояние.
// Возвращает true, если рейс существует, и
// false — в противном случае.
bool match(string from, string to, int &dist);
// При заданном from ищет любой рейс. // Возвращает true, если рейс найден, II и false — в противном случае, bool find (string from, Flightlnfo Set);
public:
// Помещает рейсы в базу данных.
void addflight(string from, string to, int dist) { flights.push_back(Flightlnfo(from, to, dist));
}
// Показывает маршрут и общее расстояние, void route();
// Определяет, есть ли маршрут между from и to. void findroute(string from, string to);
// Возвращает true, если маршрут был найден, bool routefound() {
return !btStack.empty();
}
};
В классе search объявлены две переменные-экземпляра со спецификатором доступа private. Первая — вектор объектов типа Flightlnfo, назван ный flights и содержащий данные о рейсах (напоминаю, что вектор "
контейнер библиотеки STL, который реализует динамический массив). Вторая переменная — стек, названный btstack и используемый для воз-ррата или отката. Как вы увидите, стек для возврата очень важен во всех рариантах поиска.
Класс search содержит две встроенные функции: addfiighto и r0utefound (). Когда создается первый объект типа search, его вектор flights пуст. Рейсы между городами добавляются с помощью повторяющихся вызовов функции addfiighto с указанием пунктов отправления и прибытия, а также расстояния между ними. Функция addfiighto просто помешает каждый рейс в коней вектора flights, длина которого автоматически увеличивается для того, чтобы вместить новые данные, функция routefoundo определяет, существует ли маршрут между пунктами отправления и назначения, используя данные стека возврата. Если стек пуст, то между городами маршрута нет. В противном случае стек возврата содержит найденный маршрут (процесс формирования маршрута у разных способов поиска различный).
Реализация остальных членов класса search описана в следующих разделах. В табл. 7.3 приведено их краткое назначение.
|
