ДП предлагает конструировать оптимальный путь по частям - представить задачу как многошаговую. Разместим условно все входы на одной вертикальной прямой, все узлы, которые встречаются первыми на пути от входов к выходам, - на другой прямой. Также поступим со второй и другими группами узлов и, наконец, с выходами. Получим схему лабиринта.
Построение оптимального пути можно начинать с 1-го или 4-го шага, но предпочтительнее с 4-го - обратная прогонка. Будем искать оптимальное решение для каждого из узлов, в котором можем оказаться перед 4-м шагом (это узлы 8,9 и 10). Фиксируем узел 8 и из четырех значений времени перехода из него к выходам выбираем наименьшее. Соответствующий переход может принадлежать оптимальному пути. Узлу 8 приписываем этот переход и найденное минимальное время, которое обозначим как t 8. Аналогично поступаем, фиксируя узел 9, а затем 10. В результате получим t 9 и t 10 соответственно и переходы, на которых достигаются эти минимальные значения времени. Тем самым завершается первый этап построения оптимального пути.
Теперь полагаем, что осталось совершить 3-й и 4-й переходы. Фиксируем узел 4 и определяем минимальный путь из него к выходам. Достаточно сравнить только три: 1)время на переходе 4-8 плюс t 8; 2)время на переходе 4-9 плюс t 9; 3)время на переходе 4-10 плюс t 10. Минимальное значение приписываем узлу 4 (t 4) и выделяем жирной линией соответствующий переход на третьем шаге. Принципиальная особенность ДП: оптимальный переход на шаге 3 определялся не как самый короткий среди переходов этого шага, а как такой, который обеспечивает минимум времени от данного узла к выходу. Точно так же находим решения для узлов 5, 6 и 7. Опираясь на них, можно переходить к третьему этапу построения оптимального пути, охватывающему 2, 3 и 4-й шаги. Рассуждения аналогичны вышеприведенным. Последний, четвертый, этап охватывает все шаги. Найдя решение для 1-го шага, мы тем самым завершаем построение оптимальных путей. Двигаясь по полученному решению от входа к выходу, то есть в прямом направлении, последовательно находим переходы, составляющие оптимальный путь.
