Код, в котором действительно находятся соединяющие города рейсы, содержит функция f indroute (), ключевой метод при поиске маршрута между городами. Она вызывается с названиями городов — пунктов отправления и назначения в качестве параметров.
// Определяет, есть ли маршрут между 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;
}
// Пробует другой маршрут, if(find(from, f)) {
btStack.push(Flightlnfo(from, to, f.distance));
f indrou te (f. to, to) ,-
)
else if(!btStack.empty()) {
// Поднимается на уровень вверх и проверяет другой маршрут.
f = btStack.top();
btStack.pop();
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 () вызывается рекурсивно. Этот процесс продолжается до тех пор, пока не достигнута цель или не исчерпана база данных.
Например, если функция findrouteO вызывается для поиска маршрута между Нью-Йорком и Чикаго, в первом операторе if условное выражение будет истинным и функция findrouteO завершится, так как есть прямой рейс между Нью-Йорком и Чикаго. Ситуация будет сложнее при поиске маршрута между Нью-Йорком и Калгари. В этом случае условное выражение первого оператора if ложно, так как нет прямого рейса между этими двумя городами. Далее во втором условном операторе делается попытка найти прямой рейс из Нью-Йорка до любого другого города. В этом случае функция find о первым находит рейс Нью-Йорк—Чикаго, и сведения о нем помещаются в стек возврата, а функция findrouteO вызывается рекурсивно с Чикаго как пунктом отправления. К сожалению, нет маршрута из Чикаго в Калгари, и далее следует несколько неудачных попыток найти маршрут. В конце концов, после нескольких рекурсивных вызовов функции findrouteo и немаловажного возврата обнаруживается рейс между Нью-Йорком и Торонто, а из Торонто есть рейс в Калгари. Эта находка вызывает завершение функции findrouteO, последовательное завершение всех ее Рекурсивных вызовов. В заключение первоначально вызванная функция f indroute () также возвращается в вызывающую программу. Вы можете д0. бавить операторы cout в функцию findrouteo, чтобы увидеть, как она обрабатывает разные пункты отправления и назначения. Важно понять, что функция findrouteo не возвращает решение, а формирует его. После выхода из функции findroute () в стеке возврата, в переменной btstack, содержится маршрут из пункта отправления в пункт назначения. Более того, успешна или неудачна работа функции findrouteo, определяется состоянием стека. Пустой стек означает неудачу, в противном случае он содержит решение.
Как правило, возможность возврата или отката (бектрекинг) — ключевая составляющая поисковых систем с использованием методов искусственного интеллекта. В классе search откат выполняется благодаря применению рекурсии и стека возврата (вот почему язык С++, поддерживающий рекурсию и использующий библиотеку STL, — хороший выбор для разработчика систем искусственного интеллекта). Почти все ситуации отката обрабатываются подобно стеку: первым пришел, последним вышел. В процессе поиска пути впервые встреченные узлы помещаются в стек. При попадании в тупик из стека удаляется последний помещенный в него узел, и с этой точки начинается новый поиск пути. Процесс продолжается до достижения цели или исчерпания всех возможных путей.
|
