В транспортной сети имеется несколько маршрутов по проезду из начального пункта 1 в конечный пункт 11. Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице. Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.
Разобьем всю транспортную сеть на пояса и отнесем каждый из десяти пунктов к одному из четырех поясов: пункты 8, 9 и 10 принадлежат к первому поясу, 6 и 7 ко второму, 2, 3, 4 и 5 к третьему и 1 к четвертому.
На k-ом шаге будем находить оптимальные маршруты из городов k-го пояса до конечного пункта.
I этап. Условная оптимизация
1-й шаг. k=1. 𝐹1(𝑆) = 𝑡𝑆11.
Не нашел нужную задачу?