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

Íàïèøèòå ïñåâäîêîä äëÿ àëãîðèòìà ÌåðëèíàÑèãàëëà.Äîêàæèòå åãî êîððåêòíîñòü. Îïðåäåëèòå îöåíêó ñëîæíîñòèàëãîðèòìà ÌåðëèíàÑèãàëëà ïî ÷èñëó ñîîáùåíèé è ïî÷èñëó ïåðåñûëàåìûõ áèòîâ.2. Ïîêàæèòå, ÷òî (ïðîìåæóòî÷íûå) òàáëèöû ìàðøðóòèçàöèè,âû÷èñëÿåìûå àëãîðèòìîì Ìåðëèíà-Ñèãàëëà, âñåãäàîñòàþòñÿ àöèêëè÷åñêèìè íà ïðîòÿæåíèè ðàáîòûàëãîðèòìà.3. Äîêàæèòå Òåîðåìó 5.6.Àëãîðèòì ×àíäèÌèñðûÀëãîðèòì ×àíäè è Ìèñðû âû÷èñëÿåò âñå êðàò÷àéøèå ïóòè êçàäàííîé âåðøèíå-àäðåñàòó íà îñíîâå ïðèíöèïà äèôôóçíûõâû÷èñëåíèé .

Ñóòü åãî òàêîâà: ðàñïðåäåëåííîå âû÷èñëåíèåíà÷èíàåòñÿ â îäíîé-åäèíñòâåííîé âåðøèíå, è äðóãèå óçëû ñåòèïîî÷åðåäíî ïðèñîåäèíÿþòñÿ ê âû÷èñëåíèþ òîëüêî ïîñëåïîëó÷åíèÿ ñîîáùåíèÿ.Àëãîðèòì ×àíäèÌèñðûÀëãîðèòì ×àíäè è Ìèñðû âû÷èñëÿåò âñå êðàò÷àéøèå ïóòè êçàäàííîé âåðøèíå-àäðåñàòó íà îñíîâå ïðèíöèïà äèôôóçíûõâû÷èñëåíèé . Ñóòü åãî òàêîâà: ðàñïðåäåëåííîå âû÷èñëåíèåíà÷èíàåòñÿ â îäíîé-åäèíñòâåííîé âåðøèíå, è äðóãèå óçëû ñåòèïîî÷åðåäíî ïðèñîåäèíÿþòñÿ ê âû÷èñëåíèþ òîëüêî ïîñëåïîëó÷åíèÿ ñîîáùåíèÿ.×òîáû âû÷èñëèòü ðàññòîÿíèå îò êàæäîé âåðøèíû äî çàäàííîãîóçëàv0(à òàêæå ïðåäïî÷òèòåëüíûé èñõîäÿùèé êàíàë ñâÿçè),êàæäûé óçåëuóñòàíàâëèâàåò íà÷àëüíîå çíà÷åíèåîæèäàåò ïîëó÷åíèÿ ñîîáùåíèé.Du [v0 ] = ∞èÀëãîðèòì ×àíäèÌèñðûÀëãîðèòì ×àíäè è Ìèñðû âû÷èñëÿåò âñå êðàò÷àéøèå ïóòè êçàäàííîé âåðøèíå-àäðåñàòó íà îñíîâå ïðèíöèïà äèôôóçíûõâû÷èñëåíèé .

Ñóòü åãî òàêîâà: ðàñïðåäåëåííîå âû÷èñëåíèåíà÷èíàåòñÿ â îäíîé-åäèíñòâåííîé âåðøèíå, è äðóãèå óçëû ñåòèïîî÷åðåäíî ïðèñîåäèíÿþòñÿ ê âû÷èñëåíèþ òîëüêî ïîñëåïîëó÷åíèÿ ñîîáùåíèÿ.×òîáû âû÷èñëèòü ðàññòîÿíèå îò êàæäîé âåðøèíû äî çàäàííîãîóçëàv0(à òàêæå ïðåäïî÷òèòåëüíûé èñõîäÿùèé êàíàë ñâÿçè),êàæäûé óçåëuóñòàíàâëèâàåò íà÷àëüíîå çíà÷åíèåDu [v0 ] = ∞èîæèäàåò ïîëó÷åíèÿ ñîîáùåíèé.Óçåëv0hmydist, v0 , 0i âñåì ñâîèìu ïîëó÷àåò ñîîáùåíèåîòïðàâëÿåò ñîîáùåíèåñîñåäÿì. Êàê òîëüêî âåðøèíàhmydist, v0 , diw è óáåæäàåòñÿ â òîì, ÷òîd + ωuw < Du [v0 ] , çíà÷åíèåìïåðåìåííîé Du [v0 ] ñòàíîâèòñÿ ñóììà d + ωuw , è âñåì ñîñåäÿìâåðøèíû u îòïðàâëÿåòñÿ ñîîáùåíèå hmydist, v0 , Du [v0 ]i.îò ñîñåäàâûïîëíÿåòñÿ íåðàâåíñòâîÀëãîðèòì ×àíäèÌèñðûvar Du [v0 ]Nbu [v0 ]: âåñ: âåðøèíàinit ∞ ;init udef;v0 :begin Dv0 [v0 ] := 0 ;forall w ∈ Neighv0 doÒîëüêî äëÿ âåðøèíûsendhmydist, v0 , 0itowendhmydist, v0 , di,ïîëó÷åííîãî âåðøèíîé u îò ñîñåäà w :{ hmydist, v0 , di ∈ Mwu }begin receive hmydist, v0 , di from w ;if d + ωuw < Du [v0 ] thenbegin Du [v0 ] := d + ωuw ; Nbu [v0 ] := w ;forall x ∈ Neighu do send hmydist, v0 , Du [v0 ]iÎáðàáîòêà ñîîáùåíèÿendendtoxÀëãîðèòì ×àíäèÌèñðûÇàäà÷è.1.

Äîêàæèòå, ÷òî ïðèâåäåííàÿ íèæå ôîðìóëà çàäàåòèíâàðèàíò àëãîðèòìà ×àíäè-Ìèñðû âû÷èñëåíèÿ ïóòåé,âåäóùèõ â âåðøèíóv0 .∀u, w : hmydist, v0 , di ∈ Mwu∧ ∀u : d(u, v0 ) ≤ Du [v0 ]=⇒d(w , v0 ) ≤ dÏðèâåäèòå ïðèìåð âûïîëíåíèÿ, â êîòîðîì êîëè÷åñòâîîáìåíîâ ñîîáùåíèÿì ýêñïîíåíöèàëüíî çàâèñèò îò ÷èñëàêàíàëîâ â ñåòè.Du [v0 ]d(u, v0 ), ò.å.2. Èñïîëüçóÿ èíâàðèàíò, äîêàæèòå, ÷òî çíà÷åíèåâñåãäà ÿâëÿåòñÿ âåðõíåé îöåíêîé âåëè÷èíûd(u, v0 ) ≤ Du [v0 ].Àëãîðèòì ×àíäèÌèñðûÇàäà÷è.1.

Äîêàæèòå, ÷òî â ðàìêàõ äîïóùåíèÿ ñëàáîé ñïðàâåäëèâîñòèî òîì, ÷òî â ëþáîì âûïîëíåíèè êàæäîå îòïðàâëåííîåñîîáùåíèå ðàíî èëè ïîçäíî áóäåò ïîëó÷åíî, â ëþáîìâû÷èñëåíèè àëãîðèòìà ×àíäèÌèñðû äîñòèãàåòñÿ òàêàÿêîíôèãóðàöèÿ, ÷òî â êàæäîì óçëåíåðàâåíñòâîDu [v0 ] ≤ d(u, v0 ).uâûïîëíÿåòñÿÎòñþäà ñëåäóåòêîððåêòíîñòü ýòîãî àëãîðèòìà2. Äîêàæèòå, ÷òî Àëãîðèòì ×àíäèÌèñðû âû÷èñëÿåòòàáëèöû ìàðøðóòèçàöèè ñ íàèìåíüøèì ÷èñëîì çâåíüåâñîâåðøàÿ ïðè ýòîì îáìåíO(N 2 · W )O(N 2 )ñîîáùåíèÿìè è ïåðåäàâàÿáèòîâ èíôîðìàöèè ïî êàæäîìó êàíàëó ñâÿçè .Àëãîðèòì ×àíäèÌèñðûÇàäà÷è.1.

 îïèñàíèè àëãîðèòìà ×àíäèÌèñðû íå óêàçûâàåòñÿ, äîêàêèõ ïîð äîëæíî ïðîâîäèòüñÿ âû÷èñëåíèå ìàðøðóòîâ âêàæäîì ïðîöåññå. Äîêàæèòå, â ëþáîé êîíôèãóðàöèèëþáîãî âûïîëíåíèÿ àëãîðèòìà ×àíäèÌèñðûïðîìåæóòî÷íûå òàáëèöû ìàðøðóòèçàöèè ÿâëÿþòñÿàöèêëè÷åñêèìè. ×òî íóæíî äîáàâèòü ê àëãîðèòìó×àíäèÌèñðû, äëÿ òîãî ÷òîáû êàæäûé ïðîöåññ ìîãóçíàòü, ÷òî ïîñòðîåíèå òàáëèö ìàðøðóòèçàöèè â ñåòèçàâåðøåíî.ÊÎÍÅÖ ËÅÊÖÈÈ 5..