16.4. Решение задачи о кратчайшем пути методами динамического программирования.

Задача 2. На данной сети дорог (рис. 6) указаны расстояния из пункта в пункт. Найти кратчайший маршрут перевозки груза пункта 1 в пункт 10.

¦ Разобьем все пункты сети на группы (состояния, табл. 1). К группе 0 отнесем пункт 1, к группе 1 пункты, в которые можно попасть непосред-ственно из пункта 1 (таковыми будут 2 и 3), к группе 2 отне-сем пункты, в которые можно попасть непосредственно из
	Рис. 6

любого пункта группы 1 (таковыми будут 4, 5 и 6), и т.д. В результате движение транспорта с грузом из пункта 1 в пункт 10 можно рассматривать как четырехшаговый процесс: на первом шаге транспорт перемещается из пункта 1 в какой-то пункт группы 1, на втором шаге –

системы выступает транспорт с грузом, перемещающийся из начального пункта с1 в конечный пункт с10, и сеть дорог. За состояние si-1 системы перед i-м шагом естественно принять местонахождение транспорта с грузом в одном из пунктов, в котором он побывает перед этим шагом:

s0={с1}, s1={с2; с3}, s2={с4; с5; с6}, s3={с7; с8; с9}, s4={с10}.

Управление и на i-м шаге состоит в выборе дороги (i, j), по которой следует направлять груз из данного пункта в соседний в общем направлении к пункту 10. Состояние в конце шага определяется номером пункта, в который будет доставлен груз в результате сделанного выбора (принятого управления), а значение целевой функции на i-м шаге – это кратчайшее расстояние из данного пункта в выбранный соседний пункт.

В соответствии с вычислительной схемой метода динамического программирования фактическое формирование искомого оптимального управления данным процессом состоит из двух процедур: условной оптимизации и безусловной оптимизации. Условная оптимизация осуществляется в результате попятного движения от последнего шага исследуемого явления к его первому шагу; в процессе этого движения находятся шаговые условно-оптимальные управления. Безусловная оптимизация осуществляется в процессе движения в прямом направлении от первого шага к последнему; при этом из найденных ранее шаговых условно-оптимальных управлений формируется безусловное оптимальное управление всем данным процессом.

Рекуррентное уравнение для алгоритма обратной прогонки имеет вид

(si-1)={d(si-1, si)+(si)}, i=1,2,3,4,    (19)

где d(si-1, si) – расстояние от пункта si-1 до пункта si. При этом (s4)=0.

IV шаг. Условную оптимизацию начнем с анализа четвертого шага. Состояние, в которых транспорт с грузом может оказаться перед четвертым шагом, зависит от управлений на предшествующих шагах и соответствует его местонахождению либо в пункте 7, либо в пункте 8, либо в пункте 9. Это будет состояние s3. Из каждого указанного пункта можно перейти в конечный пункт с10 единственным путем: из пункта 7 в пункт 10 груз может быть доставлен только дорогой (7, 10), из 8 в 10 – дорогой (8, 10), из 9 в 10 – дорогой (9,10).

Условно-оптимальные затраты на этом шаге в общем случае выражаются основным функциональным уравнением:

(s3)=d(s3, s4),

где d(s3, s4) – расстояние от одного из пунктов s3 до пункта s4. Соответствующей последовательностью вычислений будет >>>.

Так как пункт 10 (s4={с10}) связан с пунктами 7, 8 и 9 (s3={с7; с8; с9}) в точности одним маршрутом, альтернативы для выбора отсутствуют, и результаты IV шага можно оформить в виде табл. 2.

                                       Таблица 2

III шаг. Переходя к третьему этапу условной оптимизации, запишем функциональное уравнение для этого шага, которое получится из равенства (19) при i=3:

(s2)={d(s2, s3)+(s3)}.         (20)

Из рис.

                                                                        Таблица 3

Оптимальное решение III шага означает следующее. Если вы находитесь в пункте с4 или с5, кратчайший путь к пункту с10 проходит через пункт с7, а если находитесь в пункте с6, кратчайший путь к пункту с10 проходит через пункт с8.

II шаг. Используя значения (s2), полученные на III шаге, можно сравнить допустимые альтернативные решения, как показано в табл. 4.

                                                                        Табл. 4.

I шаг. Заключительным этапом процедуры условной оптимизации является анализ первого шага. Особенность этого шага состоит в том, что в его начале состояние с1 системы определено однозначно: транспорт с грузом находится в пункте 1, так что множество s0 состояний содержит единственный элемент с1, а множество Х1 управлений – два элемента: (1, 2) и (1, 3). Функциональное уравнение для этого шага имеет вид

(s0)={d(s0, s1)+(s1)}.

Результаты вычислений приведены в табл. 5.

                                                                        Табл. 5.

Как видно из табл. 5, условно-оптимальным управлением для этого шага является выбор дороги (1, 3), обеспечивающий кратчайшее расстояние (s0)=15 на всем пути от пункта 1 до пункта 10.Что же касается структуры этого пути (кратчайшего маршрута), то она выяснится в процессе процедуры безусловной оптимизации.

При безусловной оптимизации остается пройти еще раз весь оптимизируемый процесс, но уже в прямом правлении, начиная с первого и кончая четвертого шагом, и «прочитать» искомое оптимальное управление (кратчайший маршрут), которое будет составлено из найденных ранее (при условной оптимизации) шаговых условно-оптимальных управлений (дорог между отдельными пунктами сети). Из табл. 5 видно, что из начального пункта с1 груз следует направлять по дороге (1, 3), ибо именно этому условно-оптимальному управлению соответствует минимальное расстояние (см. последний столбец табл. 5). В результате груз окажется в пункте с3. Переходя к табл. 4 замечаем, что из пункта 3 груз необходимо доставлять дорогой (3, 5) в пункт с5 (см. последний столбец табл. 4). Из табл. 3 видно, что далее груз должен перевозиться по дороге (5, 7) до пункта с7, откуда, как это следует из табл. 2, он направляется дорогой (7, 10) в конечный пункт с10. Таким образом, кратчайший маршрут пролегает через пункты 1, 3, 5, 7 и 10, при этом пройденный путь минимизируется и составляют 15 ед.                                                                                           ?

Замечание 1. При использовании метода динамического программирования часто получаются побочные результаты, связанные с рассматриваемой задачей и нередко имеющие не менее важное значение. В данном случае кроме оптимального маршрута доставки груза из пункта 1 в пункт 10 информация, содержащаяся в табл. 2 – 5, позволяет находить кратчайший маршрут в пункт 10 из любого другого пункта данной сети дорог. Находятся эти маршруты так же, как и сформированный выше маршрут 1—3—5—7—10. Так, например, оптимальный маршрут из пункта 2 в пункт 10 пройдет через пункты 5 и 7.

Замечание 2. В рассматриваемом примере проиллюстрирована одна из главных особенностей метода динамического программирования: при выборе решения на каждом шаге необходимо руководствоваться интересами всего оптимизируемого процесса, а не только данного шага. Именно этим объясняется включение в наиболее экономичный маршрут дороги (1,3), длина которой в 2 раза больше, чем дороги (1, 2). Эта «жертва» на первом шаге принесена с тем, чтобы минимизировать общий путь на всем четырехшаговом маршруте.