Денвер Лос-Анджелес Чикаго Калгари Слос-Анджелес)

Решение

Лос-Анджелес Хьюстон Эрбана

(Лос-АнджелесЗ Ложная Вершина

Рис. 7.10. Маршрут, найденный методом восхождения на гору , и ложная вершина

Анализ метода восхождения на гору

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

280 Глава?

Поиск методом наименьшей стоимости

Метод наименьшей стоимости (least-cost search) противоположен методу вос, хождения на гору. Представьте себе, что вы на роликовых коньках стоите на склоне высокого холма на середине улицы и чувствуете со всей определенностью, что спускаться гораздо легче, чем карабкаться вверх. Это и есть стратегия метода наименьшей стоимости. Другими словами, описываемый метод выбирает путь наименьшего сопротивления.

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

const int MAXDIST = 100000;

Версия для метода наименьшей стоимости.

При заданном from находит самый короткий рейс из from.

Возвращает true, если рейс найден,

и false - в противном случае.

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

int pos = -1;

int dist = MAXDIST; длиннее, чем самый длинный рейс

for (unsigned i=0; i < flights.sizeO; i-i-+) (

if(flights[i].from == from && !flights[i].skip) { Использует самый короткий рейс, if(flights[i].distance < dist) { pos = i;

dist = flights[i].distance;

if(pos != -1) { f = flights[pos];

flights[pos].skip = true; предотвращает повторное использование return true;

return false;

Лри использовании приведенной версии функции find о получено следующее рещение. prom? New York ipo? Los Angeles

ffgii York to Toronto to Los Angeles Distance is 3000

Как видите, найден хороший маршрут - не лучший, но приемлемый. На рис. 7.11 показан найденный методом наименьшей стоимости путь, ведущий к цели.

Денвер [Лос-Анджелес Чикаго Калгари Лос-Аиджвлес Первое решение

Хьюстон Эрбана

Лос-Анджелес

Рис. 7.11. Путь, найденный методом наименьшей стоимости