8 Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон, страница 4

Êàê áûëî óæå óñòàíîâëåíî, ïîêàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ (ïî îäíîìó âêàæäîì íàïðàâëåíèè), è ýòî ñëóæèò îáîñíîâàíèåì ñëîæíîñòèïî ÷èñëó ñîîáùåíèé.Îñòàåòñÿ óáåäèòüñÿ â òîì, ÷òî äåðåâî, ïîñòðîåííîå â ðåçóëüòàòåïðèìåíåíèÿ ïðàâèëà R3, áóäåò äåðåâîì ïîèñêà â ãëóáèíó.Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÄîêàçàòåëüñòâî.Ñîãëàñíî ïðàâèëó R3 âñëåä çà ïåðâûì ïðîõîæäåíèåì ïîñòÿãèâàþùèåìó ðåáðó íåìåäëåííî ñëåäóåò ïîâòîðíîåïðîõîæäåíèå â îáðàòíîì íàïðàâëåíèè.Äîïóñòèì, ÷òî pq ýòî ñòÿãèâàþùåå ðåáðî, è p ïåðâûéïðîöåññ, âîñïîëüçîâàâøèéñÿ ýòèì ðåáðîì. Ê òîìó ìîìåíòó,êîãäà ïðîöåññ q ïîëó÷àåò ìàðêåð îò p , ýòîò ìàðêåð óæåïîáûâàë â q (èíà÷å q çàíåñ áû â ïåðåìåííóþ fatherq ññûëêó íàp , è íàøå ðåáðî íå ìîãëî áû ñ÷èòàòüñÿ ñòÿãèâàþùèì) èusedq [p] èìååò çíà÷åíèå false (ïîñêîëüêó ïî ïðåäïîëîæåíèþ páûë ïåðâûì èç ýòèõ äâóõ ïðîöåññîâ, âîñïîëüçîâàâøèìñÿóêàçàííûì ðåáðîì).Ñëåäîâàòåëüíî, ñîãëàñíî ïðàâèëó R3, q íåìåäëåííî âîçâðàùàåòìàðêåð ïðîöåññó p .Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÄîêàçàòåëüñòâî.Òåïåðü ìîæíî ïîêàçàòü, ÷òîåñëè ðåáðîpqÿâëÿåòñÿñòÿãèâàþùèì, è åãî âïåðâûå èñïîëüçîâàë ïðîöåññp, òîq ∈ A[p] .Ðàññìîòðèì ïóòü, ïî êîòîðîìó ñëåäîâàë ìàðêåð äî òåõ ïîð,ïîêà îí íå áûë îòïðàâëåí ïî ðåáðó pq .

Ò.ê. pq ñòÿãèâàþùååðåáðî, ìàðêåð óæå ïîáûâàë â âåðøèíå q äî òîãî, êàê îí äîñòèãq ïî óêàçàííîìó ðåáðó: . . . , q, . . . , p, qÑîêðàòèì ýòîò ïóòü, çàìåíÿÿ âñå ôðàãìåíòû âèäà r1 , r2 , r1 ,ãäå r1 r2 ñòÿãèâàþùåå ðåáðî, ôðàãìåíòîì r1 . Òîãäà âñåñòÿãèâàþùèå ðåáðà áóäóò óäàëåíû. Ïîëó÷åííûé â ðåçóëüòàòåïóòü áóäåò ïóòåì â T , ñîñòîÿùèì òîëüêî èç ðåáåð,èñïîëüçîâàííûõ ïðåæäå ïåðâîãî îáðàùåíèÿ ê pq .Åñëè q íå ÿâëÿåòñÿ ïðåäøåñòâåííèêîì p , òî ðåáðî èç q âfatherq áûëî çàäåéñòâîâàíî ðàíåå, íåæåëè áûëî èñïîëüçîâàíîðåáðî qp , âîïðåêè ïðàâèëó R2 íàøåãî àëãîðèòìà.Àëãîðèòì ÀâåðáàõàÊëàññè÷åñêèé àëãîðèòì ïîèñêà â ãëóáèíó èìååò áîëüøóþñëîæíîñòü ïî âðåìåíè, ò.ê.

âñå ðåáðà ñåòè îáõîäÿòñÿïîñëåäîâàòåëüíî. Ïðè ýòîì ìàðêåð-ñîîáùåíèå îáõîäèò âñåñòÿãèâàþùèå ðåáðà è íåìåäëåííî âîçâðàùàåòñÿ. Âî âñÿêîìðåøåíèè áîëåå íèçêîé ñëîæíîñòè ïî âðåìåíè ìàðêåð-ñîîáùåíèåïðîõîäèò òîëüêî ïî ðåáðàì, âõîäÿùèì â äåðåâî. àëãîðèòìå Àâåðáàõà ïðîöåññ ïðè ïåðåäà÷å ìàðêåðà óæå çíàåòî òîì, ó êàêîãî èç åãî ñîñåäåé óæå ïîáûâàë ìàðêåð.Òîãäà ïðîöåññ ëèáî âûáèðàåò êàêîãî-íèáóäü ñîñåäà, íåïîëó÷àâøåãî äî ñèõ ïîð ìàðêåð, ëèáî âîçâðàùàåò ìàðêåð âðîäèòåëüñêóþ âåðøèíó, åñëè òàêîãî ñîñåäà íåò.Àëãîðèòì ÀâåðáàõàÊîãäà ìàðêåð âïåðâûå äîñòàåòñÿ ïðîöåññó p (äëÿ èíèöèàòîðà â ìîìåíò çàïóñêà àëãîðèòìà), p îïîâåùàåò êàæäîãî ñîñåäà r ,êðîìå ðîäèòåëüñêîé âåðøèíû, îòïðàâëÿÿ åìó ñîîáùåíèå hvisi.Ìàðêåð íå ïåðåäàåòñÿ, äî òåõ ïîð ïîêà p íå ïîëó÷èò ñîîáùåíèåhacki îò âñåõ ñâîèõ ñîñåäåé.

Ýòî ãàðàíòèðóåò, ÷òî êàæäûéñîñåä r ïðîöåññà p îñâåäîìëåí ê ìîìåíòó îòïðàâëåíèÿ ìàðêåðàïðîöåññîì p î òîì, ÷òî ýòîò ìàðêåð óæå ïîáûâàë ó p .Êîãäà ïîçäíåå ìàðêåð äîñòèãíåò r , ïðîöåññ r óæå íå áóäåòîòïðàâëÿòü ìàðêåð ïðîöåññó p , åñëè òîëüêî p íå ÿâëÿåòñÿðîäèòåëüñêîé âåðøèíîé äëÿ r .Àëãîðèòì Àâåðáàõàvarusedp [q]fatherp: bool init false for each q ∈ Neighp ;(*Óêàçûâàåò, îòïðàâëÿë ëè p ìàðêåð ïðîöåññó q *): process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;forall r ∈ Neighp do send hvisi to r ;forall r ∈ Neighp do receive hacki from r ;usedp [q] := true ; send htoki to qendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ htoki îò q0 :begin if fatherp = udef thenbegin fatherp := q0 ;forall r ∈ Neighp \ {fatherp } do send hvisi to r ;forall r ∈ Neighp \ {fatherp } do receive hacki from rend;if p is the initiator and ∀q ∈ Neighp : usedp [q]then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin if fatherp 6= q0 ∧ ¬usedp [q0 ]then q := q0else choose q ∈ Neighp \{fatherp } with ¬usedp [q]usedp [q] := true ; send htoki to qendelse beginusedp [fatherp ] := true ; send htoki to fatherpendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ hvisi îò q0 :begin usedp [q0 ] := true ; send hacki to q0 endendÀëãîðèòì ÀâåðáàõàÒåîðåìà î àëãîðèòìå ÀâåðáàõàÀëãîðèòì Àâåðáàõà ñòðîèò äåðåâî ïîèñêà â ãëóáèíó çà 4N − 2åäèíèö âðåìåíè, ïðîâîäÿ ïðè ýòîì 4|E | îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì Ñèäîíà àëãîðèòìå Ñèäîíà íå îòïðàâëÿþòñÿ ñîîáùåíèÿ ack, è çà ñ÷åòýòîãî óëó÷øàåòñÿ ñëîæíîñòü ïî âðåìåíè.

Ìàðêåð îòïðàâëÿåòñÿíåìåäëåííî, áåç çàäåðæêè íà äâå åäèíèöû âðåìåíè äëÿîæèäàíèÿ ïîäòâåðæäåíèé.Çäåñü âîçìîæíî âîçíèêíîâåíèå ñëåäóþùåé ñèòóàöèè. Âïðîöåññå p óæå ïîáûâàë ìàðêåð, è ýòîò ïðîöåññ óæå îòïðàâèëñîîáùåíèå vis ñâîåìó ñîñåäó r .Ïîçäíåå ìàðêåð äîñòàåòñÿ ïðîöåññó r , íî åùå äî òîãî, êàê visîò p äîñòèãëî r . Òîãäà r ìîæåò ïåðåäàòü ìàðêåð ïðîöåññó p ïîñòÿãèâàþùåìó ðåáðó.Àëãîðèòì Ñèäîíà×òîáû ñïðàâèòüñÿ ñ òàêîé ñèòóàöèåé, ïðîöåññ p çàïèñûâàåò (âïåðåìåííóþ lastp ) òåõ ñîñåäåé, êîòîðûì îí â ïîñëåäíþþî÷åðåäü îòïðàâëÿë ìàðêåð.Êîãäà ìàðêåð ïðîõîäèò òîëüêî ïî ðåáðàì äåðåâà, ïðîöåññ pïîëó÷àåò â î÷åðåäíîé ðàç ìàðêåð îò òîãî ñàìîãî ñîñåäà lastp .

Àâ òîì ñöåíàðèè, êîòîðûé áûë îïèñàí âûøå, p ïîëó÷àåò ìàðêåðîò äðóãîãî ñîñåäà, à èìåííî îò r .  ýòîì ñëó÷àå ìàðêåðèãíîðèðóåòñÿ, íî p ïîìå÷àåò ðåáðî rp êàê èñïîëüçîâàííîå, êàêáóäòî ïî íåìó áûëî ïîëó÷åíî ñîîáùåíèå vis îò r .Ïðîöåññ r ïîëó÷àåò îò p ñîîáùåíèå vis, ïîñëå òîãî êàê îíïåðåäàë ìàðêåð ïðîöåññó p , ò. å. r ïîëó÷àåò ñîîáùåíèå vis îòñâîåãî ñîñåäà lastr .

Òîãäà r âåäåò ñåáÿ òàê, êàê åñëè áû îíâîîáùå íå ïåðåäàâàë ìàðêåð ïðîöåññó p , à èìåííî, r âûáèðàåòñëåäóþùåãî ñîñåäà è ïåðåäàåò åìó ìàðêåð.Àëãîðèòì Ñèäîíàvarusedp [q]fatherplastp: bool init false for each q ∈ Neighp ;(* Óêàçûâàåò, îòïðàâëÿë ëè p ìàðêåð ïðîöåññó q *): process init udef ;: process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;forall r ∈ Neighp do send vis to r ;usedp [q] := true ; lastp := q ; send tok to qendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ vis îò q0 :begin usedp [q0 ] := true ;if q0 = lastp then (* Èñòîëêîâûâàòü êàê ñîîáùåíèå tokforward tok message as upon receipt of tok messageendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ tok îò q0 :begin if lastp 6= udef and lastp 6= q0 then usedp [q0 ] := true(* Ýòî ñòÿãèâàþùåå ðåáðî, èñòîëêîâûâàòü êàê ñîîáùåíèå vis *)else(* Ïîñòóïàòü, êàê â ïðåäûäóùåì àëãîðèòìå *)begin if fatherp = udef thenbegin fatherp := q0 ;forall r ∈ Neighp \{fatherp } do send vis to rend ;if p èíèöèàòîð and ∀q ∈ Neighp : usedp [q]then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin if fatherp 6= q0 ∧ ¬usedp [q0 ]then q := q0else choose q ∈ Neighp \ {fatherp }with ¬usedp [q] ;usedp [q] := true ; lastp := q ; send tok to qendelse beginendusedp [fatherp ] := true ; sendtokto fatherpÀëãîðèòì ÑèäîíàÒåîðåìà î àëãîðèòìå ÑèäîíàÀëãîðèòì Ñèäîíà ñòðîèò DFS äåðåâî çà 2N − 2 åäèíèöûâðåìåíè, èñïîëüçóÿ 4|E | îáìåíîâ ñîîáùåíèÿìè.Çàäà÷è1.

Ïðåäïîëîæèì, ÷òî åñòü æåëàíèå èñïîëüçîâàòü âîëíîâîéàëãîðèòì â ñåòè, â êîòîðîé âîçìîæíî äóáëèðîâàíèåñîîáùåíèé.IIÊàêèå èçìåíåíèÿ íóæíî âíåñòè â àëãîðèòì ýõà?Êàêèå èçìåíåíèÿ íóæíî âíåñòè â àëãîðèòì Ôèííà?2. Àäàïòèðóéòå àëãîðèòì ýõà äëÿ âû÷èñëåíèÿ ñóììû âõîäíûõäàííûõ âñåõ ïðîöåññîâ.ÊÎÍÅÖ ËÅÊÖÈÈ 7..