|
Рисунок 3.4 - Сетевая модель шага 3
Шаг 4
В вектор состояния входят 5 узлов:
Узел (2,6) - г. Казань, (3,5) - г. Саранск, (4,4) - г. Липецк, (5,3) - г. Курск, (6,2) - г. Белгород
Из узлов (2,6) и (6,2) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
Стоимость прокладки дороги из г. Казани и г. Белгорода в конечный пункт г. Самару равна:
А для г. Саранска, г. Липецка и г. Курска следует рассмотреть по 2 варианта маршрута.
Из узла (3,5) г. Саранска можно продолжить дорогу к пункту В либо через (3,6) г. Уфу, либо через (4,5) г. Пензу.
Путь из г. Саранска в г. Самару через г. Уфу складывается из суммы работ:
Путь из г. Саранска в г. Самару через г. Пензу складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Пензу
Из узла (4,4) г. Липецка можно продолжить дорогу к пункту В либо через (4,5) г. Пензу, либо через (5,4) г. Тамбов.
Путь из г. Липецка в г. Самару через г. Пензу складывается из суммы работ:
Путь из г. Липецка в г. Самару через г. Тамбов складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Пензу
Из узла (5,3) г. Курска можно продолжить дорогу к пункту В либо через (5,4) г. Тамбов, либо через (6,3) г. Воронеж.
Путь из г. Курска в г. Самару через г. Тамбов складывается из суммы работ:
Путь из г. Курска в г. Самару через г. Воронеж складывается из суммы работ:
Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Тамбов
При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (2,6), (3,5), (4,4), (5,3) и (6,2).
Найдем минимальное значение функции цели (оптимальный маршрут) при i=6, используя основное функциональное уравнение Беллмана (3.1):
Рисунок 3.5 - Сетевая модель шага 4
Шаг 5
В вектор состояния входят 6 узлов:
Узел (1,6) - г. Киров, (2,5) - г. Владимир, (3,4) - г. Калуга, (4,3) - г. Тула, (5,2) - г. Брянск, (6,1) - г. Гомель.
Из узлов (1,6) и (6,1) путь в смежные с ними узлы однозначен. Обходной путь существует, но он не оптимален.
А для г. Владимира, г. Калуги, г. Тулы, г. Брянска следует рассмотреть по 2 варианта маршрута.
Из узла (2,5) г. Владимира можно продолжить дорогу к пункту В либо через (2,6) г. Казань, либо через (3,5) г. Саранск.
Путь из г. Владимира в г. Самару через г. Казань складывается из суммы работ:
Путь из г. Владимира в г. Самару через г. Саранск складывается из суммы работ:
|
