282 [лава у

Анализ поиска методом наименьшей стоимости

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

Получение множественных решений

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

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

Удаление пути

Метод удаления пути (path removal) при генерации множественных решений удаляет из базы данных все узлы, сформировавшие текущее решение, и затем пытается найти другое. По существу, он обрезает ветви дерева. Для поиска множественных решений с помошью удаления пути нужно заменить функцию main о версией, приведенной в листинге 7.4.

Листинг 7.4. Функция inain() для получения множественных решений с помощью удаления пути

int main О {

char to[40], from[40]; Search ob;

Добавляет рейсы в базу данных. ob.addflightCNew York , Chicago , 900) ob.addflight( Chicago . Denver . 1000); ob.addflight( New York , IToronto , 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 , 1500J; ob.addflight( Denver , Los Angeles , 1000);

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

cin.getline(frQm, 40); cout To? ;

cin.getline(to, 40);

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

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

ob.findroute(from, to);

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

ob.routeO;

return 0;

В листинге 7.4 добавлен цикл for, повторяющийся, пока не пуст стек возврата. Напоминаю, что если стек пуст, не найдено никакого (в данном случае ни одного дополнительного) рещения. Больше никаких изменений не требуется, так как у любого рейса, включенного в решение, будет помечено Поле skip. Следовательно, функция find о больше не найдет этот рейс, и он не станет частью следующего решения, т. е. он не может быть найден Повторно.

ли вы используете класс search для поиска в глубину (листинг 7.1) и Приведенную в листинге 7.4 функцию main (), будут получены следующие Решения: от? New york ? Los Angeles

284 Гоава

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

New York to Toronto to Los Angeles Distance is 3000

New York to Denver to Houston to Los Angeles Distance is 4300

Профамма нашла фи решения. Но обратите внимание на то, что среди них нет лучшего решения.

Удаление узла

другой путь генерации множественных решений - метод удаления узла (node removal) - просто удаляет последний узел из текушего решения и пытается снова найти решение. Для этого в функцию main () внесены изменения, позволяющие удалить последний рейс текушего решения из базы данных, очищать все поля skip и получать новый пустой стек, использующийся для хранения следующего решения. Новая версия функции main о приведена в листинге 7.5.

Листинг 7.5. Функция inain() для получения множественных решений с помощью удаления узла

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

char to[40], from[40];

Search ob;

Flightlnfo f;

Добавляет рейсы в базу данных, ob.addflight( New York , Chicago , 900); ob.addflight( 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.addf1ight( Denver , Urbana , 1000); ob.addflight( Denver , Houston , 1000); ob.addf1ight( Houston , Los Angeles , 1500); ob.addflight( Denver , Los Angeles , 1000);