Задача динамического программирования

Из узла (3,3) г. Глазово можно продолжить дорогу к пункту В либо через (3,4) г. Калугу, либо через (4,3) г. Тулу.

Путь из г. Глазово в г. Самару через г. Калугу складывается из суммы работ:

Путь из г. Глазово в г. Самару через г. Тулу складывается из суммы работ: Цафт отзывы СОТРУДНИКОВ узнать больше.

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Тулу

Из узла (4,2) г. Рославля можно продолжить дорогу к пункту В либо через (4,3) г. Тулу, либо через (5,2) г. Брянск.

Путь из г. Рославля в г. Самару через г. Тулу складывается из суммы работ:

Путь из г. Рославля в г. Самару через г. Брянск складывается из суммы работ:

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Брянск

Из узла (5,1) г. Могилева можно продолжить дорогу к пункту В либо через (5,2) г. Брянск, либо через (6,1) г. Гомель.

Путь из г. Могилева в г. Самару через г. Брянск складывается из суммы работ:

Путь из г. Могилева в г. Самару через г. Гомель складывается из суммы работ:

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Брянск

При выборе оптимального маршрута достаточно знаний прокладывания маршрута в пункт В из (1,5), (2,4), (3,3), (4,2) и (5,1).

Найдем минимальное значение функции цели (оптимальный маршрут) при i=4, используя основное функциональное уравнение Беллмана (3.1):

Рисунок 3.7 - Сетевая модель шага 6

Шаг 7

В вектор состояния входят 4 узла:

Узел (1,4) - г. Кострома, (2,3) - г. Вязьма, (3,2) - г. Ярцево, (4,1) - г. Орша Для г. Костромы, г. Вязьмы, г. Ярцево, г. Орша следует рассмотреть по 2 варианта маршрута.

Из узла (1,4) г. Костромы можно проложить дорогу к пункту В либо через (1,5) г. Иваново, либо через (2,4) г. Москву.

Путь из г. Костромы в г. Самару через г. Иваново складывается из суммы работ:

Путь из г. Костромы в г. Самару через г. Москву складывается из суммы работ:

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Иваново

Из узла (2,3) г. Вязьмы можно продолжить дорогу к пункту В либо через (2,4) г. Москву, либо через (3,3) г. Глазово.

Путь из г. Вязьмы в г. Самару через г. Москву складывается из суммы работ:

Путь из г. Вязьмы в г. Самару через г. Глазово складывается из суммы работ:

Сравниваем два значения и выбираем наименьшее значение. В данном случае выбираем маршрут, проходящий через г. Глазово

Из узла (3,2) г. Ярцево можно продолжить дорогу к пункту В либо через (3,3) г. Глазово, либо через (4,2) г. Рославль.

Путь из г. Ярцево в г. Самару через г. Глазово складывается из суммы работ:

Перейти на страницу: 1 2 3 4 5 6 7 8 9 10 11