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

Ñîáûòèå aq ýòîåäèíñòâåííîå ñîáûòèå, äëÿ êîòîðîãî âûïîëíÿåòñÿ q ∈ NInc (aq ) ,è êîòîðîìó íå ïðåäøåñòâóåò äðóãîå ñîáûòèå a0 ,0óäîâëåòâîðÿþùåå óñëîâèþ q ∈ NInc (a ) . Çíà÷èò,q ∈ NInc (f ) =⇒ aq f .Èç îïèñàíèÿ àëãîðèòìà âèäíî, ÷òî äëÿ êàæäîãî r ∈ Inqíàéäåòñÿ ñîáûòèå e ∈ Cr , ïðåäøåñòâóþùåå aq . Îòñþäàñëåäóåò äîêàçûâàåìîå óòâåðæäåíèå.Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïðîöåññ p ïðèíèìàåò ðåøåíèå òîëüêî òîãäà, êîãäà Incp = NIncp .Ïóñòü dp ýòî ñîáûòèå ðåøåíèÿ â ïðîöåññå p ; òîãäàInc (dp ) = NInc (dp ) .Òåïåðü ìû âèäèì, ÷òî1.

p ∈ Inc (dp ) ;2. èç q ∈ Inc (dp ) ñëåäóåò q ∈ NInc (dp ) , è îòñþäà ïîëó÷àåìInq ⊆ Inc (dp ) .Ïîñêîëüêó ñåòü ñèëüíî ñâÿçíàÿ, ìû ïîëó÷àåì èñêîìîåðàâåíñòâî Inc (dp ) = P .Àëãîðèòìû îáõîäàÎñîáî èíòåðåñíû öåíòðàëèçîâàííûå âîëíîâûå àëãîðèòìû, âêîòîðûõ âñå ñîáûòèÿ âûñòðîåíû â îäíó öåïî÷êó ïðè÷èííîñëåäñòâåííîé çàâèñèìîñòè, è ðåøåíèå ïðèíèìàåò èíèöèàòîð.Âîëíîâûå àëãîðèòìû òàêîãî ðîäà íàçûâàþòñÿîáõîäà.àëãîðèòìàìèÀëãîðèòìîì îáõîäà íàçûâàåòñÿ àëãîðèòì, îáëàäàþùèéñëåäóþùèìè òðåìÿ ñâîéñòâàìè.1.  êàæäîì âû÷èñëåíèè åäèíñòâåííûé èíèöèàòîð çàïóñêàåòàëãîðèòì, îòïðàâëÿÿ îäíî-åäèíñòâåííîå ñîîáùåíèå.2. Âñÿêèé ïðîöåññ ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ ëèáîîòïðàâëÿåò ðîâíî îäíî ñîîáùåíèå, ëèáî ïðèíèìàåòðåøåíèå.3.

Àëãîðèòì çàâåðøàåò ðàáîòó â èíèöèàòîðå, è ê òîìóìîìåíòó, êîãäà ýòî ïðîèñõîäèò, êàæäîìó ïðîöåññó õîòÿ áûîäèí ðàç óäàëîñü îòïðàâèòü ñîîáùåíèå.Àëãîðèòì îáõîäà ïðîèçâîëüíûõ ñåòåéÀëãîðèòì îáõîäà ïðîèçâîëüíûõ ñâÿçíûõ ñåòåéáûë ïðåäëîæåí Òàððè â 1895.

Ýòîò àëãîðèòìîïðåäåëÿåòñÿ äâóìÿ ñëåäóþùèìè ïðàâèëàìè.R1. Ïðîöåññ íå ïåðåäàåò ìàðêåð ïî îäíîìó è òîìóæå êàíàëó äâàæäû.R2. Íå-èíèöèàòîð ïåðåäàåò ìàðêåð ñâîåéðîäèòåëüñêîé âåðøèíå (ñîñåäó, îò êîòîðîãî îíâïåðâûå ïîëó÷èë ìàðêåð) òîëüêî â òîì ñëó÷àå,êîãäà åãî íåâîçìîæíî ïåðåäàòü ïî äðóãèìêàíàëàì ñîãëàñíî ïðàâèëó R1.Àëãîðèòì ÒàððèÈíèöèàòîðHHHHHHHH@@@@@ @@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~HHHHHHHH@@@@@ @@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * HHHHtoc HHH@@@@@ @@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * HHHHHHHtoc~*@@@@@@@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * HHtoc HHHHH*~*~@@@@@@@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*toc~*~@@@@@@@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@@@@@@@@@@@@toc ~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@@@toc@@@@@@@@@* ~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@*@@@@@@@@@toc@@* ~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@*@@@@@@@@@@@* * ~~toc~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@ toc@*@@@@@@@@@*@@* * ~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@@*@@@@@@@@toc@*@@* * ~~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@@*@@@@@@@@@*@@* * ~~*~~~ tocÀëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@@*@@toc@@@@@@*@*@@* * ~~*~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@*@*@@@@@@@@*toc@*@@* * ~~*~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@*@*@@@@@@@@*@*@@* * ~~*~~*~ tocÀëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*toc*@@@*@*@@@@@@@@**@*@@* * ~~*~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*toc**@@@*@*@@@@@@@@**@*@@* * ~~*~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~***@* @@*@*@@@@@@@@**@*@@*toc* ~~*~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~***@* @@*@*@@@@@@@@**@*@@* * ~~* * ~~*~toc Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**toc* * @@@*@*@@@@@@@@***@*@@** ~~* * ~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~tocH * *HHHHHHH**~*~***@* @@*@*@@@@@@@@***@*@@** ~~* * ~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~ DECIDE!H * *HHHHHHH**~*~***@* @@*@*@@@@@@@@***@*@@** ~~* * ~~*~ Àëãîðèòì Òàððèusedp [q] : boolinit false for each q ∈ Neighp ;fatherp : process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;usedp [q] := true ; send tok to q endÄëÿ êàæäîãî ïðîöåññà ïîñëå ïðèåìà tok îò q0 :begin if fatherp = udef then fatherp := q0 ;if ∀q ∈ Neighp : usedp [q] then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin choose q ∈ Neighp \ {fatherp } with ¬usedp [q] ;usedp [q] := true ; send tok to qvarendelse beginendendusedp [fatherp ] := true ; sendtokto fatherpÀëãîðèòì ÒàððèÒåîðåìà îá àëãîðèòìå ÒàððèÀëãîðèòì Òàððè ýòî àëãîðèòì îáõîäà.Äîêàçàòåëüñòâî.Ìàðêåð ïåðåäàåòñÿ íå áîëåå îäíîãî ðàçà â êàæäîì èç äâóõíàïðàâëåíèè ïî ëþáîìó êàíàëó.

Çíà÷èò, ñîâåðøàåòñÿ íå áîëåå2|E | ïåðåäà÷ ñîîáùåíèé, è ïîýòîìó àëãîðèòì çàâåðøàåòñÿ.Êàæäûé ïðîöåññ îòïðàâëÿåò ìàðêåð ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà, è ïîýòîìó îí åãî ïîëó÷àåò ïî êàæäîìóêàíàëó íå áîëåå îäíîãî ðàçà.Åñëè ìàðêåðîì âëàäååò íå-èíèöèàòîð p , òî ïðîöåññó pïðèøëîñü ïîëó÷àòü ìàðêåð íà îäèí ðàç áîëüøå, ÷åì îòïðàâëÿòüåãî. Çíà÷èò, ÷èñëî êàíàëîâ, èíöèäåíòíûõ p , ïðåâîñõîäèò ÷èñëîêàíàëîâ, èñïîëüçîâàííûõ ýòèì ïðîöåññîì äëÿ ïåðåäà÷èìàðêåðà.

Ïîýòîìó p íå ïðèíèìàåò ðåøåíèÿ, à ïåðåäàåò ìàðêåð.Çíà÷èò, â çàêëþ÷èòåëüíîé êîíôèãóðàöèè ìàðêåð ó èíèöèàòîðà,è îí ïðèíèìàåò ðåøåíèå.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Âñå êàíàëû, èíöèäåíòíûå èíèöèàòîðó áûëèèñïîëüçîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè.Êàæäûé êàíàë áûë èñïîëüçîâàí èíèöèàòîðîì äëÿ ïåðåäà÷èìàðêåðà, èáî â ïðîòèâíîì ñëó÷àå àëãîðèòì íå çàâåðøàåòñÿ.Èíèöèàòîðó ïðèøëîñü ïîëó÷àòü ìàðêåð ñòîëüêî æå ðàç,ñêîëüêî è îòïðàâëÿòü åãî.À ïîñêîëüêó ïîëó÷àòü åãî ïðèõîäèëîñü ïî ðàçíûì êàíàëàì, òîìàðêåð áûë ïîëó÷åí ïî îäíîìó ðàçó ñ èñïîëüçîâàíèåì êàæäîãîêàíàëà.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Äëÿ êàæäîãî ïîñåùåííîãî ìàðêåðîì ïðîöåññàêàíàëû, èíöèäåíòíûåppâñå, èñïîëüçîâàëèñü äëÿ ïåðåäà÷èìàðêåðà â êàæäîì íàïðàâëåíèè ïî îäíîìó ðàçó.Äîïóñòèì ïðîòèâíîå. Ïóñòü p ñàìûé ïåðâûé èç ïîñåùåííûõìàðêåðîì ïðîöåññîâ, äëÿ êîòîðîãî íå âûïîëíÿåòñÿ ýòîïðåäïîëîæåíèå.

Òàêèì ïðîöåññîì íå ìîæåò áûòü èíèöèàòîð.Ñîãëàñíî âûáîðó p âñå êàíàëû, èíöèäåíòíûå fatherp , áûëèèñïîëüçîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè. Ïîýòîìóp óæå îòïðàâèë ìàðêåð â ðîäèòåëüñêóþ âåðøèíó.Çíà÷èò, p èñïîëüçîâàë âñå ñâîè êàíàëû äëÿ îòïðàâëåíèÿìàðêåðà. Ò.ê. ìàðêåð âåðíóëñÿ ê èíèöèàòîðó, ïðîöåññó pïðèøëîñü ïîëó÷àòü åãî ñòîëü æå ÷àñòî, ñêîëü è îòïðàâëÿòü.Íî òîãäà ïî êàæäîìó êàíàëó ïðîöåññ p ïîëó÷àë ìàðêåð ïîîäíîìó ðàçó âîïðåêè ñäåëàííîìó ïðåäïîëîæåíèþ.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Ìàðêåð ïîñåòèë âñå ïðîöåññû.Åñëè áû íàøëèñü ïðîöåññû, êîòîðûå ìàðêåðó íå óäàëîñüïîñåòèòü, òî ýòî îçíà÷àëî áû, ÷òî äëÿ íåêîòîðîé ïàðûñîñåäíèõ ïðîöåññîâ p è q ìàðêåðó óäàëîñü ïîáûâàòü â p , íî íåóäàëîñü ïîñåòèòü q .Íî ýòî ïðîòèâîðå÷èò òîìó, ÷òî ïðîöåññó p ïðèøëîñüèñïîëüçîâàòü êàæäûé êàíàë â îáîèõ íàïðàâëåíèÿõ. Çíà÷èòìàðêåð ïîáûâàë âî âñåõ ïðîöåññàõ, è âñå êàíàëû áûëèçàäåéñòâîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè.Àëãîðèòì ÒàððèÊàæäîå âû÷èñëåíèå àëãîðèòìà Òàððè çàäàåò â ñåòè îñòîâíîåäåðåâî (ïî÷åìó? ).Êîðíåì äåðåâà ñëóæèò èíèöèàòîð, è êàæäûé íå-èíèöèàòîð p êìîìåíòó çàâåðøåíèÿ âû÷èñëåíèÿ óæå çàíîñèò â ïåðåìåííóþfatherp ññûëêó íà ðîäèòåëüñêóþ âåðøèíó â ýòîì äåðåâå.Åñëè òðåáóåòñÿ, ÷òîáû êàæäûé ïðîöåññ îáëàäàë (ê ìîìåíòóçàâåðøåíèÿ âû÷èñëåíèÿ) ñâåäåíèÿìè î òîì, êàêèå èç åãîñîñåäåé ÿâëÿþòñÿ ñûíîâíèìè âåðøèíàìè â ýòîì äåðåâå, òîýòîãî ìîæíî äîñòè÷ü îòïðàâëÿÿ ñïåöèàëüíîå ñîîáùåíèåïðîöåññó fatherp .Àëãîðèòìû îáõîäà â ãëóáèíóÎñîáî èíòåðåñíû àëãîðèòìû ïîñòðîåíèÿ îñòîâíûõ äåðåâüåâ, óêîòîðûõ êàæäîå ñòÿãèâàþùåå ðåáðî ñîåäèíÿåò äâå âåðøèíû,îäíà èç êîòîðûõ âûñòóïàåò â ðîëè ïðåäøåñòâåííèêà äðóãîé.Ñòÿãèâàþùåå ðåáðî ýòî ðåáðî, íå ïðèíàäëåæàùåå îñòîâíîìóäåðåâó.Äëÿ îñòîâíîãî äåðåâà T ñåòè G è äëÿ êàæäîé åãî âåðøèíû pçàïèñü T [p] áóäåò îáîçíà÷àòü ìíîæåñòâî âåðøèí ïîääåðåâà,ðàñòóùåãî èç p , à çàïèñü A[p] ìíîæåñòâî ïðåäøåñòâåííèêîâp , ëåæàùèõ â äåðåâå T íà ïóòè èç êîðíÿ â p .

Çàìåòèì, ÷òîq ∈ T [p] ⇐⇒ p ∈ A[q] .ÎïðåäåëåíèåÊîðíåâîå îñòîâíîå äåðåâî T ñåòè G íàçûâàåòñÿ äåðåâîìïîèñêà â ãëóáèíó , åñëè äëÿ êàæäîãî ñòÿãèâàþùåãî ðåáðà pqâûïîëíÿåòñÿ ñîîòíîøåíèå q ∈ T [p] ∨ q ∈ A[p] .Àëãîðèòìû îáõîäà â ãëóáèíóÈíèöèàòîðHHHHHHHH@@@@@ @@@@@@@@@@ Àëãîðèòìû îáõîäà â ãëóáèíóÈíèöèàòîðHHHHHHHH@@ ñòÿãèâàþùåå@ ðåáðî@@ @@@@@@@@@@ Àëãîðèòìû îáõîäà â ãëóáèíóÄåðåâî îáõîäà â ãëóáèíóÈíèöèàòîðHHHHHHHH@@@@@ @@@@@@@@@@ Àëãîðèòìû îáõîäà â ãëóáèíóÈíèöèàòîðHHHHHHHHHHHHHHH@@@@@ @@@@@@@@@@ Àëãîðèòìû îáõîäà â ãëóáèíóÍå ÿâëÿåòñÿ äåðåâîì îáõîäà â ãëóáèíóÈíèöèàòîðHHHHHHHHHHHHHHH@@@@@ @@@@@@@@@@ Àëãîðèòìû îáõîäà â ãëóáèíóÇàäà÷à.Ïðèâåäèòå ïðèìåð ñåòè, äëÿ êîòîðîé îñòîâíîå äåðåâî,ïîñòðîåííîå àëãîðèòìîì Òàððè, íå ÿâëÿåòñÿ äåðåâîì ïîèñêà âãëóáèíó.Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÊëàññè÷åñêèé àëãîðèòì ïîèñêà â ãëóáèíóïîëó÷àåòñÿ èç àëãîðèòìà Òàððè, â êîòîðîìñâîáîäà âûáîðà î÷åðåäíîãî ñîñåäà äëÿ ïåðåäà÷èåìó ìàðêåðà îãðàíè÷åíà òðåòüèì ïðàâèëîìñëåäóþùåãî âèäà.R3.

Âñÿêèé ðàç, êîãäà ïðîöåññ ïîëó÷àåò ìàðêåð,îí âîçâðàùàåò åãî íàçàä ïî òîìó æå êàíàëó,åñëè ýòî íå ïðîòèâîðå÷èò ïðàâèëàì R1 è R2.Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóusedp [q] : boolinit false for each q ∈ Neighp ;fatherp : process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;usedp [q] := true ; send tok to q endÄëÿ êàæäîãî ïðîöåññà ïîñëå ïðèåìà tok îò q0 :begin if fatherp = udef then fatherp := q0 ;if ∀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 tok to qvarendelse beginendusedp [fatherp ] := true ; sendtokto fatherpendÊëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÒåîðåìà î êëàññè÷åñêîì àëãîðèòìå îáõîäà âãëóáèíóÊëàññè÷åñêèé àëãîðèòì ïîèñêà â ãëóáèíó ñòðîèò îñòîâíîåäåðåâî ïîèñêà â ãëóáèíó, èñïîëüçóÿ ïðè ýòîì 2|E | îáìåíîâñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Ïîñêîëüêó â îñíîâó íàøåãî àëãîðèòìà ïîëîæåí àëãîðèòìÒàððè, ìû èìååì äåëî ñ àëãîðèòìîì îáõîäà, êîòîðûéâû÷èñëÿåò îñòîâíîå äåðåâî T .