Графовые модели. Методы поиска кратчайших путей

Следует особо отметить, что выбор оптимального решения на определенном шаге не дает гарантии получения оптимального решения для задачи в целом. Иными словами, для получения оптимального решения для всей задачи приходится иногда выбирать не лучшее решение на определенном шаге. На текущем шаге выбирается не лучшее решение, а то, которое предусматривает максимальную сумму выигрыша от всех оставшихся шагов.
При учете вышесказанного выполнять вычисления в задачах динамического программирования более удобно от конца к началу. Действительно можно легко планировать последний, m-1. Выполняя вычисления по последнему шагу, надо сделать ряд предположений: как закончился предыдущий, m-1, шаг и для каждого предположения найти условно-оптимальное решение на m-м шаге. Аналогичным образом выполняются m-1, m-2 и т.д. шаги, вплоть до первого шага. Таким образом, будут найдены условно-оптимальные решения на каждом шаге. Затем выполняется переход от условно-оптимального решения к безусловно-оптимальному решению на каждом шаге, иными словами, выполняются решения о первого шага к последнему, ориентируясь на полученные условно-оптимальные решения. Теперь на первом шаге известна «стоимость» решения задачи от второго шага до последнего шага и, соответственно, можно указать оптимальное решение на первом шаге (снизить «стоимость» первого шага). Затем выполняются аналогичным образом второй, третий и т.д. шаги.
При применении динамического программирования многошаговая задача решается два раза: от конца к началу (определение условно-оптимального решения) и от начала к концу (определение безусловно-оптимального решения). Первый этап трудоемкий и длительный, второй - короткий и уточняет решение первого этапа (по готовым рекомендациям определяется безусловно-оптимальное решение на каждом шаге). 
Алгоритм Форда-Беллмана обладает более универсальным характером и может применяться для графовой модели любого вида. Но применение его является наиболее целесообразным для графов, в которых существуют контуры положительной длины и веса дуг обладают произвольными значениями. Если все дуги имеют неотрицательные значения, то с точки зрения вычислительной сложности более эффективным является алгоритм Дейкстры. Для бесконтурных графов наиболее быстро работает алгоритм, основывающийся на идее динамического программирования и реализованный в методах PERT (Project Evaluation Research Task) и CPM (Critical Path Method). В отечественной литературе наряду с указанными обозначениями применяются соответственно термины СПУ (сетевое планирование и управление) и МКП (метод критического пути).
Непосредственными обобщениями вышепредставленной задачи о кратчайшем пути являются две следующие задачи.
Задача А. Для заданной начальной вершины s ( X найти кратчайшие пути ([s, xi] между s и всеми другими вершинами xi ( X \ s.
Задача В. Определить кратчайшие пути ([y, z] между всеми парами вершин y, z ( X.
Почти все методы, дающие возможность решить задачу о кратчайшем пути ([s, t], также обеспечивают и получение всех кратчайших путей от s к любой вершине xi ( X \ s с небольшими дополнительными вычислительными затратами. Задача В может быть решена либо n-кратным применением алгоритмов для задачи А, при этом на каждом шаге в качестве s выбираются разные вершины y ( X, или однократным применением специального алгоритма (к примеру, алгоритма Флойда, обеспечивающего решение задачи В для графов с контурами положительной длины при произвольных весах дуг).
Необходимо сказать, что все перечисленные алгоритмы и методы предназначаются для поиска путей в ориентированных графах. Но, если исходный граф G содержит неориентированные ребра, то для поиска кратчайшего пути может быть рассмотрен новый граф G(, каждое ребро в котором [xi, xj] с весом lij заменяется парой направленных противоположно дуг (xi, xj) и (xj, xi) с весами l(xi, xj) = l(xj, xi) = lij соответственно.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Введение в математическое моделирование. - М.: Логос, 2014. - 397 c.
Голубева, Н.В. Математическое моделирование систем и процессов: Учебное пособие / Н.В. Голубева. - СПб.: Лань, 2013. - 192 c.
Горлач, Б. А. Математическое моделирование. Построение моделей и численная реализация / Б.А. Горлач, В.Г. Шахов. - М.: Лань, 2016. - 292 c.
Зайдель, А.Н. Математическое моделирование. Построение моделей и численная реализация: Учебное пособие / А.Н. Зайдель. - СПб.: Лань, 2016. - 304 c.
Рейзлин, В.И. Математическое моделирование: Учебное пособие для магистратуры / В.И. Рейзлин. - Люберцы: Юрайт, 2016. - 126 c.
Голубева, Н.В. Математическое моделирование систем и процессов: Учебное пособие / Н.В. Голубева. - СПб.: Лань, 2013. – С. 48.
Рейзлин, В.И. Математическое моделирование: Учебное пособие для магистратуры / В.И. Рейзлин. - Люберцы: Юрайт, 2016. – С. 86.
Зайдель, А.Н. Математическое моделирование. Построение моделей и численная реализация: Учебное пособие / А.Н. Зайдель. - СПб.: Лань, 2016. – С. 105.
Введение в математическое моделирование. - М.: Логос, 2014. – С. 195.
Рейзлин, В.И. Математическое моделирование: Учебное пособие для магистратуры / В.И. Рейзлин. - Люберцы: Юрайт, 2016. – С. 88.
Горлач, Б. А. Математическое моделирование. Построение моделей и численная реализация / Б.А. Горлач, В.Г. Шахов. - М.: Лань, 2016. – С. 95.
Введение в математическое моделирование. - М.: Логос, 2014. – С. 196.









2





1