Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Метод Форда - Беллмана





 

Данный метод обеспечивает нахождение кратчайших путей m[s, xi] между источником s и всеми другими вершинами xi Î X \ s для ориентированного графа G = (X, U), в котором отсутствуют контуры суммарной отрицательной длины. Веса дуг l(xi, xj) могут иметь любые значения. Метод является итерационным и основан на изменении пометок вершин графа, причем значения (xi) в конце k-й итерации равны длинам таких кратчайших путей m[s, xj], которые содержат не более k + 1 дуг.

Ниже приводится формальная схема алгоритма, реализующая метод Форда - Беллмана.

 

Алгоритм 1.1 (метод Форда - Беллмана)

 

Данные: орграф G = (X, U), имеющий n вершин, с выделенным иcточником s Î X; веса дуг l(xi, xj) для всех (xi, xj) Î U.

Результаты: длины l*(xi) кратчайших путей m[s, xi] для всех xi Î X \ s.

Шаг 1 (присвоение начальных значений)

Установить номер итерации k = 0. Определить множество вершин
S = Г(s). Присвоить начальные значения пометкам:

Шаг 2 (обновление пометок вершин)

Для каждой вершины xj ÎГ(S) изменить пометку:

,

где .

Пометки вершин xj Ï Г(S) не изменять и присвоить

.

Шаг 3 (проверка условий окончания)

а) Если k £ n - 1 и для всех xi Î X, то получен оптимальный результат , i = . Конец алгоритма.

б) Если k < n - 1 и хотя бы для одной вершины
xi Î X, то выполнить переход к шагу 4.

в) Если k = n - 1 и для некоторой xi Î X, то в графе G существует цикл суммарной отрицательной длины и задача не имеет решения. Конец алгоритма.

Шаг 4 (подготовка к следующей итерации)

Определить множество S следующим образом:

.

Изменить номер итерации k = k + 1 и выполнить переход к шагу 2.

 

Следует отметить, что на шаге 2 множество S содержит все вершины xi графа, для которых кратчайшие пути m[s, xi] состоят из k дуг. Множество Tj определяет вершины из множества S, связанные дугами с xj. Если
xj Ï Г(S), то кратчайший путь из s в xj не может состоять из k + 1 дуг и поэтому пометки таких вершин l(xj) изменять не требуется. На шаге 4 новое множество S содержит все вершины, кратчайшие пути до которых содержат k + 1 дуг.



Представленный алгоритм обеспечивает получение оптимального решения. Доказательство приводится в работах [6, 10] и базируется на принципах динамического программирования и том факте, что если не существует никакого оптимального пути из k дуг, то не может также существовать никакого оптимального пути, содержащего k + 1 дуг.

Вычислительная сложность метода Форда - Беллмана имеет оценку О(n3), т. е. в случае полного связного графа с n вершинами требуется порядка n3 операций сложения и сравнения. Алгоритм 1.1 можно использовать и в случае неотрицательных весов дуг, но более предпочтительным является применение алгоритма Дейкстры, так как его оценка трудоемкости составляет О(n2) операций.

Пример 1.1. Применение метода Форда - Беллмана для графа G = (X, U), приведенного на рис. 1.2 и заданного матрицей D (см. упражнение 1.12), показано в табл. 1.2. Предполагается, что источником s является вершина x1. Окончательные значения пометок l*(xi) равны 0, 1, 4, 3, -1 для вершин xi, , соответственно. Кратчайшие пути m[s, xi], где s = x1 и , получены с использованием соотношения (1.2). Результаты решения задачи, включая дерево кратчайших путей, представлены на рис. 1.3.

 

Рис. 1.2. Представление графа для примера 1.1

 

 

У П Р А Ж Н Е Н И Я

 

1.15. Определить особенности графовых моделей, для которых может применяться метод Форда - Беллмана.

1.16. Какое наибольшее число итераций может потребоваться при работе алгоритма 1.1? Изменится ли это значение, если веса всех дуг графа будут неотрицательными?

1.17. Решить задачу построения кратчайших путей m[x2, x5] и m[x5, x2] для графа, показанного на рис. 1.2.

1.18. Разработать подпрограммы формирования множеств S, Г(S) и Tj для xjÎ Г(S).

1.19. Разработать подпрограммы вычисления меток вершин и проверки условий окончания итерационного процесса для метода Форда -Беллмана.

1.20. Модифицировать алгоритм 1.1 таким образом, чтобы для построения кратчайших путей использовать пометки вида [l*(xj), mj], описанные в предыдущем разделе.

Таблица 1.2

Результаты работы алгоритма Форда - Беллмана (пример 1.1)

Итерация Множество S Множество Г(S) Вершина Множество Ti Пометка l(xi)
k = 0 {x2, x5}   s = x1 x2 x3 x4 x5     ¥ ¥
k = 1 {x2, x5} {x2, x3, x4, x5} x1 x2 x3 x4 x5   {x5} {x2} {x2 ,x5} {x2} min(1, 3+8) = 1 min(¥, 1+3) = 4 min(¥, 1+3, 3+4) = 4 min(3, 1+8) = 3
k = 2 {x3, x4} {x3, x4, x5} x1 x2 x3 x4 x5     {x4} {x3} {x3} min(4, 4+2) = 4 min(4, 4+1) = 4 min(3, 4-5) = -1
k = 3 {x5} {x2, x4} x1 x2 x3 x4 x5   {x5}   {x5} min(1, -1+8) = 1 min(4, -1+4) = 3 -1
k = 4 {x4} {x3} x1 x2 x3 x4 x5     {x4} min(4, 3+2) = 4 -1

 



1.21. Решить задачу из примера 1.1 по алгоритму, полученному при выполнении упражнения 1.20.

1.22. Составить программы поиска кратчайших путей по методу Форда - Беллмана для двух способов построения путей (см. раздел 1.2).

 

Рис. 1.3. Результаты поиска путей (пример 1.1)

1.23. Получить (машинное) решение задачи вычисления длин кратчайших путей m[x1, xj], , для графа, показанного на рис. 1.4.

Ответ: вектор значений l*(xi), , имеет следующий вид:

(0, -3, -11, -5, 2, -7, -1, 13, 16).

Рис. 1.4. Представление графа для упражнения 1.23






Date: 2015-10-21; view: 2108; Нарушение авторских прав

mydocx.ru - 2015-2019 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию