Лекция 5. Задача маршрутизации. Алгоритм Флойда-Уоршалла_ Туэга_ Мерлина-Сигалла_ Чанди-Мисры, страница 4

Îñòàëîñü ïîêàçàòü, ÷òî ãðàô Tw íå ñîäåðæèò öèêëîâ.Çàìåòèì, ÷òî åñëè äëÿ âåðøèíûíåðàâåíñòâîDu [w ] < ∞, òîÀëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Äîêàçàòåëüñòâî.u 6= w âûïîëíÿåòñÿNbu [w ] 6= udef è DNbu [w ] [w ] < ∞ .Çíà÷èò äëÿ êàæäîé âåðøèíû u ∈ Vw , u 6= w , ñóùåñòâóåòâåðøèíà x ∈ Vw , äëÿ êîòîðîé âåðíî ðàâåíñòâî Nbu [w ] = x .Äëÿ êàæäîé âåðøèíû u ∈ Vw , u 6= w , â ìíîæåñòâå Ew åñòüîäíî ðåáðî, è ïîýòîìó ÷èñëî âåðøèí â Tw áîëüøå ÷èñëà ðåáåðíà 1.

Îñòàëîñü ïîêàçàòü, ÷òî ãðàô Tw íå ñîäåðæèò öèêëîâ.Êîëü ñêîðî äëÿ ðåáðà ux ∈ Ew èìååò ìåñòî ðàâåíñòâîd S (u, w ) = ωux + d S (x, w ) , íàëè÷èå öèêëà hu0 , u1 , . . . , uk i âãðàôå Tw ïîâëåêëî áû çà ñîáîé ñëåäóþùåå ñîîòíîøåíèåÇàìåòèì, ÷òî åñëè äëÿ âåðøèíûíåðàâåíñòâîDu [w ] < ∞, òîd S (u0 , w ) = ωu0 u1 + ωu1 u2 + · · · + ωuk−1 u0 + d S (u0 , w ),èç êîòîðîãî âûòåêàåò0 = ωu0 u1 + ωu1 u2 + · · · + ωuk−1 u0 ,÷òîïðîòèâîðå÷èò äîïóùåíèþ î òîì, ÷òî êàæäûé öèêë èìååòïîëîæèòåëüíûé âåñ.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)var SuDu: set of nodes ;: array of weights ;Nbu: array of nodes ;begin Su := ∅ ;forall v ∈ V doif v = u then begin Du [v ] := 0 ; Nbu [v ] := udef endelse if v ∈ Neighuthen begin Du [v ] := ωuv ; Nbu [v ] := v endelse begin Du [v ] := ∞ ; Nbu [v ] := udef end;while Su 6= V dobegin pick w from V \ Su ;(* Âñå ïðîöåññû âûáèðàþò îäíó è òó æå âåðøèíów*)if u = w then broadcast Dw else receive Dw ;forall v ∈ V doif Du [w ] + Dw [v ] < Du [v ] thenbegin Du [v ] := Du [w ] + Dw [v ] ; Nbu [v ] := Nbu [w ] end;Su := Su ∪ {w }endÀëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Òåîðåìà 5.4.

(î êîððåêòíîñòè óïðîùåííîãî àëãîðèòìàÒóýãà)Óïðîùåííûé àëãîðèòì Òóýãà çàâåðøàåò ñâîå âûïîëíåíèå âêàæäîì óçëå ñåòè ïîñëåNèòåðàöèé îñíîâíîãî öèêëà. Êîãäàu , äëÿ êàæäîé âåðøèíû vâûïîëíÿåòñÿ ðàâåíñòâî Du [v ] = d(u, v ) , è â òîì ñëó÷àå, åñëèñåòè åñòü ïóòü èç u â v , òî çíà÷åíèåì ïåðåìåííîé Nbu [v ]âÿâëÿåòñÿ íàèìåíîâàíèå ïåðâîãî êàíàëà â êðàò÷àéøåì ïóòè èçuàëãîðèòì çàâåðøàåòñÿ â óçëåâv; â ïðîòèâíîì ñëó÷àåNbu [v ] = udef.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Òåîðåìà 5.4.

(î êîððåêòíîñòè óïðîùåííîãî àëãîðèòìàÒóýãà)Óïðîùåííûé àëãîðèòì Òóýãà çàâåðøàåò ñâîå âûïîëíåíèå âêàæäîì óçëå ñåòè ïîñëåNèòåðàöèé îñíîâíîãî öèêëà. Êîãäàu , äëÿ êàæäîé âåðøèíû vâûïîëíÿåòñÿ ðàâåíñòâî Du [v ] = d(u, v ) , è â òîì ñëó÷àå, åñëèñåòè åñòü ïóòü èç u â v , òî çíà÷åíèåì ïåðåìåííîé Nbu [v ]âÿâëÿåòñÿ íàèìåíîâàíèå ïåðâîãî êàíàëà â êðàò÷àéøåì ïóòè èçuàëãîðèòì çàâåðøàåòñÿ â óçëåâv; â ïðîòèâíîì ñëó÷àåNbu [v ] = udef.Äîêàçàòåëüñòâî.Çàâåðøàåìîñòü è ÷àñòè÷íàÿ êîððåêòíîñòü íàøåãî àëãîðèòìàñëåäóþò èç êîððåêòíîñòè àëãîðèòìà Ôëîéäà-Óîðøàëëà(Òåîðåìà 5.3.).

Îòñþäà ñëåäóåò è ñïðàâåäëèâîñòü óòâåðæäåíèÿî çíà÷åíèè ïåðåìåííîéNbu [v ], ïîñêîëüêó çíà÷åíèåèçìåíÿåòñÿ âñÿêèé ðàç, êîãäà ïåðåìåííîéíîâîå çíà÷åíèå ïðèñâàèâàåòñÿ.Du [v ]Nbu [v ]ïðèñâàèâàåòñÿÀëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Íåîáõîäèìî èìåòü ñðåäñòâà äëÿ øèðîêîâåùàòåëüíîãîðàñïðîñòðàíåíèÿ èíôîðìàöèè, â òî âðåìÿ êàê êàæäûé ïðîöåññèìååò âîçìîæíîñòü îáùàòüñÿ òîëüêî ñî ñâîèìè ñîñåäÿìè.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Íåîáõîäèìî èìåòü ñðåäñòâà äëÿ øèðîêîâåùàòåëüíîãîðàñïðîñòðàíåíèÿ èíôîðìàöèè, â òî âðåìÿ êàê êàæäûé ïðîöåññèìååò âîçìîæíîñòü îáùàòüñÿ òîëüêî ñî ñâîèìè ñîñåäÿìè.Äëÿ ýòîãî ïðèãîäíû âîëíîâûå àëãîðèòìû .Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Íåîáõîäèìî èìåòü ñðåäñòâà äëÿ øèðîêîâåùàòåëüíîãîðàñïðîñòðàíåíèÿ èíôîðìàöèè, â òî âðåìÿ êàê êàæäûé ïðîöåññèìååò âîçìîæíîñòü îáùàòüñÿ òîëüêî ñî ñâîèìè ñîñåäÿìè.Äëÿ ýòîãî ïðèãîäíû âîëíîâûå àëãîðèòìû .Íî Òóýã çàìåòèë, ÷òî åñëèDu [w ] = ∞â íà÷àëå ýòàïàîáðàáîòêè îïîðíîé âåðøèíû, òî ïî îêîí÷àíèè ýòîãî ýòàïàòàáëèöà ìàðøðóòèçàöèè óçëàDu [w ] + Dw [v ] < Du [v ]uíå èçìåíÿåòñÿ, ò.ê.

íåðàâåíñòâîíåâåðíî äëÿ êàæäîé âåðøèíûv.Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Íåîáõîäèìî èìåòü ñðåäñòâà äëÿ øèðîêîâåùàòåëüíîãîðàñïðîñòðàíåíèÿ èíôîðìàöèè, â òî âðåìÿ êàê êàæäûé ïðîöåññèìååò âîçìîæíîñòü îáùàòüñÿ òîëüêî ñî ñâîèìè ñîñåäÿìè.Äëÿ ýòîãî ïðèãîäíû âîëíîâûå àëãîðèòìû .Íî Òóýã çàìåòèë, ÷òî åñëèDu [w ] = ∞â íà÷àëå ýòàïàîáðàáîòêè îïîðíîé âåðøèíû, òî ïî îêîí÷àíèè ýòîãî ýòàïàòàáëèöà ìàðøðóòèçàöèè óçëàDu [w ] + Dw [v ] < Du [v ]uíå èçìåíÿåòñÿ, ò.ê. íåðàâåíñòâîíåâåðíî äëÿ êàæäîé âåðøèíûÏîýòîìó òàáëèöó ìàðøðóòèçàöèèDwòå óçëû, êîòîðûå ïðèíàäëåæàò äåðåâóv.íóæíî äîñòàâèòü òîëüêî âTw(â òîì âèäå, âêîòîðîì îíî ïîñòðîåíî ê íà÷àëó ýòàïà îáðàáîòêè îïîðíîéâåðøèíû), è øèðîêîâåùàòåëüíóþ ðàññûëêó ìîæíî ïðîâåñòèDw òîëüêîTw .ýôôåêòèâíî, îòïðàâëÿÿ òàáëèöóêîòîðûå âõîäÿò â ñîñòàâ äåðåâàïî òåì êàíàëàì,Àëãîðèòì Òóýãà (óïðîùåííûé âàðèàíò)Íåîáõîäèìî èìåòü ñðåäñòâà äëÿ øèðîêîâåùàòåëüíîãîðàñïðîñòðàíåíèÿ èíôîðìàöèè, â òî âðåìÿ êàê êàæäûé ïðîöåññèìååò âîçìîæíîñòü îáùàòüñÿ òîëüêî ñî ñâîèìè ñîñåäÿìè.Äëÿ ýòîãî ïðèãîäíû âîëíîâûå àëãîðèòìû .Íî Òóýã çàìåòèë, ÷òî åñëèDu [w ] = ∞â íà÷àëå ýòàïàîáðàáîòêè îïîðíîé âåðøèíû, òî ïî îêîí÷àíèè ýòîãî ýòàïàòàáëèöà ìàðøðóòèçàöèè óçëàDu [w ] + Dw [v ] < Du [v ]uíå èçìåíÿåòñÿ, ò.ê.

íåðàâåíñòâîíåâåðíî äëÿ êàæäîé âåðøèíûÏîýòîìó òàáëèöó ìàðøðóòèçàöèèDwòå óçëû, êîòîðûå ïðèíàäëåæàò äåðåâóv.íóæíî äîñòàâèòü òîëüêî âTw(â òîì âèäå, âêîòîðîì îíî ïîñòðîåíî ê íà÷àëó ýòàïà îáðàáîòêè îïîðíîéâåðøèíû), è øèðîêîâåùàòåëüíóþ ðàññûëêó ìîæíî ïðîâåñòèDw òîëüêî ïî òåì êàíàëàì,êîòîðûå âõîäÿò â ñîñòàâ äåðåâà Tw . Óçåë w îòïðàâëÿåòòàáëèöó Dw ñâîèì ñûíîâíèì âåðøèíàì â äåðåâå Tw , èêàæäûé óçåë â äåðåâå Tw , ïîëó÷èâ ýòó òàáëèöó îòðîäèòåëüñêîé âåðøèíû â äåðåâå Tw , ïåðåäàåò åå ñâîèìñûíîâíèì âåðøèíàì â äåðåâå Tw .ýôôåêòèâíî, îòïðàâëÿÿ òàáëèöóÀëãîðèòì Òóýãà (ïîëíûé âàðèàíò) íà÷àëå ýòàïà îáðàáîòêè îïîðíîé âåðøèíûäëÿ êîòîðîãîwêàæäûé óçåëu,Du [w ] < ∞ , çíàåò, êàêàÿ âåðøèíà ÿâëÿåòñÿ åãîTw , íî íå çíàåò, êàêèå âåðøèíû ÿâëÿþòñÿðîäèòåëåì â äåðåâååãî ñûíîâüÿìè.v äîëæåí îòïðàâèòü ñîîáùåíèå êàæäîìóu , ñîîáùèâ ïðîöåññó u , ÿâëÿåòñÿ ëè v ñûíîâíåéäëÿ u â äåðåâå Tw .Ïîýòîìó êàæäûé óçåëñâîåìó ñîñåäóâåðøèíîéÀëãîðèòì Òóýãà (ïîëíûé âàðèàíò) íà÷àëå ýòàïà îáðàáîòêè îïîðíîé âåðøèíûäëÿ êîòîðîãîwêàæäûé óçåëu,Du [w ] < ∞ , çíàåò, êàêàÿ âåðøèíà ÿâëÿåòñÿ åãîTw , íî íå çíàåò, êàêèå âåðøèíû ÿâëÿþòñÿðîäèòåëåì â äåðåâååãî ñûíîâüÿìè.v äîëæåí îòïðàâèòü ñîîáùåíèå êàæäîìóu , ñîîáùèâ ïðîöåññó u , ÿâëÿåòñÿ ëè v ñûíîâíåéäëÿ u â äåðåâå Tw .Ïîýòîìó êàæäûé óçåëñâîåìó ñîñåäóâåðøèíîéËþáîé óçåë ìîæåò ïðèíÿòü ó÷àñòèå â ðàñïðîñòðàíåíèèòàáëèöû îïîðíîé âåðøèíûw, êàê òîëüêî îí ïîëó÷èò èçâåñòèÿî òîì, êàêèå èç ñîñåäåé ÿâëÿþòñÿ åãî ñûíîâíèìè âåðøèíàìè âäåðåâåTw.Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò)Èíèöèàëèçàöèÿvar SuDuNbu: set of nodes ;: array of weights ;: array of nodes ;begin Su := ∅ ;forall v ∈ V doif v = uthen begin Du [v ] := 0 ; Nbu [v ] := udef endelse if v ∈ Neighuthen begin Du [v ] := ωuv ; Nbu [v ] := v endelse begin Du [v ] := ∞ ; Nbu [v ] := udef end;Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò)Âûÿâëåíèå ñûíîâíèõ óçëîâwhile Su 6= V dobegin pick w from V \ Su;(* Ïîñòðîèòü äåðåâîTw*)forall x ∈ Neighu doif Nbu [w ] = x then send hys, w i to xelse send hnys, w i to x;recu := 0 ; (* u äîëæåí ïîëó÷èòü |Neighu | ñîîáùåíèé *)while recu < |Neighu | dobegin receive hys, w i or hnys, w i; recu := recu + 1 end;Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò)Óòî÷íåíèå òàáëèö ìàðøðóòèçàöèèif Du [w ] < ∞ then (*ïðèíÿòü ó÷àñòèå â îáðàáîòêå îïîðíîé âåðøèíû*begin if u 6= w then receive hdtab, w , Di from Nbu [w ] ;forall x ∈ Neighu doif hys, w i was received from xthen send hdtab, w , Di to x ;forall v ∈ V do (*ëîêàëüíàÿ îáðàáîòêà îïîðíîé âåðøèíû w *)if Du [w ] + D[v ] < Du [v ] thenbegin Du [v ] := Du [w ] + D[v ]; Nbu [v ] := Nbu [w ] endend;Su := Su ∪ {w }endendÀëãîðèòì Òóýãà (ïîëíûé âàðèàíò) àëãîðèòìå èñïîëüçóþòñÿ ñîîáùåíèÿ òðåõ òèïîâ:Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò) àëãîðèòìå èñïîëüçóþòñÿ ñîîáùåíèÿ òðåõ òèïîâ:hys, w i (ys îò ¾your son¿) îòïðàâëÿåòñÿ îòóçëà u ê óçëó x â íà÷àëå ýòàïà îáðàáîòêè îïîðíîéâåðøèíû w , åñëè x ÿâëÿåòñÿ ðîäèòåëüñêîé âåðøèíîé äëÿu â äåðåâå Tw .1.

ÑîîáùåíèÿÀëãîðèòì Òóýãà (ïîëíûé âàðèàíò) àëãîðèòìå èñïîëüçóþòñÿ ñîîáùåíèÿ òðåõ òèïîâ:hys, w i (ys îò ¾your son¿) îòïðàâëÿåòñÿ îòóçëà u ê óçëó x â íà÷àëå ýòàïà îáðàáîòêè îïîðíîéâåðøèíû w , åñëè x ÿâëÿåòñÿ ðîäèòåëüñêîé âåðøèíîé äëÿu â äåðåâå Tw .1. Ñîîáùåíèÿhnys, w i (nys îò ¾not your son¿) îòïðàâëÿåòñÿx â íà÷àëå ýòàïà îáðàáîòêè îïîðíîéâåðøèíû w , åñëè x íå ÿâëÿåòñÿ ðîäèòåëüñêîé âåðøèíîéäëÿ u â äåðåâå Tw .2.

Ñîîáùåíèåîò óçëàuê óçëóÀëãîðèòì Òóýãà (ïîëíûé âàðèàíò) àëãîðèòìå èñïîëüçóþòñÿ ñîîáùåíèÿ òðåõ òèïîâ:hys, w i (ys îò ¾your son¿) îòïðàâëÿåòñÿ îòóçëà u ê óçëó x â íà÷àëå ýòàïà îáðàáîòêè îïîðíîéâåðøèíû w , åñëè x ÿâëÿåòñÿ ðîäèòåëüñêîé âåðøèíîé äëÿu â äåðåâå Tw .1. Ñîîáùåíèÿhnys, w i (nys îò ¾not your son¿) îòïðàâëÿåòñÿx â íà÷àëå ýòàïà îáðàáîòêè îïîðíîéâåðøèíû w , åñëè x íå ÿâëÿåòñÿ ðîäèòåëüñêîé âåðøèíîéäëÿ u â äåðåâå Tw .2. Ñîîáùåíèåîò óçëàuê óçëóhdtab, w , Di îòïðàâëÿåòñÿ ïî õîäó îáðàáîòêèw ïî êàæäîìó ðåáðó äåðåâà Tw , ÷òîáûòàáëèöó Dw â êàæäóþ âåðøèíó, êîòîðàÿ äîëæíà3. Ñîîáùåíèåîïîðíîé âåðøèíûäîñòàâèòüáóäåò âîñïîëüçîâàòüñÿ ýòèì çíà÷åíèåì.Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò)ÏóñòüW ÷èñëî áèòîâ äëÿ çàïèñè âåñà ïóòè.Òåîðåìà 5.5.

(êîððåêòíîñòè è ñëîæíîñòè àëãîðèòìàÒóýãà)Äëÿ êàæäîé ïàðû âåðøèíðàññòîÿíèå ìåæäóuèvuèvàëãîðèòì Òóýãà âû÷èñëÿåò. Åñëè ýòî ðàññòîÿíèå êîíå÷íî, òî îíòàêæå îïðåäåëÿåò ïåðâûé êàíàë â êðàò÷àéøåì ïóòè.Ïî õîäó ðàáîòû àëãîðèòìà ïî êàæäîìó êàíàëó ïðîõîäèòO(N)2ñîîáùåíèé, O(N W ) áèòîâ èíôîðìàöèè. Òàêèì îáðàçîì,ñóììàðíî ïî õîäó ðàáîòû àëãîðèòìà ïåðåäàåòñÿñîîáùåíèé èO(N 3 · W )O(N · |E |)áèòîâ èíôîðìàöèè. Êðîìå òîãî âêàæäîì óçëå èñïîëüçóåòñÿ ïàìÿòü, îáúåì êîòîðîé ñîñòàâëÿåòO(N · W )áèòîâ.Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò)ÄîêàçàòåëüñòâîÏîëíàÿ âåðñèÿ àëãîðèòìà Òóýãà ïîñòðîåí íà îñíîâåóïðîùåííîé âåðñèè, è ïîýòîìó êîððåêòíà.Àëãîðèòì Òóýãà (ïîëíûé âàðèàíò)ÄîêàçàòåëüñòâîÏîëíàÿ âåðñèÿ àëãîðèòìà Òóýãà ïîñòðîåí íà îñíîâåóïðîùåííîé âåðñèè, è ïîýòîìó êîððåêòíà.