10 Избрание лидера в произвольных сетях - алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана (1185647)
Текст из файла
ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 9.Çàäà÷à èçáðàíèÿ ëèäåðà.Íèæíèå îöåíêè ñëîæíîñòè.Îïòèìàëüíûå âûáîðû.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS).Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíà.Çàäà÷à èçáðàíèÿ ëèäåðàÇàäà÷à èçáðàíèÿ ëèäåðà ñîñòîèò â òîì, ÷òîáû, èñõîäÿ èçêîíôèãóðàöèè, â êîòîðîé âñå ïðîöåññû ïðåáûâàþò â îäíîì èòîì æå ñîñòîÿíèè, äîñòè÷ü òàêîé êîíôèãóðàöèè, â êîòîðîéðîâíî îäèí ïðîöåññ áóäåò íàõîäèòüñÿ â ñîñòîÿíèè leader , òîãäàêàê âñå îñòàëüíûå ïðîöåññû áóäóò ïðåáûâàòü â ñîñòîÿíèè lost .ÎïðåäåëåíèåÀëãîðèòìîì èçáðàíèÿ ëèäåðà íàçûâàåòñÿ àëãîðèòì,êîòîðûé îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè.1. Êàæäûé ïðîöåññ íàäåëåí îäíèì è òåì æå ëîêàëüíûìàëãîðèòìîì.2. Àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì.3.
Àëãîðèòì äîñòèãàåò çàêëþ÷èòåëüíîé êîíôèãóðàöèè âêàæäîì âû÷èñëåíèè, è â êàæäîé çàêëþ÷èòåëüíîéêîíôèãóðàöèè ñóùåñòâóåò ðîâíî îäèí ïðîöåññ, êîòîðûéíàõîäèòñÿ â ñîñòîÿíèè leader à âñå îñòàëüíûå ïðîöåññûïðè ýòîì ïðåáûâàþò â ñîñòîÿíèè lost.Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðàÒåîðåìà.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Ñëåäñòâèå.Âñÿêèé äåöåíòðàëèçîâàííûé âîëíîâîé àëãîðèòì äëÿïðîèçâîëüíûõ ñåòåé áåç ïðåäâàðèòåëüíîé îñâåäîìëåííîñòè îñîñåäÿõ èìååò ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè, íåìåíüøóþ ÷åì Ω(|E | + N log N) .Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðà'$Ñåòü Sïðîöåññ p1~~ïðîöåññ p2&%Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðà''$Ñåòü SÑåòü Sïðîöåññ p1&ïðîöåññ p10~~~~ïðîöåññ p2$0ïðîöåññ p20%&%Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðà'$'Ñåòü SÑåòü Sïðîöåññ p1$0ïðîöåññ p10~@@~@@~ïðîöåññ p2&@@~ïðîöåññ p20%&%Îïòèìàëüíûå âûáîðûÂÎÏÐÎÑ.Ìîæíî ëè ïðîâåñòè âûáîðû ëèäåðà âïðîèçâîëüíûõ ñåòÿõ ñ èñïîëüçîâàíèåìO(|E | + N log N)îáìåíîâ ñîîáùåíèÿìè?Çàäà÷è èçáðàíèÿ ëèäåðà è ïîñòðîåíèÿ îñòîâíîãî äåðåâà òåñíîñâÿçàíû äðóã ñ äðóãîì.ÏóñòüCE ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè çàäà÷è îâûáîðàõ,à CT äëÿ ñëîæíîñòü ïîñòðîåíèÿ îñòîâíîãî äåðåâà.Îïòèìàëüíûå âûáîðûÀëãîðèòì èçáðàíèÿ ëèäåðà íà äåðåâå ðåøàåò çàäà÷ó î âûáîðàõíà äðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè.Èç ýòîé òåîðåìû ñëåäóåò, ÷òî CE ≤ CT + O(N) .Åñëè â íàøåì ðàñïîðÿæåíèè åñòü ëèäåð, òî îñòîâíîå äåðåâîìîæíî ïîñòðîèòü ñ èñïîëüçîâàíèåì 2|E | îáìåíîâ ñîîáùåíèÿìèïðè ïîìîùè öåíòðàëèçîâàííîãî àëãîðèòìà îáõîäà ñåòè.Ïîýòîìó ñïðàâåäëèâî íåðàâåíñòâî CT ≤ CE + 2|E | .Òàêèì îáðàçîì, äëÿ îïòèìàëüíîãî âûáîðà ëèäåðà íåîáõîäèìîè äîñòàòî÷íî óìåòü îïòèìàëüíî ñòðîèòü îñòîâíîå äåðåâî.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS) ñòðîèò îñòîâíîåäåðåâî ñ èñïîëüçîâàíèåì 2|E | + 5N log N îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS)Àëãîðèòì GHS îïèðàåòñÿ íà ñëåäóþùèå äîïóùåíèÿ.1.
Êàæäîìó ðåáðó ïðèïèñàí óíèêàëüíûé âåñ ω(e) . Âñå âåñàðåáåð ëèíåéíî óïîðÿäî÷åíû.2. Âñå óçëû ïðåáûâàþò ïåðâîíà÷àëüíî â ñîñòîÿíèèîöåïåíåíèÿ è ïðîáóæäàþòñÿ ïåðåä íà÷àëîì âûïîëíåíèÿàëãîðèòìà.Íåêîòîðûå óçëû ïðîáóæäàþòñÿ ñàìîïðîèçâîëüíî, äðóãèåìîãóò ïîëó÷èòü ñîîáùåíèå ïî õîäó ðàáîòû àëãîðèòìà, åùåïðåáûâàÿ â îöåïåíåíèè.Ïðè ýòîì óçåë, ïîëó÷èâøèé ñîîáùåíèå, âíà÷àëå âûïîëíÿåòïðîöåäóðó ëîêàëüíîé èíèöèàëèçàöèè, à çàòåì ïðèñòóïàåò êîáðàáîòêå ýòîãî ñîîáùåíèÿ.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÐàññìîòðèì âçâåøåííûé ãðàô G = (V , E ) , è äëÿ îáîçíà÷åíèÿâåñà ðåáðà e áóäåì èñïîëüçîâàòü çàïèñü ω(e) .Ìû áóäåì ïîëàãàòü, ÷òî êàæäîå ðåáðî èìååò óíèêàëüíûé âåñ.Âåñ îñòîâíîãî äåðåâà T â ãðàôå G ïîëàãàåòñÿ ðàâíûì ñóììåâåñîâ âñåõ N − 1 ðåáåð, âõîäÿùèõ â ñîñòàâ T .Ïðè ýòîì T íàçûâàåòñÿ ìèíèìàëüíûì îñòîâíûì äåðåâîì , èëèñîêðàùåííî MST, åñëè íè îäíî îñòîâíîå äåðåâî íå èìååò âåñìåíüøèé, ÷åì T .Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÓòâåðæäåíèå 9.1.Åñëè âñå âåñà ðåáåð ïîïàðíî ðàçëè÷íû, òî ñóùåñòâóåò òîëüêîîäíî MST.Äîêàçàòåëüñòâî.Äîïóñòèì, ÷òî åñòü äâà MST T1 è T2 , ïðè÷åì T1 6= T2 .Ðàññìîòðèì ðåáðî e íàèìåíüøåãî âåñà, êîòîðîå ñîäåðæèòñÿ âîäíîì èç ýòèõ äåðåâüåâ, íî íå ñîäåðæèòñÿ â äðóãîì.Ïðåäïîëîæèì, ÷òî e ∈ T1 .
Òîãäà T2 ∪ {e} ñîäåðæèò öèêë, è,ïîñêîëüêó â äåðåâå T1 íåò öèêëîâ, õîòÿ áû îäíî ðåáðî ýòîãîöèêëà, ñêàæåì, ðåáðî e 0 , íå ñîäåðæèòñÿ â T1 . Ñîãëàñíîâûáîðó ðåáðà e , ñïðàâåäëèâî íåðàâåíñòâî ω(e) < ω(e 0 ) .Íî òîãäà äåðåâî T2 ∪ {e} \ {e 0 } èìååò âåñ ìåíüøèé, ÷åì T2 ,âîïðåêè òîìó, ÷òî T2 ÿâëÿåòñÿ MST.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÔðàãìåíò ïðîèçâîëüíîå ïîääåðåâî MST.
Ðåáðî e íàçûâàåòñÿèñõîäÿùèì ðåáðîì ôðàãìåíòà F , åñëè îäèí èç êîíöîâ eïðèíàäëåæèò F , à äðóãîé íåò.Óòâåðæäåíèå 9.2.Åñëè F ÿâëÿåòñÿ ôðàãìåíòîì, è e ðåáðî íàèìåíüøåãî âåñà,èñõîäÿùåå èç F , òî F ∪ {e} òàêæå ÿâëÿåòñÿ ôðàãìåíòîì.Äîêàçàòåëüñòâî.ÑÀÌÎÑÒÎßÒÅËÜÍÎ (ðóêîâîäñòâóÿñü äîêàçàòåëüñòâîìïðåäûäóùåãî óòâåðæäåíèÿ).Àëãîðèòìû íà÷èíàþò ðàáîòó, ðàñïîëàãàÿ ôðàãìåíòàìè,ñîñòîÿùèìè èç åäèíñòâåííîãî óçëà, è ïîñëåäîâàòåëüíîíàðàùèâàþò ôðàãìåíòû, äî òåõ ïîð ïîêà íå áóäåò çàâåðøåíîïîñòðîåíèå MST.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.1. Ôîðìèðóåòñÿ òàêîå ñåìåéñòâî ôðàãìåíòîâ, ÷òîîáúåäèíåíèå èõ ñîäåðæèò âñå óçëû ñåòè.2. Ïåðâîíà÷àëüíî ýòî ñåìåéñòâî ñîñòîèò èç âñåõ óçëîâ ñåòè,êàæäûé èç êîòîðûõ ðàññìàòðèâàåòñÿ êàê ãðàô ñ îäíèìóçëîì.3.
Óçëû âñÿêîãî ôðàãìåíòà âñòóïàþò âî âçàèìîäåéñòâèå ñöåëüþ âûÿâëåíèÿ èñõîäÿùåãî èç ôðàãìåíòà ðåáðà ñíàèìåíüøèì âåñîì.4. Êàê òîëüêî áóäåò îïðåäåëåíî èñõîäÿùåå èç ôðàãìåíòàðåáðî ñ íàèìåíüøèì âåñîì, äàííûé ôðàãìåíò ñîåäèíÿåòñÿñ äðóãèì ôðàãìåíòîì ïóòåì äîáàâëåíèÿ ýòîãî èñõîäÿùåãîðåáðà, êîòîðîå ñòðîèòñÿ â ðåçóëüòàòå âçàèìîäåéñòâèÿ ýòèõäâóõ ôðàãìåíòîâ.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÄëÿ ýôôåêòèâíîé ðåàëèçàöèè ýòèõ øàãîâ íóæíû.1. Èìÿ ôðàãìåíòà.×òîáû îïðåäåëèòü èñõîäÿùåå ðåáðî íàèìåíüøåãî âåñà,íåîáõîäèìî ñóìåòü ïðîâåðèòü, âûâîäèò ëè íåêîòîðîå ðåáðî çàïðåäåëû ôðàãìåíòà èëè îíî âåäåò â óçåë òîãî æå ñàìîãîôðàãìåíòà.
Äëÿ ýòîãî êàæäûé ôðàãìåíò áóäåò íàäåëåíèìåíåì, êîòîðîå áóäåò èçâåñòíî âñåì ïðîöåññàì, âõîäÿùèì âýòîò ôðàãìåíò. Ïðîöåññû áóäóò ïðîâåðÿòü, ÿâëÿåòñÿ ëè ðåáðîâíóòðåííèì èëè âíåøíèì ðåáðîì, ñðàâíåíèâàÿ èìåíàôðàãìåíòîâ, ê êîòîðûì îíè îòíîñÿòñÿ.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS2. Ñîåäèíåíèå ñòàðøåãî è ìëàäøåãî ôðàãìåíòîâ.Êîãäà äâà ôðàãìåíòà ñîåäèíÿþòñÿ, â ïðîöåññàõ õîòÿ áû îäíîãîèç ýòèõ ôðàãìåíòîâ ïðîèñõîäèò ïåðåìåíà èìåíè ôðàãìåíòà;äëÿ ýòîãî òðåáóåòñÿ, ÷òîáû èçìåíåíèå èìåíè ïðîèçîøëî âêàæäîé òî÷êå õîòÿ áû îäíîãî èç óêàçàííûõ ôðàãìåíòîâ. ×òîáûîñóùåñòâèòü ýòî èçìåíåíèå ýôôåêòèâíî, â îñíîâó ñòðàòåãèèñîåäèíåíèÿ ôðàãìåíòîâ ïîëîæåí ñëåäóþùèé ïðèíöèï:ìëàäøèé ôðàãìåíò ïðèñîåäèíÿåòñÿ ê ñòàðøåìó ôðàãìåíòó èïðèíèìàåò èìÿ ñòàðøåãî ôðàãìåíòà.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS3.
Ðàíãè ôðàãìåíòîâ.Êàæäîìó ôðàãìåíòó ñîïîñòàâëÿåòñÿ ðàíã , êîòîðûéïåðâîíà÷àëüíî ïîëàãàåòñÿ ðàâíûì 0 äëÿ ëþáîãî ôðàãìåíòà,ñîñòîÿùåãî èç îäíîãî óçëà.Ôðàãìåíò F1 ìîæåò ñîåäèíèòüñÿ ñ ôðàãìåíòîì F2 áîëååâûñîêîãî ðàíãà, ïîñëå ÷åãî íîâûé ôðàãìåíò F1 ∪ F2 áóäåòèìåòü òàêîé æå ðàíã, êàê è ôðàãìåíò F2 , è óíàñëåäóåò èìÿôðàãìåíòà F2 .Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò F2'$Èìÿ: name2ðàíã: rank2piÔðàãìåíò F1'$pj&%Èìÿ: name1&%rank2 > rank1ðàíã: rank1Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò F2Ôðàãìåíò F2'$Èìÿ: name2ðàíã: rank2pihmessagei-&%'$pjÈìÿ: name2&%rank2 > rank1ðàíã: rank2Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS3.
Ðàíãè ôðàãìåíòîâ.Ïðè ñîåäèíåíèå äâóõ ôðàãìåíòîâ îäíîãî è òîãî æå ðàíãà íîâûéôðàãìåíò áóäåò íîñèòü íîâîå èìÿ è åãî ðàíã áóäåò íà åäèíèöóïðåâîñõîäèòü ðàíã ñîåäèíåííûõ ôðàãìåíòîâ. Èìåíåìîáðàçîâàâøåãîñÿ ôðàãìåíòà áóäåò âåñ òîãî ðåáðà, êîòîðîåñîåäèíèëî äâà èñõîäíûõ ôðàãìåíòà; óêàçàííîå ðåáðî íàçîâåìñòåðæíåì íîâîãî ôðàãìåíòà. Òå äâà óçëà, êîòîðûå ñîåäèíåíûðåáðîì-ñòåðæíåì, áóäóò íàçûâàòüñÿ ñòåðæíåâûìè óçëàìè .Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò F2Èìÿ: name2ðàíã: rank'$piÔðàãìåíò F1'$pj&%Èìÿ: name1&%îäèíàêîâûé ðàíãðàíã: rankÃëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò FÔðàãìåíò F'$Èìÿ: ωijpi'$hmessage1 i-pjÈìÿ: ωijhmessage2 i&%&%ðàíã: rank + 1ðàíã: rank + 1îäèíàêîâûé ðàíãÃëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÓòâåðæäåíèå 9.3.Åñëè ñîáëþäàòü óêàçàííûå âûøå ïðàâèëà ñîåäèíåíèÿôðàãìåíòîâ, òî ñóììàðíî âî âñåõ ïðîöåññàõ ïåðåìåíà èìåíèèëè ðàíãà ñëó÷èòñÿ íå áîëåå N log N ðàç.Äîêàçàòåëüñòâî.Ðàíã âñÿêîãî ïðîöåññà íå ïîíèæàåòñÿ, è ëèøü â òîì ñëó÷àå,êîãäà îí ïîâûøàåòñÿ, ïðîöåññ âûíóæäåí ïåðåìåíèòü èìÿñâîåãî ôðàãìåíòà.Èíäóêöèåé ïî L ìîæíî óáåäèòüñÿ, ÷òî êàæäûé ôðàãìåíò ðàíãàL ñîäåðæèò íå ìåíåå 2L ïðîöåññîâ, è ïîýòîìó ìàêñèìàëüíîâîçìîæíûé ðàíã ðàâåí log N .Îòñþäà ñëåäóåò, ÷òî â êàæäîì îòäåëüíîì ïðîöåññå ðàíãñîäåðæàùåãî åãî ôðàãìåíòà ïîâûøàåòñÿ íå áîëåå log N ðàç.Çíà÷èò, îáùåå ÷èñëî ïåðåìåí èìåíè è ðàíãà ôðàãìåíòàîãðàíè÷åíî âåëè÷èíîé N log N .Còðàòåãèÿ ñîåäèíåíèÿÏóñòü ôðàãìåíò F = (FN, L) èìååò èìÿ FN è ðàíã L , è eF èñõîäÿùåå èç F ðåáðî íàèìåíüøåãî âåñà.Ïðàâèëî A.Ïðàâèëî B.Ïðàâèëî C.Åñëè eF âåäåò â ôðàãìåíò F 0 = (FN 0 , L0 ) , äëÿêîòîðîãî L < L0 , òî F ïðèñîåäèíÿåòñÿ ê F 0 , èîáðàçîâàâøèéñÿ íîâûé ôðàãìåíò ñîõðàíÿåò èìÿFN 0 è ðàíã L0 .Åñëè eF âåäåò â ôðàãìåíò F 0 = (FN 0 , L0 ) , äëÿêîòîðîãî L = L0 è eF 0 = eF , òî ýòè ôðàãìåíòàñîåäèíÿþòñÿ è îáðàçóþò îäèí íîâûé ôðàãìåíò,êîòîðûé áóäåò íîñèòü èìÿ ω(eF ) è èìåòü ðàíãL+1 . îñòàëüíûõ ñëó÷àÿõ (êîãäà L > L0 èëè L = L0 èeF 0 6= eF ) ôðàãìåíò F äîëæåí îæèäàòü, êîãäàîòêðîåòñÿ âîçìîæíîñòü ïðèìåíåíèÿ ïðàâèëà Aèëè B.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.Istatep ðåæèì ðàáîòû ïðîöåññà {sleep, find, found};Istachp [q] ñòàòóñ êàíàëà ñâÿçè {basic, branch, reject};Inamep èìÿ ôðàãìåíòà;Ibestwtp íàèìåíüøèé âåñ èñõîäÿùåãî ðåáðà;Ilevelp ðàíã ïðîöåññà;Ifatherp êàíàë, âåäóùèé â ñòåðæíåâîé óçåë ôðàãìåíòà;Itestchp , bestchp ïåðñïåêòèâíûå êàíàëû ñâÿçè ñ ñîñåäÿìè;Irec ñ÷åò÷èê.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhconnect, leveli ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç ôðàãìåíòà, ñóêàçàíèåì ðàíãà ýòîãî ôðàãìåíòà;hinitiate, level, name, statei ñîîáùåíèå, êîòîðîåîòïðàâëÿåòñÿ ïî ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èçôðàãìåíòà,ïðè âûïîëíåíèè ïðàâèëà À ïðèñîåäèíåíèÿ ôðàãìåíòàìåíüøåãî ðàíãà, à òàêæåïðè âûïîëíåíèè ïðàâèëà B îáúåäèíåíèÿ äâóõôðàãìåíòîâ îäèíàêîâîãî ðàíãà;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIIhtest, level, namei ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî¾ñâåæåìó¿ ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç óçëà, ñóêàçàíèåì èìåíè è ðàíãà ôðàãìåíòà, êîòîðîìóïðèíàäëåæèò óçåë;hrejecti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå îäíîìó è òîìó æå ôðàãìåíòó;haccepti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå ðàçíûì ôðàãìåíòàì;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhreport, bestwti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîíàïðàâëåíèþ ê ñòåðæíåâîìó óçëó ñ óêàçàíèåìíàèìåíüøåãî âåñà ¾ñâåæåãî¿ ðåáðà, èñõîäÿùåãî èç óçëà;hchangerooti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðàì ïðèñîåäèíÿåìîãî ôðàãìåíòà è óêàçûâàåò òîíàïðàâëåíèå, â êîòîðîì áóäåò ðàñïîëàãàòüñÿ ñòåðæíåâîéóçåë;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(1) Ïåðâûì äåéñòâèåì êàæäîãî ïðîöåññàÿâëÿåòñÿ èíèöèàëèçàöèÿ äàííîãî àëãîðèòìà:begin ïóñòü pq ýòî êàíàë ñâÿçè ïðîöåññà p ,èìåþùèé íàèìåíüøèé âåñ ;stachp [q] := branch ; level p := 0 ;statep := found ; recp := 0 ;send hconnect, 0i to qendÊàæäûé ïðîöåññ íà÷èíàåò ðàáîòó ñ òîãî, ÷òîïðèñâèâàåò ñåáå ñàìûé íèçêèé ðàíã,íàõîäèò èñõîäÿùåå ðåáðî íàèìåíüøåãî âåñà, èîáúÿâëÿåò î ñâîåé ãîòîâíîñòè ïðèñîåäèíèòüñÿ ê ñîñåäíåìóôðàãìåíòó.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > levelpthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qÏîñëå ïðåäëîæåíèÿ îá îáúåäèíåíèè ôðàãìåíòîâ òîò óçåë,êîòîðûé ïîëó÷èë ýòî ïðåäëîæåíèå, ïðîâåðÿåò ðàíã ñîñåäíåãîôðàãìåíòà,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qè åñëè ðàíã ñîñåäíåãî ôðàãìåíòà ìåíüøå ðàíãà òîãîôðàãìåíòà, êîòîðîìó ïðèíàäëåæèò óçåë p , òî óçåë pîòïðàâëÿåò ñîñåäíåìó ôðàãìåíòó ïðèêàç ïðèñîåäèíèòüñÿ ¾âêà÷åñòâå ïîä÷èíåííîãî¿, ïðèíÿâ èìÿ è ðàíã ñòàðøåãîôðàãìåíòà,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)endîáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qà â ïðîòèâíîì ñëó÷àå ïðîöåññ p ïðîâåðÿåò, íå áûëî ëè ðåáðîpq óæå ¾îïðîáîâàíî¿ ïðîöåññîì p ðàíåå.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qÅñëè ýòî ðåáðî íå áûëî åùå ¾îïðîáîâàíî¿ ïðîöåññîì p , òîîáðàáîòêà ïðåäëîæåíèÿ îáúåäèíèòüñÿ îòêëàäûâàåòñÿ äî òåõïîð, ïîêà ïðîöåññ p íå ïðèñòóïèò ê îöåíêå ðåáðà pq ,....Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qà èíà÷å (ò.å.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
