Лекция 10. Задача избрания лидера. Нижние оценки. Оптимальные выборы. Алгоритм GHS и Корача-Каттена-Морана, страница 4

Ïîýòîìó p çàïóñêàåò ïðîöåäóðó changeroot .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(9) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hreport, ωi îò q :begin if q 6= fatherpthen (* îòâåòèòü íà ñîîáùåíèå initiate *)begin if ω < bestwtp thenbegin bestwtp := ω ; bestchp := q end;recp := recp + 1 ; reportendendelse (* ðåáðî pq íà ïóòè â ñòåðæåíü *)if statep = findthen îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if ω > bestwtpthen changerootelse if ω = bestwtp = ∞ then stop ïðîòèâíîì ñëó÷àå îáúåäèíåíèå ôðàãìåíòà, ê êîòîðîìó ïðèíàäëåæèò p , ñ¾ðàâíîïðàâíûì¿ ôðàãìåíòîì áóäåò ïðîâîäèòüñÿ ïî òó ñòîðîíó ôðàãìåíòà, íàêîòîðîé ëåæèò óçåë q , è ïîýòîìó äàííûå, ñîáðàííûå p íåàêòóàëüíû.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(10) procedure changeroot:begin if stachp [bestchp ] = branchthen send hchangerooti to bestchpelse begin send hconnect, level p i to bestchp ;stachp [bestchp ] := branchendendÝòà ïðîöåäóðà èíèöèèðóåò îáúåäèíåíèå ôðàãìåíòà ïîíàéäåííîìó èñõîäÿùåìó ðåáðó íàèìåíüøåãî âåñà.

Ñîîáùåíèåhchangerooti îòïðàâëÿåòñÿ ïî íàïðàâëåíèþ ê èñõîäÿùåìóðåáðó íàèìåíüøåãî âåñà äî òåõ ïîð, ïîêà...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(10) procedure changeroot:begin if stachp [bestchp ] = branchthen send hchangerooti to bestchpelse begin send hconnect, level p i to bestchp ;stachp [bestchp ] := branchendend... ýòî ñîîáùåíèå íå äîñòèãíåò òîãî óçëà, èç êîòîðîãî èñõîäèòðåáðî íàèìåíüøåãî âåñà. Òîãäà èç ýòîãî óçëà â ñîñåäíèéôðàãìåíò îòïðàâëÿåòñÿ ïðåäëîæåíèå hconnect, levelp i îáîáúåäèíåíèè.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(11) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hchangerooti:begin changeroot endÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÒàêèì îáðàçîì êàæäûé ëîêàëüíûé àëãîðèòì ìîæåò âûïîëíÿòüîäíî èç 10 äåéñòâèé (1)(10) ñ èñïîëüçîâàíèåì ïðîöåäóð test ,report , changeroot .Èç ïîäðîáíîãî îïèñàíèÿ àëãîðèòìà äîëæíî áûòü ÿñíî, ÷òîðåáðî, ïî êîòîðîìó èç ôðàãìåíòà îòïðàâëÿåòñÿ ñîîáùåíèåhconnect, Li äåéñòâèòåëüíî ÿâëÿåòñÿ èñõîäÿùèì èç ôðàãìåíòàðåáðîì íàèìåíüøåãî âåñà.

Îòñþäà ñëåäóåò, ÷òî MST áóäåòïîñòðîåíî ïðàâèëüíî, åñëè êàæäûé ôðàãìåíò äåéñòâèòåëüíîîòïðàâëÿåò òàêîå ñîîáùåíèå è ñîåäèíÿåòñÿ ñ äðóãèìôðàãìåíòîì, íåñìîòðÿ íà îæèäàíèå, ïðåäóñìîòðåííîå äàííûìàëãîðèòìîì.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÒåîðåìà.Àëãîðèòì GHS âû÷èñëÿåò ìèíèìàëüíîå îñòîâíîå äåðåâî,èñïîëüçóÿ ïðè ýòîì íå áîëåå 5N log N + 2|E | îáìåíîâñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Àëãîðèòì ïîñòðîèò MST, åñëè ìû äîêàæåì, ÷òî îí íå áóäåòçàáëîêèðîâàí.Ïîòåíöèàëüíàÿ âîçìîæíîñòü äëÿ âçàèìíîé áëîêèðîâêèâîçíèêàåò â òåõ ñèòóàöèÿõ, êîãäà óçëû èëè ôðàãìåíòû äîëæíûïðåáûâàòü â îæèäàíèè òîãî, ÷òî îïðåäåëåííûå óñëîâèÿ áóäóòâûïîëíåíû â äðóãîì óçëå èëè â äðóãîì ôðàãìåíòå.

Îæèäàíèå âñòåðæíåâûõ óçëàõ, ñâÿçàííîå ñ ñîîáùåíèÿìè hreport, ωi, íåïðèâîäèò ê áëîêèðîâêå, ïîòîìó ÷òî êàæäûé ñòåðæíåâîé óçåëðàíî èëè ïîçäíî ïîëó÷èò ñâîäêè îò âñåõ ñâîèõ ïðååìíèêîâ(åñëè òîëüêî âåñü ôðàãìåíò öåëèêîì íå ïðåáûâàåò â îæèäàíèèäðóãîãî ôðàãìåíòà), ïîñëå ÷åãî óêàçàííîå ñîîáùåíèå áóäåòîáðàáîòàíî.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÄîêàçàòåëüñòâî.Ðàññìîòðèì ñëó÷àé, êîãäà ñîîáùåíèå, îòïðàâëåííîå èçôðàãìåíòà F1 = (level 1 , name 1 ) , äîñòèãàåò íåêîòîðîãî óçëàôðàãìåíòà F2 = (level 2 , name 2 ) .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÄîêàçàòåëüñòâî.Ðàññìîòðèì ñëó÷àé, êîãäà ñîîáùåíèå, îòïðàâëåííîå èçôðàãìåíòà F1 = (level 1 , name 1 ) , äîñòèãàåò íåêîòîðîãî óçëàôðàãìåíòà F2 = (level 2 , name 2 ) .Ñîîáùåíèå hconnect, level 1 i äîëæíî îæèäàòü îáðàáîòêè, åñëèlevel 1 ≥ level 2 è íèêàêîå ñîîáùåíèå hconnect, level 2 i íå áûëîîòïðàâëåíî ïî òîìó æå ñàìîìó ðåáðó èç ôðàãìåíòà F2 (ñì.

(2)).Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÄîêàçàòåëüñòâî.Ñîîáùåíèå htest, level 1 , name 1 i äîëæíî îæèäàòü îáðàáîòêè,åñëè level 1 > level 2 (ñì. (5)). Âî âñåõ òåõ ñëó÷àÿõ, êîãäàôðàãìåíò F1 îæèäàåò ôðàãìåíò F2 , âûïîëíÿåòñÿ îäíî èçñëåäóþùèõ óñëîâèé:1. level 1 > level 2 ;2. level 1 = level 2 ∧ ω(eF1 ) > ω(eF2 ) ;3.

level 1 = level 2 ∧ ω(eF1 ) = ω(eF2 ) è F2 âñå åùå ïðåáûâàåò âïîèñêå èñõîäÿùåãî èç ýòîãî ôðàãìåíòà ðåáðà íàèìåíüøåãîâåñà. (Êîëü ñêîðî eF1 ÿâëÿåòñÿ ðåáðîì, èñõîäÿùèì èç F2 ,íåðàâåíñòâî ω(eF2 ) > ω(eF1 ) âûïîëíÿòüñÿ íå áóäåò.)Òàêèì îáðàçîì, âçàèìíàÿ áëîêèðîâêà ïî çàìêíóòîìó öèêëóíåâîçìîæíà.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÄîêàçàòåëüñòâî.Îñòàåòñÿ îöåíèòü ñëîæíîñòü àëãîðèòìà.IÎöåíèòå, ñêîëüêî ñîîáùåíèé êàæäîãî òèïà îòïðàâëÿåòñÿïðîöåññàìè ïî õîäó ðàáîòû àëãîðèòìà â ñåòè ñ N óçëàìè è|E | ðåáðàìè.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÄîêàçàòåëüñòâî.Îñòàåòñÿ îöåíèòü ñëîæíîñòü àëãîðèòìà.IÎöåíèòå, ñêîëüêî ñîîáùåíèé êàæäîãî òèïà îòïðàâëÿåòñÿïðîöåññàìè ïî õîäó ðàáîòû àëãîðèòìà â ñåòè ñ N óçëàìè è|E | ðåáðàìè.IÍà îñíîâàíèè ýòîé îöåíêè ïîêàæèòå, ÷òî ñëîæíîñòüàëãîðèòìà GHS ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè íåïðåâîñõîäèò âåëè÷èíû 2N log N + 5|E |.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÌåæäó çàäà÷åé î âûáîðàõ è çàäà÷åé îáõîäà ñåòè åñòü òåñíàÿâçàèìîñâÿçü.

Ïîýòîìó ìîæíî èñïîëüçîâàòü îáùèé ìåòîäïîñòðîåíèÿ ýôôåêòèâíîãî àëãîðèòìà èçáðàíèÿ ëèäåðà äëÿïðîèçâîëüíîãî êëàññà ñåòåé íà îñíîâå âñÿêîãî àëãîðèòìàîáõîäà ñåòåé. îñíîâó àëãîðèòìà Êîðà÷àÊàòòåíàÌîðàíà ïîëîæåíû èäåèäâóõ ìåòîäîâ:IIìåòîäà óãàñàíèÿ,àëãîðèòìà Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÑõîäñòâî ñ ìåòîäîì óãàñàíèÿ ïðîÿâëÿåòñÿ âòîì, ÷òî èíèöèàòîðû âûáîðîâ ïðèñòóïàþò êîáõîäàì ñåòè, èñïîëüçóÿ ìàðêåðû, ïîìå÷åííûå èõîòëè÷èòåëüíûìè ïðèçíàêàìè. ïðîöåññå îáõîäà ïðîöåññû ìîãóò ïîãëîùàòüìàðêåðû.

È åñëè îáõîä çàâåðøèòñÿ, òî èíèöèàòîðýòîãî îáõîäà áóäåò ñ÷èòàòüñÿ èçáðàííûì.Íî äëÿ ýòîãî çàâåðøèòüñÿ äîëæåí òîëüêî îäèíîáõîä. Âñå îñòàëüíûå îáõîäû äîëæíû óãàñíóòü.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíà×òîáû ¾ãàñèòü¿ îáõîäû, àëãîðèòì îïåðèðóåò íà ðàçíûõóðîâíÿõ , ïîäîáíî òîìó êàê àëãîðèòìÏåòåðñîíà/ÄîëåâàÊëåéâàÐîäå ðàçáèâàåò ñâîå âû÷èñëåíèåíà òóðû.Åñëè çàïóùåíû ïî êðàéíåé ìåðå äâà îáõîäà, òî îäèí èçìàðêåðîâ ðàíî èëè ïîçäíî äîñòèãíåò òîãî ïðîöåññà, â êîòîðîìóæå óñïåë ïîáûâàòü äðóãîé.

Òîãäà îáõîä, êîòîðûé ïðîâîäèòñÿïðè ïîìîùè âíîâü ïðèáûâøåãî ìàðêåðà, áóäåò ïðåðâàí.Öåëü ðàáîòû àëãîðèòìà ñîñòîèò â òîì, ÷òîáû ïðèâåñòè äâåìàðêåðà âìåñòå â îäèí ïðîöåññ, ãäå îíè áóäóò ïîäàâëåíû, èïîñëå ýòîãî ìîæåò íà÷àòüñÿ íîâûé îáõîä.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 1.Âìåñòî òóðîâ â àëãîðèòìå Êîðà÷àÊàòòåíàÌîðàíàèñïîëüçóþòñÿ óðîâíè ; äâå ìàðêåðà äàþò íà÷àëî íîâîìó îáõîäóòîëüêî â òîì ñëó÷àå, åñëè îíè íàõîäÿòñÿ íà îäíîì è òîì æåóðîâíå, è ïðè ýòîì óðîâåíü âíîâü çàïóùåííîãî îáõîäà áóäåò íàåäèíèöó áîëüøå.Óðîâåíü ïðîöåññà ýòî óðîâåíü òîãî ìàðêåðà, îáõîä êîòîðîãîîí ïîääåðæèâàåò.

Óðîâåíü ïðîöåññà ìîæåò èçìåíÿòüñÿ ïðèïîñåùåíèè ïðîöåññà äðóãèìè ìàðêåðàìè.Åñëè êàêîé-ëèáî ìàðêåð âñòðå÷àåòñÿ ñ äðóãèì ìàðêåðîì áîëååâûñîêîãî óðîâíÿ èëè äîñòèãàåò óçëà, êîòîðûé óæå ïîñåòèëìàðêåð áîëåå âûñîêîãî óðîâíÿ, òî ýòîò ïðèáûâøèé ìàðêåðïðîñòî ïîäàâëÿåòñÿ áåç âñÿêîãî âëèÿíèÿ íà ìàðêåð áîëååâûñîêîãî óðîâíÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 2.×òîáû ïðèâåñòè ìàðêåðû îäíîãî è òîãî æå óðîâíÿ ñîâìåñòíî âîäèí ïðîöåññ, êàæäîìó ìàðêåðó ïðåäïèñûâàåòñÿ îäèí èç òðåõðåæèìîâ: çàõâàò (annex), ïîãîíÿ (chase) èëè îæèäàíèå .Ìàðêåð èíèöèèðóåòñÿ â ðåæèìå çàõâàòà, è â ýòîì ðåæèìå îíïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà.Âçàèìîäåéñòâèå ñ àëãîðèòìîì îáõîäà ïðîèñõîäèò çà ñ÷åòîáðàùåíèÿ ê ôóíêöèè trav : ýòà ôóíêöèÿ ëèáî óêàçûâàåò òîãîñîñåäà, êîòîðîìó íóæíî ïåðåïðàâèòü ìàðêåð, ëèáî çàÿâëÿåò îïðèíÿòèè ðåøåíèÿ, åñëè äàííûé îáõîä çàâåðøèëñÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 3.Ìàðêåð â ðåæèìå çàõâàòà ïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà, ïîêàíå ñëîæèòñÿ îäíà èç ñëåäóþùèõ ñèòóàöèé.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 3.Ìàðêåð â ðåæèìå çàõâàòà ïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà, ïîêàíå ñëîæèòñÿ îäíà èç ñëåäóþùèõ ñèòóàöèé.1.

Àëãîðèòì îáõîäà çàâåðøåí, è ïðîöåññ ñòàíîâèòñÿ ëèäåðîì.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 3.Ìàðêåð â ðåæèìå çàõâàòà ïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà, ïîêàíå ñëîæèòñÿ îäíà èç ñëåäóþùèõ ñèòóàöèé.1. Àëãîðèòì îáõîäà çàâåðøåí, è ïðîöåññ ñòàíîâèòñÿ ëèäåðîì.2. Ìàðêåð ïîäàâëÿåòñÿ â óçëå áîëåå âûñîêîãî óðîâíÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 3.Ìàðêåð â ðåæèìå çàõâàòà ïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà, ïîêàíå ñëîæèòñÿ îäíà èç ñëåäóþùèõ ñèòóàöèé.1. Àëãîðèòì îáõîäà çàâåðøåí, è ïðîöåññ ñòàíîâèòñÿ ëèäåðîì.2. Ìàðêåð ïîäàâëÿåòñÿ â óçëå áîëåå âûñîêîãî óðîâíÿ.3.

Ìàðêåð äîñòèã óçëà, â êîòîðîì åãî îæèäàåò äðóãîé ìàðêåðòîãî æå óðîâíÿ; òîãäà îáà ìàðêåðà ïîäàâëÿþòñÿ, è èçýòîãî óçëà íà÷èíàåòñÿ íîâûé îáõîä.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 3.Ìàðêåð â ðåæèìå çàõâàòà ïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà, ïîêàíå ñëîæèòñÿ îäíà èç ñëåäóþùèõ ñèòóàöèé.1. Àëãîðèòì îáõîäà çàâåðøåí, è ïðîöåññ ñòàíîâèòñÿ ëèäåðîì.2.

Ìàðêåð ïîäàâëÿåòñÿ â óçëå áîëåå âûñîêîãî óðîâíÿ.3. Ìàðêåð äîñòèã óçëà, â êîòîðîì åãî îæèäàåò äðóãîé ìàðêåðòîãî æå óðîâíÿ; òîãäà îáà ìàðêåðà ïîäàâëÿþòñÿ, è èçýòîãî óçëà íà÷èíàåòñÿ íîâûé îáõîä.4. Ìàðêåð äîñòèã óçëà òîãî æå óðîâíÿ, êîòîðûé ïîñåòèëïîñëåäíèì ìàðêåð ñ áîëüøèì îòëè÷èòåëüíûì ïðèçíàêîìèëè ìàðêåð â ðåæèìå ïîãîíè; òîãäà íàø ìàðêåð ïåðåõîäèòâ ðåæèì îæèäàíèÿ è îñòàåòñÿ â ýòîì óçëå;Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 3.Ìàðêåð â ðåæèìå çàõâàòà ïîä÷èíÿåòñÿ àëãîðèòìó îáõîäà, ïîêàíå ñëîæèòñÿ îäíà èç ñëåäóþùèõ ñèòóàöèé.1.

Àëãîðèòì îáõîäà çàâåðøåí, è ïðîöåññ ñòàíîâèòñÿ ëèäåðîì.2. Ìàðêåð ïîäàâëÿåòñÿ â óçëå áîëåå âûñîêîãî óðîâíÿ.3. Ìàðêåð äîñòèã óçëà, â êîòîðîì åãî îæèäàåò äðóãîé ìàðêåðòîãî æå óðîâíÿ; òîãäà îáà ìàðêåðà ïîäàâëÿþòñÿ, è èçýòîãî óçëà íà÷èíàåòñÿ íîâûé îáõîä.4. Ìàðêåð äîñòèã óçëà òîãî æå óðîâíÿ, êîòîðûé ïîñåòèëïîñëåäíèì ìàðêåð ñ áîëüøèì îòëè÷èòåëüíûì ïðèçíàêîìèëè ìàðêåð â ðåæèìå ïîãîíè; òîãäà íàø ìàðêåð ïåðåõîäèòâ ðåæèì îæèäàíèÿ è îñòàåòñÿ â ýòîì óçëå;5. Ìàðêåð äîñòèã óçëà òîãî æå óðîâíÿ, â êîòîðîì ïîñëåäíèìïîáûâàë ìàðêåð â ðåæèìå çàõâàòà ñ ìåíüøèìîòëè÷èòåëüíûì ïðèçíàêîì; òîãäà íàø ìàðêåð ïåðåõîäèò âðåæèì ïîãîíè è ïåðåïðàâëÿåòñÿ ïî òîìó æå êàíàëó, ïîêîòîðîìó áûë îòïðàâëåí ïðåäûäóùèé ìàðêåð.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 4.Ìàðêåð â ðåæèìå ïîãîíè ïåðåïðàâëÿåòñÿ â êàæäîì óçëå ïîòîìó êàíàëó, ïî êîòîðîìó áûë îòïðàâëåí ñàìûé ïîñëåäíèé èçïîñåòèâøèõ ýòîò óçåë ìàðêåðîâ, åñëè òîëüêî íå ñêëàäûâàåòñÿîäíà èç ñëåäóþùèõ ñèòóàöèé.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 4.Ìàðêåð â ðåæèìå ïîãîíè ïåðåïðàâëÿåòñÿ â êàæäîì óçëå ïîòîìó êàíàëó, ïî êîòîðîìó áûë îòïðàâëåí ñàìûé ïîñëåäíèé èçïîñåòèâøèõ ýòîò óçåë ìàðêåðîâ, åñëè òîëüêî íå ñêëàäûâàåòñÿîäíà èç ñëåäóþùèõ ñèòóàöèé.1.

Ìàðêåð äîñòèã ïðîöåññà áîëåå âûñîêîãî óðîâíÿ; òîãäàìàðêåð ïîäàâëÿåòñÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 4.Ìàðêåð â ðåæèìå ïîãîíè ïåðåïðàâëÿåòñÿ â êàæäîì óçëå ïîòîìó êàíàëó, ïî êîòîðîìó áûë îòïðàâëåí ñàìûé ïîñëåäíèé èçïîñåòèâøèõ ýòîò óçåë ìàðêåðîâ, åñëè òîëüêî íå ñêëàäûâàåòñÿîäíà èç ñëåäóþùèõ ñèòóàöèé.1. Ìàðêåð äîñòèã ïðîöåññà áîëåå âûñîêîãî óðîâíÿ; òîãäàìàðêåð ïîäàâëÿåòñÿ.2. Ìàðêåð äîñòèã ïðîöåññà, â êîòîðîì õðàíèòñÿ ìàðêåð òîãîæå óðîâíÿ, ïðåáûâàþùèé â ðåæèìå îæèäàíèÿ; òîãäà îáàìàðêåðà èçûìàþòñÿ è â ýòîì ïðîöåññå íà÷èíàåòñÿ íîâûéîáõîä.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 4.Ìàðêåð â ðåæèìå ïîãîíè ïåðåïðàâëÿåòñÿ â êàæäîì óçëå ïîòîìó êàíàëó, ïî êîòîðîìó áûë îòïðàâëåí ñàìûé ïîñëåäíèé èçïîñåòèâøèõ ýòîò óçåë ìàðêåðîâ, åñëè òîëüêî íå ñêëàäûâàåòñÿîäíà èç ñëåäóþùèõ ñèòóàöèé.1. Ìàðêåð äîñòèã ïðîöåññà áîëåå âûñîêîãî óðîâíÿ; òîãäàìàðêåð ïîäàâëÿåòñÿ.2.