Введение в функцию стоимости
Теперь, когда мы создали модель направленного графа для перемещения через пространство, пришло время для моделирования 'стоимости' перемещения сквозь пространство. На стоимость может влиять много различных вещей в зависимости от того, хотим ли мы найти самый короткий путь; самый быстрый путь, или путь с наименьшим риском быть обнаруженным врагами, и так далее.
Мы будем решать задачу поиска самых быстрых и наименее опасных путей. Адаптации под другие варианты должны быть очевидны.При использовании нашего алгоритма поиска пути, мы должны трактовать местность на карте двойственно (свободно или занято). Мы можем перемещаться с различными скоростями по различным типам местности. Например, воду, болота и горы трудно или невозможно пройти (то есть это препятствия, которые надо обойти) в то время как поля и пустыни проходимы, а дороги намного быстрее. При отсутствии врагов (иначе их надо обходить) мы таким образом хотим найти самый быстрый возможный путь через эту местность.
Чтобы сделать это, значение 'стоимости' назначено на каждую грань. Эти значения могут быть получены через функцию определенную на множестве всех граней, и термин 'функция стоимости ' используется. Путь - это множество 'связанных' граней, между вершинами источника и адресата. Стоимость пути - сумма издержек всех граней в пути. Допустимый путь - путь с определенной суммой стоимости.
Давайте примем стоимость грани равной времени, за которое наше транспортное средство пересекает грань. Таким образом, основная единица функции стоимости - это 'время нахождения в пути'. Другими словами, ясно что проблема нахождения оптимального пути между двумя вершинами, в смысле минимизация стоимости пути, эквивалентна проблеме нахождения самого быстрого пути. Проблема о самом коротком пути частный случай проблемы самого быстрого пути, где все возможные типы местности имеют то же самую скорость для транспортного средства.
Как будет отмечено в разделе 4, будет выгодно установить условие, что все грани стоят больше, чем ноль. Это также физически оправдано для наземных транспортных средств - перемещение всегда имеет стоимость.
Но как можем мы смоделировать воздействие всех различных параметров, которые мы хотим учесть во время перемещения по грани от одной вершины до другой? И как можем мы смоделировать такие ограничения как враги, препятствия и другие факторы, которые не могут быть явно выражены как время нахождения в пути? 'Основная стоимость грани' основанная на типе местности будет задана, и различные 'модификаторы' будут затем использоваться, чтобы все 'ограничения' принять во внимание. Модификатор определен как функция, которая некоторым способом изменяет основную стоимость грани.
После определения функции стоимости и различных модификаторов, мы завершим упрощение задачи на взвешенном графе. Затем остается 'только' фактически найти оптимальный путь в разделе 4. 5.1.2.1