264 [пава?

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

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

if(flights[i].from == from && !flights[i].skip) { f = flights[i];

flights[ij.skip = true; препятствует повторному использованию return true;

return false;

Пункт отправления передается в переменной from. Если рейс найден, функция find о возвращает true, а объект типа Flightlnfo, связанный с этим рейсом, запоминается в переменной, на которую ссылается второй параметр f. В противном случае функция find о возврашает false. Различие между функциями find о и match о СОСТОИТ В ТОМ, ЧТО первая определяет, есть ли рейс между двумя заданными городами, а вторая выясняет, есть ли рейс из заданного города в любой другой.

Как и matcho, функния findO использует поле skip для управления возвратом из тупиков.

Функция findrouteO

Код, в котором действительно находятся соединяющие города рейсы, содержит функция findroute (), ключевой метод при поиске маршрута между городами. Она вызывается с названиями городов - пунктов отправления и назначения в качестве параметров.

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

int dist; Flightlnfo f;

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

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

return;

II Пробует другой маршрут, if(find(from, 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);

Рассмотрим функцию f indroute о подробно. Сначала функция match о проверяет, есть ли рейс между from и to. Если он существует, то цель найдена, рейс помещается в стек и функция заверщается. В противном случае функция f indroute о вызывает функцию find о для поиска рейса между from и каким-нибудь городом. Функция find о возвращает true, если такой рейс найден, в этом случае объект Flightlnfo, описывающий этот рейс, запоминается в переменной f. Если ни один рейс не доступен, функция find о возвращает false. Если рейс существует, он помещается в стек возврата и функция f indroute о вызывается рекурсивно с городом в поле f.to, ставщим новым пунктом отправления. В противном случае выполняется возврат на уровень выще. Предыдущий узел удаляется из стека и функция findroute () вызывается рекурсивно. Этот процесс продолжается до тех пор, пока не достигнута цель или не исчерпана база данных.

Например, если функция findroute () вызывается для поиска маршрута между Нью-Йорком и Чикаго, в первом операторе if условное выражение будет истинным и функция findroute о завсршйтся, так как есть прямой рейс между Нью-Йорком и Чикаго. Ситуация будет сложнее при поиске маршрута между Нью-Йорком и Калгари. В этом случае условное выражение первого оператора if ложно, так как нет прямого рейса между этими двумя городами. Далее во втором условном операторе делается попытка найти прямой рейс из Нью-Йорка до любого другого города. В этом случае функция find о первым находит рейс Нью-Йорк-Чикаго, и сведения о нем помещаются в стек возврата, а функция findroute о вызывается рекурсивно с Чикаго как пунктом отправления. К сожалению, нет маршрута из Чикаго в Калгари, и далее следует несколько неудачных попыток найти маршрут. В конце концов, после нескольких рекурсивных вызовов функции findroute о и немаловажного возврата обнаруживается рейс между Нью-Йорком и Торонто, а из Торонто есть рейс в Калгари. Эта находка вызывает завершение функции findrouteo, последовательное завершение всех ее рекурсивных вызовов. В заключение первоначально вызванная функция

findroute () также возвращается в вызывающую программу. Вы можете до. бавить операторы cout в функцию findrouteO, чтобы увидеть, как она обрабатывает разные пункты отправления и назначения. Важно понять, что функция findrouteO НС возвращает рещение, а формирует его. После выхода из функции findroute () в стеке возврата, в переменной btStack, содержится марщрут из пункта отправления в пункт назначения. Более того, успещна или неудачна работа функции findrouteO, определяется состоянием стека. Пустой стек означает неудачу, в противном случае он содержит рещение.

Как правило, возможность возврата или отката (бектрекинг) - ключевая составляющая поисковых систем с использованием методов искусственного интеллекта. В классе search откат выполняется благодаря применению рекурсии и стека возврата (вот почему язык С++, поддерживающий рекурсию и использующий библиотеку STL, - хороший выбор для разработчика систем искусственного интеллекта). Почти все ситуации отката обрабатываются подобно стеку: первым пришел, последним вышел. В процессе поиска пути впервые встреченные узлы помещаются в стек. При попадании в тупик из стека удаляется последний помещенный в него узел, и с этой точки начинается новый поиск пути. Процесс продолжается до достижения цели или исчерпания всех возможных путей.

Отображение маршрута

Функция routeo, приведенная далее, выводит на экран найденный маршрут и его длину.

Отображает маршрут и его длину.

void Search::route()

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

Для отображения маршрута меняет порядок стека на противоположный. while(!btStack.eitptyO ) {

f = btStack.top();

rev.push(f);

btStack.popO ;

Отображает маршрут. while(!rev.enpty()) {