и Переустанавливает все поля skip, void Search: rresetAllSkipО {

fordmsigned i=0; i< flights.sizeO; i++) flights[i].skip = false;

Удаляет рейс.

void Search::remove(Flightlnfo f) {

fordmsigned i=0; i< flights.sizeO; i++) if (flights [i] .from == f.fjrom && flights[i].to == f.to) flights[i].from = ;

Версия для удаления узлов, int mainO {

char to[40], from[40];

Search ob;

Flightlnfo f;

Добавляет рейсы в базу данных, ob.addflight( New York , Chicago , 900); ob. addf light ( Chicago , Denver , 1000); ob.addflight( New York , Toronto , 500); ob.addflight( New York . Denver , 1800); ob.addflight( Toronto . Calgary . 1700); ob.addflight( Toronto , Los Angeles , 2500); ob.addflight( Toronto , Chicago , 500); ob.addflight( Denver , Urbana , 1000); ob.addflight( Denver , Houston , 1000); ob.addflight( Houston , Los Angeles , 1500); ob.addflight( Denver , Los Angeles , 1000);

Получает пункты отправления и назначения, cout From? ;

cin.getline(from, 40); cout TO? ;

cin.getline(to, 40);

Находит множественные решения. for(;;) {

Проверяет, есть ли рейс.

ob.findroute(from, to);

Если не найден ни один новый маршрут, завершается, if (! ob. routef ound ()) breaJc;

Сохраняет рейс на вершине стека (on top-of-staclc) . f = ob.getTOSO;

ob.routeO; отображает текущий марщрут.

ob.resetAllSkipO; переустанавливает поля skip

Удаляет из базы данных последний рейс из предыдущего решения. ob.remove(f);

return 0;

Программа находит следующие решения: From? New York То? Los Angeles

New york to Chicago to Denver to Los Angeles Distance is 2900

New York to Chicago to Denver to Houston to Los Angeles Distance is 4400

New York to Toronto to Los Angeles Distance is 3000

В данном случае второе решение - это наихудший из возможных маршрУ тов, но найдены и два достаточно хороших решения. Обратите внимание на то, что множество решений, найденных методом удаления узла, отличается от набора маршрутов, найденных методом удаления пути. Разные подходы генерирующие множественные решения, часто дают различные результаты-

Листинг 7,7. Программа поиска оптимального решения с помощью удаления Л, использующая метод наименьшей стоимости

♦include <iostream> ♦include <staclc> ♦include <string> ♦include <vector>

sing namespace std;

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

Struct Flightlnfo {

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

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

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

Поиск оптимального решения

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

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

В листинге 7.7 приведена программа поиска оптимального решения. В ней создается дополнительный стек, названный optimal, в котором содержится оптимальное решение, и переменная экземпляра minDist, отслеживающая минимальную длину. Внесены изменения в функцию route (), и незначительно модифицирована функция main ().