Контрольная работа по дисциплине "Программирование"

                    = min(8+33 /2345; 13+26 /3452; 11+26 /4523; 19+20 /5234)=37 /64523;

В(3,{2,4,5,6})=min [s32+B(2,{4,5,6}); s34+B(4,{2,5,6}); s35+B(5,{2,4,6});s36+B(6,{2,4,5})] =

                    = min(7+40 /2645; 8+31 /4526; ∞+27 /5264; 12+29 /6452)=39 /34526;

В(2,{3,4,5,6})=min [s23+B(3,{4,5,6}); s24+B(4,{3,5,6}); s25+B(5,{3,4,6});s26+B(6,{3,4,5})] =

               =min(5+43/(3456 или 3645);12+43 /4536;19+39/5364; 9+41/(6345 или 6453))=48/(23456 или 23645);

Итак, все шаги метода динамического программирования выполнены: оптимальное значение критерия равно 37.

Оптимальный маршрут следующий:

1 ®® 6 ®® 5 ®® 2 ®® 3®® 1.

Длина маршрута: 37+s31=37+15=52

Ответ: 1 → 6 → 5 → 2 → 3→ 1,  S=52