![]() Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать неотразимый комплимент
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
![]() Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
![]() |
Метод Форда - Беллмана
Данный метод обеспечивает нахождение кратчайших путей m[s, xi] между источником s и всеми другими вершинами xi Î X \ s для ориентированного графа G = (X, U), в котором отсутствуют контуры суммарной отрицательной длины. Веса дуг l(xi, xj) могут иметь любые значения. Метод является итерационным и основан на изменении пометок вершин графа, причем значения Ниже приводится формальная схема алгоритма, реализующая метод Форда - Беллмана.
Алгоритм 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. Определить множество вершин Шаг 2 (обновление пометок вершин) Для каждой вершины xj ÎГ(S) изменить пометку:
где Пометки вершин xj Ï Г(S) не изменять и присвоить
Шаг 3 (проверка условий окончания) а) Если k £ n - 1 и б) Если k < n - 1 и в) Если k = n - 1 и Шаг 4 (подготовка к следующей итерации) Определить множество S следующим образом:
Изменить номер итерации k = k + 1 и выполнить переход к шагу 2.
Следует отметить, что на шаге 2 множество S содержит все вершины xi графа, для которых кратчайшие пути m[s, xi] состоят из k дуг. Множество Tj определяет вершины из множества S, связанные дугами с xj. Если Представленный алгоритм обеспечивает получение оптимального решения. Доказательство приводится в работах [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,
Рис. 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)
1.21. Решить задачу из примера 1.1 по алгоритму, полученному при выполнении упражнения 1.20. 1.22. Составить программы поиска кратчайших путей по методу Форда - Беллмана для двух способов построения путей (см. раздел 1.2).
Рис. 1.3. Результаты поиска путей (пример 1.1) 1.23. Получить (машинное) решение задачи вычисления длин кратчайших путей m[x1, xj], Ответ: вектор значений l*(xi), (0, -3, -11, -5, 2, -7, -1, 13, 16).
Рис. 1.4. Представление графа для упражнения 1.23 Date: 2015-10-21; view: 3765; Нарушение авторских прав |