Лекция 8. Волновые алгоритмы - фазовый_ Финна. Распред. алгоритмы обхода - Тарри_ в глубину_ Авербаха и Сидона (1185658), страница 4
Текст из файла (страница 4)
Ïóñòü p ñàìûé ïåðâûé èç ïîñåùåííûõìàðêåðîì ïðîöåññîâ, äëÿ êîòîðîãî íå âûïîëíÿåòñÿ ýòîïðåäïîëîæåíèå. Òàêèì ïðîöåññîì íå ìîæåò áûòü èíèöèàòîð.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Äëÿ êàæäîãî ïîñåùåííîãî ìàðêåðîì ïðîöåññàêàíàëû, èíöèäåíòíûåppâñå, èñïîëüçîâàëèñü äëÿ ïåðåäà÷èìàðêåðà â êàæäîì íàïðàâëåíèè ïî îäíîìó ðàçó.Äîïóñòèì ïðîòèâíîå. Ïóñòü p ñàìûé ïåðâûé èç ïîñåùåííûõìàðêåðîì ïðîöåññîâ, äëÿ êîòîðîãî íå âûïîëíÿåòñÿ ýòîïðåäïîëîæåíèå. Òàêèì ïðîöåññîì íå ìîæåò áûòü èíèöèàòîð.Ñîãëàñíî âûáîðó p âñå êàíàëû, èíöèäåíòíûå fatherp , áûëèèñïîëüçîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè.
Ïîýòîìóp óæå îòïðàâèë ìàðêåð â ðîäèòåëüñêóþ âåðøèíó.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Äëÿ êàæäîãî ïîñåùåííîãî ìàðêåðîì ïðîöåññàêàíàëû, èíöèäåíòíûåppâñå, èñïîëüçîâàëèñü äëÿ ïåðåäà÷èìàðêåðà â êàæäîì íàïðàâëåíèè ïî îäíîìó ðàçó.Äîïóñòèì ïðîòèâíîå. Ïóñòü p ñàìûé ïåðâûé èç ïîñåùåííûõìàðêåðîì ïðîöåññîâ, äëÿ êîòîðîãî íå âûïîëíÿåòñÿ ýòîïðåäïîëîæåíèå. Òàêèì ïðîöåññîì íå ìîæåò áûòü èíèöèàòîð.Ñîãëàñíî âûáîðó p âñå êàíàëû, èíöèäåíòíûå fatherp , áûëèèñïîëüçîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè. Ïîýòîìó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 è äëÿ êàæäîé åãîâåðøèíû 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 .
Êàê áûëî óæå óñòàíîâëåíî, ïîêàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ (ïî îäíîìó âêàæäîì íàïðàâëåíèè), è ýòî ñëóæèò îáîñíîâàíèå ñëîæíîñòè ïî÷èñëó ñîîáùåíèé.Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÒåîðåìà î êëàññè÷åñêîì àëãîðèòìå îáõîäà âãëóáèíóÊëàññè÷åñêèé àëãîðèòì ïîèñêà â ãëóáèíó ñòðîèò îñòîâíîåäåðåâî ïîèñêà â ãëóáèíó, èñïîëüçóÿ ïðè ýòîì 2|E | îáìåíîâñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Ïîñêîëüêó â îñíîâó íàøåãî àëãîðèòìà ïîëîæåí àëãîðèòìÒàððè, ìû èìååì äåëî ñ àëãîðèòìîì îáõîäà, êîòîðûéâû÷èñëÿåò îñòîâíîå äåðåâî T . Êàê áûëî óæå óñòàíîâëåíî, ïîêàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ (ïî îäíîìó âêàæäîì íàïðàâëåíèè), è ýòî ñëóæèò îáîñíîâàíèå ñëîæíîñòè ïî÷èñëó ñîîáùåíèé.Îñòàåòñÿ óáåäèòüñÿ â òîì, ÷òî äåðåâî, ïîñòðîåííîå â ðåçóëüòàòåïðèìåíåíèÿ ïðàâèëà R3, áóäåò äåðåâîì ïîèñêà â ãëóáèíó.Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÄîêàçàòåëüñòâî.Ñîãëàñíî ïðàâèëó R3 âñëåä çà ïåðâûì ïðîõîæäåíèåì ïîñòÿãèâàþùèåìó ðåáðó íåìåäëåííî ñëåäóåò ïîâòîðíîåïðîõîæäåíèå â îáðàòíîì íàïðàâëåíèè.Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÄîêàçàòåëüñòâî.Ñîãëàñíî ïðàâèëó R3 âñëåä çà ïåðâûì ïðîõîæäåíèåì ïîñòÿãèâàþùèåìó ðåáðó íåìåäëåííî ñëåäóåò ïîâòîðíîåïðîõîæäåíèå â îáðàòíîì íàïðàâëåíèè.Äîïóñòèì, ÷òî pq ýòî ñòÿãèâàþùåå ðåáðî, è p ïåðâûéïðîöåññ, âîñïîëüçîâàâøèéñÿ ýòèì ðåáðîì.
Ê òîìó ìîìåíòó,êîãäà ïðîöåññ q ïîëó÷àåò ìàðêåð îò p , ýòîò ìàðêåð óæåïîáûâàë â q (èíà÷å q çàíåñ áû â ïåðåìåííóþ fatherq ññûëêó íàp , è íàøå ðåáðî íå ìîãëî áû ñ÷èòàòüñÿ ñòÿãèâàþùèì) èusedq [p] èìååò çíà÷åíèå false (ïîñêîëüêó ïî ïðåäïîëîæåíèþ páûë ïåðâûì èç ýòèõ äâóõ ïðîöåññîâ, âîñïîëüçîâàâøèìñÿóêàçàííûì ðåáðîì).Ñëåäîâàòåëüíî, ñîãëàñíî ïðàâèëó R3, q íåìåäëåííî âîçâðàùàåòìàðêåð ïðîöåññó p .Êëàññè÷åñêèé àëãîðèòì îáõîäà â ãëóáèíóÄîêàçàòåëüñòâî.Òåïåðü ìîæíî ïîêàçàòü, ÷òîåñëè ðåáðîpqÿâëÿåòñÿñòÿãèâàþùèì, è åãî âïåðâûå èñïîëüçîâàë ïðîöåññq ∈ A[p] .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 îò âñåõ ñâîèõ ñîñåäåé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
