Лекция 10. Задача избрания лидера. Нижние оценки. Оптимальные выборы. Алгоритм GHS и Корача-Каттена-Морана (1185660)
Текст из файла
ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 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)îáìåíîâ ñîîáùåíèÿìè?Îïòèìàëüíûå âûáîðûÂÎÏÐÎÑ.Ìîæíî ëè ïðîâåñòè âûáîðû ëèäåðà âïðîèçâîëüíûõ ñåòÿõ ñ èñïîëüçîâàíèåìO(|E | + N log N)îáìåíîâ ñîîáùåíèÿìè?Çàäà÷è èçáðàíèÿ ëèäåðà è ïîñòðîåíèÿ îñòîâíîãî äåðåâà òåñíîñâÿçàíû äðóã ñ äðóãîì.ÏóñòüCE ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè çàäà÷è îâûáîðàõ,à CT äëÿ ñëîæíîñòü ïîñòðîåíèÿ îñòîâíîãî äåðåâà.Îïòèìàëüíûå âûáîðûÀëãîðèòì èçáðàíèÿ ëèäåðà íà äåðåâå ðåøàåò çàäà÷ó î âûáîðàõíà äðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè.Èç ýòîé òåîðåìû ñëåäóåò, ÷òî CE ≤ CT + O(N) .Îïòèìàëüíûå âûáîðûÀëãîðèòì èçáðàíèÿ ëèäåðà íà äåðåâå ðåøàåò çàäà÷ó î âûáîðàõíà äðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè.Èç ýòîé òåîðåìû ñëåäóåò, ÷òî CE ≤ CT + O(N) .Åñëè â íàøåì ðàñïîðÿæåíèè åñòü ëèäåð, òî îñòîâíîå äåðåâîìîæíî ïîñòðîèòü ñ èñïîëüçîâàíèåì 2|E | îáìåíîâ ñîîáùåíèÿìèïðè ïîìîùè öåíòðàëèçîâàííîãî àëãîðèòìà îáõîäà ñåòè.Ïîýòîìó ñïðàâåäëèâî íåðàâåíñòâî CT ≤ CE + 2|E | .Îïòèìàëüíûå âûáîðûÀëãîðèòì èçáðàíèÿ ëèäåðà íà äåðåâå ðåøàåò çàäà÷ó î âûáîðàõíà äðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè.Èç ýòîé òåîðåìû ñëåäóåò, ÷òî CE ≤ CT + O(N) .Åñëè â íàøåì ðàñïîðÿæåíèè åñòü ëèäåð, òî îñòîâíîå äåðåâîìîæíî ïîñòðîèòü ñ èñïîëüçîâàíèåì 2|E | îáìåíîâ ñîîáùåíèÿìèïðè ïîìîùè öåíòðàëèçîâàííîãî àëãîðèòìà îáõîäà ñåòè.Ïîýòîìó ñïðàâåäëèâî íåðàâåíñòâî CT ≤ CE + 2|E | .Òàêèì îáðàçîì, äëÿ îïòèìàëüíîãî âûáîðà ëèäåðà íåîáõîäèìîè äîñòàòî÷íî óìåòü îïòèìàëüíî ñòðîèòü îñòîâíîå äåðåâî.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS) ñòðîèò îñòîâíîåäåðåâî ñ èñïîëüçîâàíèåì 2|E | + 5N log N îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS)Àëãîðèòì GHS îïèðàåòñÿ íà ñëåäóþùèå äîïóùåíèÿ.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS)Àëãîðèòì GHS îïèðàåòñÿ íà ñëåäóþùèå äîïóùåíèÿ.1.
Êàæäîìó ðåáðó ïðèïèñàí óíèêàëüíûé âåñ ω(e) . Âñå âåñàðåáåð ëèíåéíî óïîðÿäî÷åíû.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS)Àëãîðèòì GHS îïèðàåòñÿ íà ñëåäóþùèå äîïóùåíèÿ.1. Êàæäîìó ðåáðó ïðèïèñàí óíèêàëüíûé âåñ ω(e) . Âñå âåñàðåáåð ëèíåéíî óïîðÿäî÷åíû.2.
Âñå óçëû ïðåáûâàþò ïåðâîíà÷àëüíî â ñîñòîÿíèèîöåïåíåíèÿ è ïðîáóæäàþòñÿ ïåðåä íà÷àëîì âûïîëíåíèÿàëãîðèòìà.Íåêîòîðûå óçëû ïðîáóæäàþòñÿ ñàìîïðîèçâîëüíî, äðóãèåìîãóò ïîëó÷èòü ñîîáùåíèå ïî õîäó ðàáîòû àëãîðèòìà, åùåïðåáûâàÿ â îöåïåíåíèè.Ïðè ýòîì óçåë, ïîëó÷èâøèé ñîîáùåíèå, âíà÷àëå âûïîëíÿåòïðîöåäóðó ëîêàëüíîé èíèöèàëèçàöèè, à çàòåì ïðèñòóïàåò êîáðàáîòêå ýòîãî ñîîáùåíèÿ.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÐàññìîòðèì âçâåøåííûé ãðàô G = (V , E ) , è äëÿ îáîçíà÷åíèÿâåñà ðåáðà e áóäåì èñïîëüçîâàòü çàïèñü ω(e) .Ìû áóäåì ïîëàãàòü, ÷òî êàæäîå ðåáðî èìååò óíèêàëüíûé âåñ.Âåñ îñòîâíîãî äåðåâà T â ãðàôå G ïîëàãàåòñÿ ðàâíûì ñóììåâåñîâ âñåõ N − 1 ðåáåð, âõîäÿùèõ â ñîñòàâ T .Ïðè ýòîì T íàçûâàåòñÿ ìèíèìàëüíûì îñòîâíûì äåðåâîì , èëèñîêðàùåííî MST, åñëè íè îäíî îñòîâíîå äåðåâî íå èìååò âåñìåíüøèé, ÷åì T .Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÓòâåðæäåíèå 9.1.Åñëè âñå âåñà ðåáåð ïîïàðíî ðàçëè÷íû, òî ñóùåñòâóåò òîëüêîîäíî MST.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÓòâåðæäåíèå 9.1.Åñëè âñå âåñà ðåáåð ïîïàðíî ðàçëè÷íû, òî ñóùåñòâóåò òîëüêîîäíî MST.Äîêàçàòåëüñòâî.Äîïóñòèì, ÷òî åñòü äâà MST T1 è T2 , ïðè÷åì T1 6= T2 .Ðàññìîòðèì ðåáðî e íàèìåíüøåãî âåñà, êîòîðîå ñîäåðæèòñÿ âîäíîì èç ýòèõ äåðåâüåâ, íî íå ñîäåðæèòñÿ â äðóãîì.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÓòâåðæäåíèå 9.1.Åñëè âñå âåñà ðåáåð ïîïàðíî ðàçëè÷íû, òî ñóùåñòâóåò òîëüêîîäíî MST.Äîêàçàòåëüñòâî.Äîïóñòèì, ÷òî åñòü äâà MST T1 è T2 , ïðè÷åì T1 6= T2 .Ðàññìîòðèì ðåáðî e íàèìåíüøåãî âåñà, êîòîðîå ñîäåðæèòñÿ âîäíîì èç ýòèõ äåðåâüåâ, íî íå ñîäåðæèòñÿ â äðóãîì.Ïðåäïîëîæèì, ÷òî e ∈ T1 .
Òîãäà T2 ∪ {e} ñîäåðæèò öèêë, è,ïîñêîëüêó â äåðåâå T1 íåò öèêëîâ, õîòÿ áû îäíî ðåáðî ýòîãîöèêëà, ñêàæåì, ðåáðî e 0 , íå ñîäåðæèòñÿ â T1 . Ñîãëàñíîâûáîðó ðåáðà e , ñïðàâåäëèâî íåðàâåíñòâî ω(e) < ω(e 0 ) .Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÓòâåðæäåíèå 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 , à äðóãîé íåò.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÔðàãìåíò ïðîèçâîëüíîå ïîääåðåâî MST. Ðåáðî e íàçûâàåòñÿèñõîäÿùèì ðåáðîì ôðàãìåíòà F , åñëè îäèí èç êîíöîâ eïðèíàäëåæèò F , à äðóãîé íåò.Óòâåðæäåíèå 9.2.Åñëè F ÿâëÿåòñÿ ôðàãìåíòîì, è e ðåáðî íàèìåíüøåãî âåñà,èñõîäÿùåå èç F , òî F ∪ {e} òàêæå ÿâëÿåòñÿ ôðàãìåíòîì.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÔðàãìåíò ïðîèçâîëüíîå ïîääåðåâî MST. Ðåáðî e íàçûâàåòñÿèñõîäÿùèì ðåáðîì ôðàãìåíòà F , åñëè îäèí èç êîíöîâ eïðèíàäëåæèò F , à äðóãîé íåò.Óòâåðæäåíèå 9.2.Åñëè F ÿâëÿåòñÿ ôðàãìåíòîì, è e ðåáðî íàèìåíüøåãî âåñà,èñõîäÿùåå èç F , òî F ∪ {e} òàêæå ÿâëÿåòñÿ ôðàãìåíòîì.Äîêàçàòåëüñòâî.ÑÀÌÎÑÒÎßÒÅËÜÍÎ (ðóêîâîäñòâóÿñü äîêàçàòåëüñòâîìïðåäûäóùåãî óòâåðæäåíèÿ).Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÔðàãìåíò ïðîèçâîëüíîå ïîääåðåâî MST.
Ðåáðî e íàçûâàåòñÿèñõîäÿùèì ðåáðîì ôðàãìåíòà F , åñëè îäèí èç êîíöîâ eïðèíàäëåæèò F , à äðóãîé íåò.Óòâåðæäåíèå 9.2.Åñëè F ÿâëÿåòñÿ ôðàãìåíòîì, è e ðåáðî íàèìåíüøåãî âåñà,èñõîäÿùåå èç F , òî F ∪ {e} òàêæå ÿâëÿåòñÿ ôðàãìåíòîì.Äîêàçàòåëüñòâî.ÑÀÌÎÑÒÎßÒÅËÜÍÎ (ðóêîâîäñòâóÿñü äîêàçàòåëüñòâîìïðåäûäóùåãî óòâåðæäåíèÿ).Àëãîðèòìû íà÷èíàþò ðàáîòó, ðàñïîëàãàÿ ôðàãìåíòàìè,ñîñòîÿùèìè èç åäèíñòâåííîãî óçëà, è ïîñëåäîâàòåëüíîíàðàùèâàþò ôðàãìåíòû, äî òåõ ïîð ïîêà íå áóäåò çàâåðøåíîïîñòðîåíèå MST.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.1. Ôîðìèðóåòñÿ òàêîå ñåìåéñòâî ôðàãìåíòîâ, ÷òîîáúåäèíåíèå èõ ñîäåðæèò âñå óçëû ñåòè.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
