Динамическое программирование. Динамическое программирование. Кратчайшие пути на ориентированном графе.

30. (1 условная задача) Рассчитать методом динамического программирования (решения полученные другими способами не принимаются) кратчайший путь по системе дорог.

Найти кратчайший путь из SдоT.

На каждом шаге в очередном слое расставляются наименьшие возможные расстояния до Т на основе длин путей до предыдущего слоя (указаны возле стрелок) и ранее вычисленных расстояний предыдущего слоя. Результаты вычислений должны быть записаны рядом с вершинами, в противном случае в процессе проверки не возможно установить факт использования алгоритма. Кроме того, напротив каждой вершины одна из исходящих стрелок должна быть помечена как решение оптимизационной задачи поиска кратчайшего пути в этой вершине. Это даст возможность восстановить оптимальный путь.

Алгоритм решения:

1. В концевой вершине (в нашем случае это Т) ставится метка Z=0/галочка не ставится (в общем случае терминальные вершины образуют - некое множество, в непрерывном случае говорят о границе, которую требуется достичь).

2. В вершинах опирающихся на концевую (на терминальную поверхность), т.е. в вершинах первого слоя можно рассчитать целевые функции.

3. Общее правило целевые функции рассчитывать в тех вершинах, которые опираются только на уже рассчитанные вершины (и не опираются ни на одну нерассчитанную).

4. Расчет в каждом случае происходит как прибавление к большой накопленной сумме записанной в вершине, на которую опирается данная и расстояния до неё. Среди всех таких сумм берётся минимум, на соответствующем направлении ставится галочка. Против рассчитываемой вершины ставится оптимальное значение Z=…

5. Расчёт длится до тех пор, пока не достигнем стартовую вершину S. Перед этим обязаны рассчитать все остальные вершины, т.к. стартовая вершинаSпрямо или опосредованно опирается на все следующие за ней вершины.