Распределенные алгоритмы (стр. 27 из 85)

4.2.1 Алгоритм Флойда-Уошала

Пусть дан взвешенный граф G = (V, E) , где вес ребра uv дан wuv . Не обязательно допускать что wuv= wvu , но допустим, что граф не содержит циклов с общим отрицательным весом. Вес пути < uo, ..., uk> определяется как

. Дистанция от u до v, обозначенная d(u, v), наименьший вес любого пути от u к v (¥ если нет такого пути). Проблема кротчайших путей всех пар - вычисление d(u, v) для каждых u и v.

Для вычисления всех расстояний, алгоритм Флойда-Уошала использует понятие S-путей; это пути, в которых все промежуточные вершины принадлежат к подмножеству S из V.

Определение 4.4. Пусть S - подмножество V. Путь < uo ..., uk> -S-путь если для любого i, 0 <i < k, uj Î S. S-расстояние от u до v, обозначенное d^S(u. v), наименьший вес любого S-пути от u до v (¥ если такого пути нет).

Алгоритм стартует рассмотрением всех Æ-путей, и увеличивая вычисления S-путей для больших подмножеств S, до тех пор пока V-пути будут рассмотрены. Могут быть сделаны следующие наблюдения.

Утверждение 4.5 Для всех u и S, d^S(u, u) = 0. Более того, S-пути удовлетворяют следующим правилам для u¹ v.

(1) Существует Æ -путь от u к v тогда и только тогда когда uv ÎE.

(2) Если uv Î E тогда d^S(u, v) = w_uv иначе d^S(u, v) =¥ .

(3) Если S'=S È{w} тогда простой S'-путь от и к v - S-путь от u к v или S-путь от u к w соединенные S-путем от w к v.

(4) Если S' = S È{w} тогда d^S’ (u, v)=min(d^S (u, v), d^S (u, w)+ d^S (w, v)).

(5) Путь от u до v существует тогда и только тогда когда V-путь от u к v существует

(6) d(u, v)= d^V (u, v),

Доказательство. Для всех u и S d^S (u, u) £.0 по причине того, что пустой путь (состоящий из 0 ребер) это S-путь от u к u с весом 0. Нет путей, имеющих меньший вес, потому что G не содержит циклов отрицательного веса, таким образом, d^S (u, u) = 0.

Для (1): Æ -путь не содержит промежуточных узлов, так Æ - путь от u к v

состоит только из канала uv.

Для (2): следует непосредственно из (1).

Для (3): простой S’-путь от u к v содержит узел w единожды, или 0 раз как промежуточный. Если он не содержит w как промежуточную вершину он S-путь, иначе он - конкатенация двух S-путей, один к w и один из w.

Для(4): Это можно доказать применив Лемму 4.1 . Получим что (если S’-путь от u в v существует) это простой S' -путь длиной d^S’(u, v) от u к v, такой, что d^S’(u, v) = min(d^S (u, v), d^S (u, w) + d^S (w, v) ) по (3).

Для (5): каждый S-путь - путь, и обратно.

Для (6): каждый S-путь - путь, и обратно, следовательно, оптимальный V-путь также оптимальный путь.

_____________________________________________________________________

begin (* Инициализация S = Æ и D = Æ-дистанция *)

S:=0;

forall u,v do

if u = v then D[u, v] := 0

else

if uv Î E then D[u, v] := w_uv

else D[u. v] := ¥ ;

(* Расширим S «центральными точками» *)

while S ¹ V do

(* Цикл инвариантен: "u, v : D[u, v] = d^S (u, v) *)

begin выбрать w из V \ S ;

(* Выполнить глобальную w-центровку *)

forall u Î V do

(* Выполнить локальную w-центровку u *)

forall v ÎV do

D[u. v] := min ( D[u, v], D[u, w] + D[w, v] ) ;

S:=S È{w}

end (*"u, v : D[u, v] = d^S (u, v)*)

end

Алгоритм4.4 Алгоритм Флойда-Уошалла.

Используя Утверждение 4.5 не сложно разработать алгоритм "динамического программирования" для решения проблемы кротчайших путей всех пар; смотри см. Алгоритм 4.4. Алгоритм вначале считает 0-пути, и, увеличивая, вычисляет S-пути для больших множеств S (увеличивая S "центральными" кругами), до тех пор, пока все пути не будут обсуждены.

Теорема 4.6 Алгоритм 4.4 вычисляет расстояние между всеми парами узлов за Q(N³) шагов.

Доказательство. Алгоритм начинает с D[u, v] = 0, если u = v, D[u, v] = w_uv , если uv Î E и D[u, v] = ¥ в другом случае, и S = 0. Следуя из Утверждения 4.5, частей (1) и (2), "u, v имеет силу D[u, v] = d^S (u, v) . В центральной окружности с центральной вершиной w множество S расширено узлом w, и означивание D[u, v] гарантирует (по частям (3) и (4) утверждения) что утверждение "u, v : D[u, v] = d^S(u, v) сохранено как инвариант цикла. Программа заканчивает работу, когда S = V, т.е., (по частям (5) и (6) утверждения и инварианту цикла) S-расстояние эквивалентно расстоянию.

Главный цикл выполняется N раз, и содержит N²операций (которые могут быть выполнены параллельно или последовательно), откуда и следует временная граница данная теоремой.

_____________________________________________________________________

var S_u : множество вершин;

D_u: массив весов;

Nb_u : массив вершин;

begin S_u :=Æ ;

forall v Î V do

if v = u

then begin D_u [v] :=0 ; Nb_u[v] := udef end

else if v Î Neigh_u

then begin D_u[v] := w_uv ; Nb_u[v] := v end

else begin Du[v] := ¥ ; Nb_u[v] := udef end ;

while S_u¹ V do

begin выбрать w из V \ S_u ;

(* Все вершины должны побывать вершиной w *)

if u == w

then "распространить таблицу D_w"

else "принять таблицу D_w"

forall v Î V do

if D_u[w] + D_w[v] < D_u[v] then

begin D_u[v]:= D_u[w] + D_w[v] ;

Nb_u[v] := Nb[w]

end;

Su := Su U {w}

end

end;

Алгоритм 4.5 Простой алгоритм (Для узла u).

4.2.2 Алгоритм кротчайшего пути.(Toueg)

Распределенный алгоритм вычисления таблиц маршрутизации бал дан Toueg [TouSOa], основанный на алгоритме Флойда-Уошалла описанном в предыдущей части. Можно проверить что алгоритм Флойда-Уошалла подходит для этих целей, т.е., что его ограничения реалистичны для распределенных систем. Наиболее важное ограничение алгоритма что граф не содержит циклов отрицательного веса. Это ограничение действительно реально для распределенных систем, где обычно каждый отдельный канал означен положительной оценкой. Даже можно дать более строгое ограничение; смотри A1 ниже. В этой части даны следующие ограничения.

A1. Каждый цикл в сети имеет положительный вес.

A2. Каждый узел в сети знает обо всех узлах (множество V).

A3. Каждый узел знает какой из узлов его сосед (хранится в Neigh_u для узла u) и веса своих выходящих каналов.

Корректность алгоритма Toueg (Алгоритма4.6) будет более просто понять если мы сперва обсудим предварительную версию алгоритма , "простой алгоритм" (Алгоритм 4.5).

Простой алгоритм. Для достижения распределенного алгоритма переменные и операции алгоритма Флойда-Уошала распределены по узлам сети. D[u, v] - переменная принадлежащая узлу u; по соглашению, это будет выражено описанием D_u[v] .Операция, означивающая D_u[v], должна быть выполнена узлам u, и когда необходимо значение переменной узла w, это значение должно быть послано u. В алгоритме Флойда-Уошала все узлы должны использовать информацию из «центрального» узла (w в теле цикла), который посылает эту информацию к всем узлам одновременно операцией "распространения". В заключение, алгоритм будет расширен операцией для поддержки не только длины кратчайших S-путей (как в переменной D_u[v]), но также первый канал такого пути (в переменной Nb_u[v]).

Утверждение что циклы сети имеет положительный вес может использоваться чтобы показать что не существует циклов в таблицах маршрутизации.

Лемма 4.7 Пусть даны S и w и выполняется:

(1) для всех u :D_u[w] = d^S(u, w) и

(2) если d^S(u, w) < ¥ и u ¹ w, то Nb_u[w]- первый канал кратчайшего S-пути к w.

Тогда направленный граф T_w = (V_w, E_w), где (u Î V_w Û D_u[w]<¥ ) и (ux ÎE_w Û (v¹wÙNb_u[w]=x)) - дерево с дугами направленными к w.

Доказательство. Во-первых, заметим, что если D_u[w] < ¥ для u ¹ w, то Nb_u[w] ¹ udef и

. Таким образом для каждого узла u Î V_w, u ¹ w существует узел x для которого Nb_u[w] = x, и x Î V_w.

Для каждого узла u¹ w в V_w существует единственное ребро в E_w, такое что число узлов в T_wпревышает количество ребер на единицу и достаточно показать что T_w не содержит циклов. Так ux ÎE_w подразумевает что d^S(u, w) =w_ux+ d^S(x, w), существование цикла <u_o, u₁, .. ., u_k> в T_w подразумевает что

d^S(u_o, w) = w_{uo u1} + w_{u1 u2} + … + w_{uk-1 uo}u+ d^S(u_o, w),

т.е., 0 = w_{uo u1} + w_{u1 u2} + … + w_{uk-1 uo}u