Условие задачи
Выбор оптимального пути в транспортной сети
В транспортной сети (рис. 2) имеется несколько маршрутов по проезду из начального пункта 1 в конечный пункт 11. Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице. Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.
Рис. 2. Транспортная сеть
Исходные данные:
Ответ
Уравнение Беллмана.
Fк(S) = min(tsj + Fk-1(j))
S пункт отправления, j - пункт назначения, tsj стоимость проезда отправления в пункт назначения.
Функция Беллмана минимально возможные затраты по перемещению из 1-го в 11-й пункт. Задачу начинаем решать с конца.
1 шаг. F1( S ) = ts11
Из пункта 11 можно попасть в пункты 8, 9, 10 при этом расстояния до этих пунктов 7, 6, 10 берутся из рис.1, третий столбец табл. 1 определяется по формуле на 1-м шаге, а j * - в каком пункте достигается минимальное значение.
Таблица 1
