русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритм Форда-Беллмана.


Дата добавления: 2013-12-23; просмотров: 4026; Нарушение авторских прав


Используя утверждение 1, нетрудно описать алгоритм нахождения таблицы значений величин (будем записывать её в виде матрицы, где - номер строки, - номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя из (1), последовательно определяем набор величин (()-й столбец матрицы), начиная с , а затем шаг за шагом увеличиваем значение до любой необходимой величины.

Алгоритм Форда – Беллмана нахождения минимального пути в нагруженном орграфе из в

Шаг 1. Пусть мы уже составили таблицу величин . Если не достижима из (предполагаем, что все величины конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть . Тогда число выражает длинны любого минимального пути из в в нагруженном орграфе . Определим минимальное число , при котором выполняется равенство . По определению чисел получим, что - минимальное число дуг в пути среди всех минимальных путей из в в нагруженном орграфе .

Шаг 3. Последовательно определяем номера такие что

. . . . . . (4)

Из (4) с учётом того, что , имеем , откуда, используя (1), получаем

(5)

Складывая равенства (4) и учитывая (5), имеем

т.е. - искомый минимальный путь из в в нагруженном орграфе . Заметим, что в этом пути ровно дуг Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном орграфе .

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

Замечание. Алгоритм можно модифицировать, с тем чтобы определить минимальный путь из в заданную вершину среди путей из в , содержащих не более дуг, где - заданное число, . Для этого в алгоритме вместо следует воспользоваться .



Пример 83.

Определить минимальный путь из v1 в v6 в нагруженном орграфе D, изображенном на рисунке 35.

Решение.

Составим матрицу C(D) длин дуг нагруженного орграфа D(табл. 68). Справа от матрицы C(D) припишем шесть столбцов, которые будем определять, используя рекуррентное соотношение (2) и исходя из (1).

Величина выражает длину минимального пути из v1 в v6 в нагруженном орграфе D. Найдем минимальное число , при котором выполняется равенство . Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех минимальных путей из v1 в v6 в нагруженном графе D равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5, где i1 = 6, удовлетворяющих (4) (для этого используем формулу (2)).

Таблица 68

  v1 v2 v3 v4 v5 v6  
v1 Ґ Ґ  
v2 Ґ Ґ Ґ Ґ Ґ   Ґ Ґ
v3 Ґ Ґ Ґ Ґ Ґ   Ґ
v4 Ґ Ґ Ґ Ґ Ґ   Ґ
v5 Ґ Ґ Ґ Ґ   Ґ
v6 Ґ Ґ Ґ Ґ Ґ Ґ   Ґ

Получаем, что в качестве такой последовательности надо взять номера 6, 2, 3, 5, 1, так как

Тогда v1v5v3v2v6 – искомый минимальный путь из v1 в v6 в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из v1 в v6 .

Шаг 1. Составляется матрица длин дуг и таблица величин z. Если z = ,

то вершина vj не достижима из v. В этом случае работа алгоритма заканчивается.

Шаг 2. Величина z выражает длину любого минимального пути из v в

vj. Определим минимальное число m e 1, при котором выполняется равенство

z = z. По определению чисел z получаем, что m – минимальное число дуг в пути среди всех минимальных путей из v в vj.

Шаг 3. Последовательно определяем номера i, …, i такие, что

(3.15)

. . . . . . . . . . . . . . .

 

Тогда v vim … vi2 v – искомый минимальный путь из v в vj.

Пример. Найти минимальный путь в орграфе рис.3.32 из вершины v в вершину v.

Рис. 3.32

Шаг 1. Составляем матрицу длин дуг данного орграфа, которая представлена в табл.3.7.

Таблица 3.7

  v1 v2 v3 v4 v5 v6
v1    
v2          
v3          
v4          
v5        
v6            

Далее составляем таблицу величин z, которая представлена в табл. 3.8. Первый столбец этой таблицы ( k = 0 ) будет состоять из следующих элементов

z = 0, z = z = z = z = z = .

Затем определяем элементы второго столбца ( k = 1 ).

По формулам (3.14) получим

z = min [0, min( z + C)].

1djd6

В этом выражении min (z + C) = , т.к. C = (см. первый столбец табл.3.8). 1djd6

Следовательно, все элементы z = 0, т.е. все элементы первой строки равны 0. Остальные элементы второго столбца определяются формулой (3.13), которая будет иметь вид

z = min (z + C).

1djd6

Минимум правой части этой формулы будет при j = 1 т.к. все z = кроме z = 0. Следовательно, искомые элементы будут вычисляться по формуле

z =C и будут равны z = , z = 5, z = 5, z = 2, z = 12.

Далее по формуле (3.13) вычисляем элементы третьего столбца ( k=2 ), начиная со второго. z = min ( z + C) = 7, z = 3, z = 4, z = 2, z = 12.

1djd6

Аналогично определяем элементы остальных строк.

Таблица 3.8

i z z z z z z
1 2

Из табл.3.8 видно, что z = 7 ` ., следовательно, вершина v достижима из вершины v.

Шаг 2. Определяем минимальное число m e 1, из равенства z = z.Из табл.3.8 видно, что m = 4, т.е. минимальное число дуг в пути среди всех минимальных путей из вершины v в вершину v равно 4.

Шаг 3. Последовательно из выражений (3.10) определяем номера

i, i, i, i, i.

Первое равенство в (3.15) будет иметь вид

z + C = z = 7.

Сравнивая четвертый столбец табл.3.8 и шестой столбец табл.3.7 видим, что это равенство выполняется при i = 2, т.е.

z + C = 5 + 2 = 7.

Запишем второе равенство из (3.15), которое будет иметь вид

z+ C = z = 5.

Сравнивая третий столбец табл.3.8 и второй столбец табл.3.7 видим, что это равенство выполняется при i = 3, т.е.

z + C = 3 + 2 = 5.

Следующее равенство из (3.15) имеет вид

z + C = z = 3 и выполняется при i = 5.

Последнее равенство будет иметь вид

z + C = z = 2 и выполняется при i = 1.

Тогда искомый минимальный путь из вершины v в вершину v будет следующий v v v v v. Он содержит минимальное число дуг среди всех возможных путей из v в v.



<== предыдущая лекция | следующая лекция ==>
Нахождение минимального пути в нагруженном графе. | Транспортные сети.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.01 сек.