Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 [ 61 ] 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

для х^: Г5 = {х Хг, х^ fl { з, Ч) = {б), P(x5) = min[2, (22 + 20)1 = 2;

для Xg: Ге = {Х4, Xg, х xg} П {а:з, А. .з^б} = {2:4}, F (Хб) = min [22, (- 5 +18)] = 13;

для Х^: Г, = {Х4, Хб, Xg} П {.З 4, х^) = {4, З^б}.

Z3(x7) = min[oo, min{(-5 + 4), (22 + 9)}]= -1;

для Xg: = {хз, x,} П {хз, X4, Xg} = {хз},

(Xg) = min [ с , (- 8 + 24)] = 16;

для Xg: Гд = (Xi, Xg} П (хз, 4, .e} = {k), Z (x9) = min[oo, (-5 + 11)1 = 6.

Xj=x

Пометки {xi) равны [0, -3, -8, -5, 2, 13, -1, 16, 6] для Xi = Xj, Xg, . . ., Xg соответственно.

Шаг 3 (б). Перейти к шагу 4.

Шаг 4. 5 = {Хб, x, Xg, Xg}.

Шаг 5. А; = 3, перейти к шагу 2. И т. д.

Продолжая этот процесс, получаем результаты, приведенные ниже в краткой форме.

Третья итерация

Шаг 2. Г (5) = {хд, Х4, Xj, xg, Х7, Xg, Xg}, Tg = {X7, Xg}, Z* (хз) = -11,

Г4 = {X7, Xg}, Z* (X4) = -5,

T, = {Xg}, Z* (xg) = 2, Ге = {X7, Xg}, Z* (Xg) = -7, = {6, X,}, Z* (X7) = -1,

78 = W, г* W = 15,

Гд = {x}, Z* (Xg) = 6.

Вектор пометок Z* (x) равен [0, -3, -11, -5, 2, -7, -1 15, 6.1

Шаг 4. S = {xg, Xg, Xg}.



Четвертая итерация

Шаг. 2. Г (5) = {xj, Х4, Zj, 3>j, Xg, x),

Тз = Ы. г (хз) = -и, т, = {Хз}, = -5,

Ts = {Хв}, I ixs) = 2,

= {6, х^), V (хт) = -1, Т'в = {а:,}, I Ы = 13, Гэ = {xg}, г (хэ) = 6.

Вектор пометок V (xj) равен [О, -3, -И, -5, 2, -7, -1, 13, 6].

Шаг 4. S = {xg}.

Пятая итерация

Шаг 2. Г (S) = {xg, х xJ,

7з = Ы, Ы = -11,

Т, = {xg}, Z (х,) = -1,

Т, = {хэ}, г (хв) = 6. Zffoe 3 (о). Останов.

Вектор пометок (xj) совпадает с (xj), и, следовательно, ати пометки равны длинам кратчайших путей. Сами пути строятся


Рис. 8.4. Окончательные пометки вершин и я-бааа.

последовательно, как и в том случае, когда использовалось соотношение (8.2). Соответствующая Xi-база показана жирными линия ми на рис. 8.4.



3. Кратчайшие пути между всеми парами вершин

Пусть требуется найти кратчайшие пути между всеми парами вершин графа. Очевидный способ получить ответ на этот вопрос заключается в ге-кратном применении алгоритма предыдупцего раздела, причем каждый раз в качестве начальной вершины s берутся различные вершины. В случае полного графа с неотрицательной матрицей весов С время, необходимое для вычислений, пропорционально га, а для произвольной матрицы весов оно про порциона л ьно га*. Поэтому если задача о кратчайшем пути имеет большую размерность, то ее невозможно решить с помош;ью последовательного применения алгоритма из разд. 2.2.

В настоящем разделе мы опишем совершенно иной подход к задаче нахождения кратчайших путей между всеми парами вершин. Этот метод применим как к неотрицательным, так и к произвольным матрицам весов и время, необходимое для вычислений, пропорционально га*. Если этот метод применить к графам с неотрицательной матрицей весов, то он сэкономит почти 50% времени [И] по сравнению с га-кратным применением алгоритма Дейкстры Метод был предложен первоначально Флойдом [13] и развит Мерчлэндом [27]. Он базируется на использовании последовательности из га преобразований (итераций) начальной матрицы весов С При этом на к-й итерации матрица представляет длины кратчайших путей между каждой парой верпшн с тем ограничением, что путь между Xt и Xf (для любых Х{ и xj) содержит в качестве промежуточных только вершины из множества {ху, Х2, . . ., ж^}.

3.1. Алгоритм Флойда (для произвольной матрицы весов)

Предположим, что в начальной матрице весов Сц = О для всех i = 1, 2, .... ге и С|у = оо, если в графе отсутствует дуга {xt, х,).

Присвоение начальных значений

Шаг 1. Положить А: = 0.

Итерация

Шаг 2. к =:к i.

Шаг 3. Для всех i Ф к, таких, что с, =И= оо, и для всех / Ф к, таких, что Си.]ф оо, введем операцию

cj , = min[c,y, (c,fc-fCfty)]. (8.5)

Проверка на окончание

Шаг 4. (а) Если сц <0, то в графе G существует цикл отрицательного веса, содержапщй вершину Х{, и решения нет. Останов.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 [ 61 ] 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95