Табличный способ решения

Согласно алгоритму метода динамического программирования анализ вариантов начинается с конца процесса. Вначале определим минимальные расстояния от пунктов 10 и 11 до конечного пункта 12 (V этап). Минимальное расстояние определим с помощью расчетных таблиц. Так, из табл. 7.1 следует, что на V этапе никаких комбинаций нет, из пунктов 10 и 11 в пункт 12 имеется только по одному пути, соответственно 12 и 10 км. На IV этапе выбрать самый короткий путь из пунктов 8 и 9 через пункты V этапа в конечный пункт 12.

Возможные варианты представлены в табл. 7.2. Для перемещения из пункта 8 в пункт 10 необходимо пройти 9 км, а из пункта 10 в пункт 12 (см. табл. 7.1) – 12 км, общая длина пути составит 21 км. Если этот путь будет проходить через пункт 11, то его длина составит 16 км. Из двух возможных комбинаций выбираем ту, которая соответствует минимальному расстоянию – 16 км, т. е. путь должен пройти через пункт 11. Аналогично находим расстояние перемещения из пункта 9 IV этапа через пункты V этапа в конечный пункт 12. Рациональным при этом оказался путь через пункт 11длиной 14 км. Это значение проставляем в столбце min L_iv-vi, а клетки таблицы с нерациональными расстояниями зачеркиваем. Таким образом, рассматриваем варианты перемещения из пунктов III этапа в пункт 12 через пункты IV этапа (табл. 7.3), а из пунктов II этапа через пункты III этапа в конечный пункт 12 (табл. 7.4). И наконец, расстояния перемещения из начального пункта 1 через пункты 2,3 и 4 II этапа представлены в табл. 7.5.

Таким образом, следуя от конца маршрута, мы вначале определили, через какой пункт рационально двигаться, чтобы оказаться в пунктах IV этапа, затем III этапа и так до пункта 1. Следовательно, получено условное оптимальное решение задачи. После этого, следуя от начала маршрута к концу, используя данные табл. 7.1-7.5, в которых условные оптимальные решения остались незачеркнутыми, находим, действительно, оптимальное решение. Из табл. 7.5 видно, что необходимо двигаться из пункта 1 в пункт 3. Из табл. 7.4 следует, что

Таблица 7.1