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

Метод наименьшей стоимости (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.size(); 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 •Го? Los Angeles щей York to Toronto to Los Angeles Distance is 3000 Как видите, найден хороший маршрут — не лучший, но приемлемый. На рис. 7.11 показан найденный методом наименьшей стоимости путь, ведущий к цели.