Диссертация (Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах), страница 6

Ñëåäîâàòåëüíî, f 0 ïðåäïîòîê. Ñ äðóãîé ñòîðîíû, â îñòàòî÷íîéñåòè Ecf 0 ïî ñðàâíåíèþ ñ Ecf 0 ìîãëè ïîÿâèòüñÿ òîëüêî ðåáðà âèäà (s, i)ïðè hi ≥ n è (i, s) ïðè hi < n, à çíà÷èò f 0 äîïóñêàåò h. Èç ýòîãî ñëåäóåò,÷òî äëÿ âû÷èñëåíèÿ ìàêñèìàëüíîãî ïîòîêà äëÿ λ0 ìîæíî èñïîëüçîâàòüíà÷àëüíûå çíà÷åíèÿ ïîòîêà f 0 è h.  [65] áîëåå ïîäðîáíî ïîêàçàíî, ÷òîïðè èñïîëüçîâàíèè ìåòîäà ïðîòàëêèâàíèÿ ïðåäïîòîêà âû÷èñëåíèå ìàêñèìàëüíîãî ïîòîêà ïîñëåäîâàòåëüíî äëÿ λ1 ≤ .

. . ≤ λk ýêâèâàëåíòíî(â õóäøåì ñëó÷àå) âû÷èñëåíèþ ìàêñèìàëüíîãî ïîòîêà äëÿ îäíîãî çíà-÷åíèÿ λ. Åñëè íóæíî âû÷èñëèòü ìàêñèìàëüíûé ïîòîê ïîñëåäîâàòåëüíîäëÿ λ1 ≥ . . . ≥ λk , òî ìîæíî èñïîëüçîâàòü àíàëîãè÷íóþ ñõåìó, åñëèâû÷èñëÿòü ïîòîê íå íà ãðàôå G, à íà åãî ðàçâåðíóòîì âàðèàíòå GR(ãðàô GR ïîëó÷àåòñÿ èç G èçìåíåíèåì îðèåíòàöèè âñåõ äóã íà ïðîòèâîïîëîæíîå è îáìåíîì ìåñòàìè èñòîêà è ñòîêà). Åñëè äëÿ G âûïîëíÿåòñÿ(1.15), òî äëÿ GR âûïîëíÿåòñÿ àíàëîãè÷íîå ñâîéñòâî, íî ñ èçìåíåíèåìçíàêà ìîíîòîííîñòè.

Òàêèì îáðàçîì, íàéäÿ äëÿ íåêîòîðîãî çíà÷åíèÿ λìàêñèìàëüíûé ïîòîê f â ãðàôå GR , êîòîðûé äîïóñêàåò h, âçÿâ λ0 < λè ñîîòâåòñòâóþùèé ïîòîê f 0 èç (1.16), ïî âûøåñêàçàííûì ñîîáðàæåíèÿìïîëó÷àåì, ÷òî f 0 äîïóñêàåò h.Òåïåðü ïîñìîòðèì íà ñëó÷àé ëèíåéíûõ ïî λ ïðîïóñêíûõ ñïîñîáíîñòåé33è, â ÷àñòíîñòè, íà çàäà÷ó (1.11). Äëÿ àíàëèçà óäîáíåå ðàññìàòðèâàòüâåëè÷èíó s−t ðàçðåçà, íåæåëè âåëè÷èíó ïîòîêà. Àäàïòèðóÿ îïðåäåëåíèå(1.14) äëÿ ïàðàìåòðè÷åñêîãî ñëó÷àÿ ïîëó÷àåì(1.17)XCut(S, λ) =ce (λ).e=(i,j)∈E,i∈S,j∈V \SÈç òåîðåìû Ôîðäà-Ôàëêåðñîíà ñëåäóåò, ÷òî çíà÷åíèå ìàêñèìàëüíîãî ïîòîêà ðàâíî çíà÷åíèþ ìèíèìàëüíîãî ðàçðåçà. Åñëè ïðîïóñêíûå ñïîñîáíîñòè ëèíåéíûå ôóíêöèè, òî Cut(S, λ) ëèíåéíà ïî λ, minS Cut(S, λ) ÿâëÿåòñÿ ìèíèìóì ëèíåéíûõ ôóíêöèé êóñî÷íî-ëèíåéíàÿ âûïóêëàÿ ââåðõôóíêöèÿ.

Îáîçíà÷èìM incut(λ) = minS Cut(S, λ). Òî÷êîé èçëîìà áóäåì íàçûâàòü òàêîå çíà÷åíèå λ, ÷òî äëÿ ëþáîãî > 0 ñóùåñòâóþò òàêèå ðàçðåçû S1 , S2 , ÷òîM incut(λ) = Cut(S1 , λ) = Cut(S2 , λ),íîCut(S1 , λ + ) > Cut(S2 ), λ + )èCut(S1 , λ − ) < Cut(S2 ), λ − ).Ãåîìåòðè÷åñêè òî÷êà èçëîìà åñòü òî÷êà ïåðåñå÷åíèÿ äâóõ ïðÿìûõ, ñîîòâåòñòâóþùèõ âåëè÷èíàì ðàçðåçîâ S1 è S2 . Åñëè äëÿ ôóíêöèé ïðîïóñêíûõ ñïîñîáíîñòåé âûïîëíÿåòñÿ (1.15) (â ýòîì ñëó÷àå äàæå íå íóæíà ëèíåéíîñòü), òî òàêèõ òî÷åê áóäåò íå áîëüøå n − 1 (çäåñü n îáùåå êîë-âîâåðøèí, âêëþ÷àÿ ñòîê è èñòîê), ïîäðîáíîñòè â [65].Èç ñîîáðàæåíèé, îïèñàííûõ â ïðåäûäóùåì ðàçäåëå, îïòèìàëüíîå çíà÷åíèå (1.11) ñîîòâåòñòâóåò ìèíèìàëüíîé òî÷êè èçëîìà M incut(λ) äëÿáëèçêèõ ê íóëþ λ ìèíèìàëüíûé ðàçðåç ñîîòâåòñòâóåò ìíîæåñòâàì {s} èV \ {t}.

Ìàêñèìàëüíîå çíà÷åíèå λ, äëÿ êîòîðîãî ýòè ðàçðåçû áóäóò îñòàâàòüñÿ ìèíèìàëüíûìè, ñîîòâåòñòâóåò ìèíèìàëüíîé òî÷êå èçëîìà. Äëÿáåñêîíå÷íî áîëüøèõ λ ìèíèìàëüíûé ðàçðåç ñîîòâåòñòâóåò ìíîæåñòâó34{s} ∪ {i ∈ V |di > 0}. Áîëåå òîãî, âåëè÷èíà òàêîãî ðàçðåçà íå çàâèñèòîò λ.Íåñìîòðÿ íà òî, ÷òî äëÿ (1.17) íå âûïîëíÿåòñÿ (1.15) (äëÿ äóã, âõîäÿùèõ â ñòîê, ïðîïóñêíûå ñïîñîáíîñòè âîçðàñòàþò), åñëè ìíîæåñòâî {i ∈V |di > 0} ñîñòîèò èç îäíîãî ýëåìåíòà, òî ìîæíî íå ðàñøèðÿòü ãðàô ôèêòèâíûì ñòîêîì, à èñïîëüçîâàòü â êà÷åñòâå ñòîêà åäèíñòâåííóþ âåðøèíóýòîãî ìíîæåñòâà.

 ýòîì ñëó÷àå âñå âõîäÿùèå äóãè áóäóò èìåòü ïîñòîÿííóþ ïðîïóñêíóþ ñïîñîáíîñòü, è, ñëåäîâàòåëüíî, óñëîâèÿ (1.15) áóäóò âûïîëíÿòüñÿ. Àíàëîãè÷íûé òðþê âîçìîæåí, åñëè ìíîæåñòâî {i ∈ V |di < 0}ñîñòîèò òîëüêî èç îäíîãî ýëåìåíòà.Íàêîíåö, îïèøåì ýôôåêòèâíûé àëãîðèòì íàõîæäåíèÿ ìèíèìàëüíîéòî÷êè èçëîìà.

Ïóñòü èçâåñòíû àïðèîðè çíà÷åíèÿ λl , λr òàêèå, ÷òî èñêîìàÿ òî÷êà èçëîìà λ∗ óäîâëåòâîðÿåò λl ≤ λ∗ ≤ λr (äëÿ (1.17) òàêèå çíà÷åíèÿ äàíû â ðàçäåëå 3). Ïóñòü Sl = argminS Cut(S, λl ), Sr =argminS Cut(S, λr ). Íàéäåì òî÷êó λ0 èç óðàâíåíèÿCut(Sl , λ0 ) = Cut(Sr , λ0 ).Òàêîå λ0 îáÿçàòåëüíî íàéäåòñÿ, òàê êàê ñëåâà è ñïðàâà íàïèñàíû ëèíåéíûå ôóíêöèè, èç îïðåäåëåíèÿ ýòèõ ðàçðåçîâ è âûïóêëîñòè âíèç M incut(λ)ïîëó÷àåì, ÷òî òî÷êà λ0 óäîâëåòâîðÿåò λl ≤ λ0 ≤ λr . Çàìåòèì, ÷òî íàèíòåðâàëå [λ0 , λr ) ñîäåðæèòñÿ õîòÿ áû îäíà òî÷êà èçëîìà, áîëåå òîãî, åñ-ëè λl è λr ëåæàò íà ñîñåäíèõ ëèíåéíûõ îòðåçêàõ M incut(·), òî λ0 ñàìàÿâëÿåòñÿ òî÷êîé èçëîìà. Ïîëîæèì λr := λ0 è ïîâòîðèì ïðîöåññ.

Åñëèïîâòîðÿòü ýòîò ïðîöåññ äî òåõ ïîð, ïîêà íå áóäåò âûïîëíÿòüñÿCut(Sl , λ) ≡ Cut(Sr , λ),òî â èòîãå ìû ïîëó÷èì ìèíèìàëüíóþ òî÷êó èçëîìà. Áîëåå ôîðìàëüíî, ýòîò àëãîðèòì âûãëÿäèò ñëåäóþùèì îáðàçîì. Ïðåäïîëàãàåòñÿ, ÷òîïðîïóñêíûå ñïîñîáíîñòè èìåþò âèä ce (λ) = ae + be λ, a = (a1 , . . . , am )T ,b = (b1 , .

. . , bm )T .35FunctionMinimum breakpoint simple(G, a, b, λl , λr )f ← Maximum ow(G, c(λl ));Sl ← Minimum cut (G, c(λl ), f );La ← 0;Lb ← 0;for e = (i, j), i ∈ Sl , j ∈ V \ Sl doLa ← La + ae ;Lb ← Lb + be ;whiletruedof ← Maximum ow(G, c(λl ));Sr ← Minimum cut (G, c(λr ), f );Ra ← 0;Rb ← 0;for e = (i, j), i ∈ SR , j ∈ V \ SR doRa ← Ra + ae ;Rb ← Rb + be ;ifLa = Ra and Lb = Rbreturn λr ;thenelseλr ←La −RaLb −Rb ;Íà ðèñóíêå 1.5 ïîêàçàíà ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ïåðåñ÷åòà λrïî ôóíêöèè M incut(λ) â îïèñàííîì àëãîðèòìå. êà÷åñòâå ôóíêöèè Maximum ow ãîäèòñÿ ëþáîé àëãîðèòì, âû÷èñëÿþùèé ìàêñèìàëüíûé ïîòîê.

 ÷àñòíîñòè, îïèñàííàÿ ðàíåå ôóíêöèÿPreow push.  îòëè÷èè îò ìåòîäà áèñåêöèè, ýòîò ìåòîä ñõîäèòñÿ ê òî÷íîìó çíà÷åíèþ çà êîíå÷íîå ÷èñëî èòåðàöèé. Íà ïðàêòèêå, äàæå äëÿ ãðàôîâ ñ íåñêîëüêèìè ñîòíÿìè òûñÿ÷ ðåáåð òàêîé àëãîðèòì äåëàåò íå áîëåå10 èòåðàöèé. Ïîñëåäîâàòåëüíîñòü {λri }ki=1 , ïîëó÷àåìàÿ â ýòîì àëãîðèòìå, ñòðîãî óáûâàåò, à çíà÷èò âîçìîæíî ïðèìåíåíèå àìîðòèçèðîâàííîéâåðñèè ïðåäïîòîêà, åñëè ïðîâîäèòü âû÷èñëåíèÿ â ãðàôå GR .

Ìîäèôèöèðîâàííàÿ âåðñèÿ àëãîðèòìà ïðåäñòàâëåíà äàëåå (ôóíêöèÿ Minimum36Mincut(λ)λ* λ2Ðèñ. 1.5: Èçìåíåíèåbreakpoint GGT.λ1λλ0 λâ àëãîðèòìàõ Minimum breakpoint simple è Minimumbreakpoint GGT).Ðàññìîòðåííûé àëãîðèòì ÿâëÿåòñÿ îòíîñèòåëüíî ðåäêèì, â îòêðûòîì äîñòóïå äîñòóïíà òîëüêî îäíà áèáëèîòåêà (paraF) ñ îïèñàííûì ìåòîäîì [36] (îïèñàíèå îò àâòîðîâ äîñòóïíî íà [45]). Íåñêîëüêèìè ìîäèôèêàöèÿìè êîäà ýòîé áèáëèîòåêè óäàëîñü ïîëó÷èòü íåáîëüøîå óëó÷øåíèå.Ïîäðîáíîñòè îïèñàíû â ãëàâå 3.1.3Äâå ïîòîêîâûõ çàäà÷è ìóëüòèàãåíòíîãîðàñïðåäåëåíèÿ ðåñóðñîâ1.3.1Çàäà÷à áàëàíñèðîâàíèÿ çàãðóçêè â ñåòèÍåôîðìàëüíî çàäà÷ó ðàñïðåäåëåíèÿ çàãðóçêè â ñåòè ìîæíî ñôîðìóëèðîâàòü ñëåäóþùèì îáðàçîì:• Ðàññìàòðèâàåòñÿ ñåòü, ñîñòîÿùàÿ èç n âû÷èñëèòåëüíûõ óçëîâ.• Íåêîòîðûå ïàðû óçëîâ ñîåäèíåíû îäíîíàïðàâëåííîé èëè äâóíàïðàâëåííîé ñâÿçüþ.37• Íà êàæäîì óçëå åñòü î÷åðåäü çàäà÷ íà èñïîëíåíèå.• Äëÿ êàæäîãî çàäàíèÿ óçåë äîëæåí ðåøèòü: âûïîëíèòü ëè çàäàíèåñàìîìó èëè îòïðàâèòü ñîñåäó.• Êàêèì îáðàçîì îðãàíèçîâàòü ïðèíÿòèå ðåøåíèé òàêèì îáðàçîì,÷òîáû ìèíèìèçèðîâàòü âðåìÿ âûïîëíåíèÿ ïîñëåäíåãî çàäàíèÿ?Çàäà÷è òàêîãî ðîäà ÿâëÿþòñÿ îñíîâîïîëàãàþùèìè äëÿ ñîâðåìåííûõâû÷èñëèòåëüíûõ ñèñòåì.

 ðàáîòàõ [40, 58, 76] îïèñàíà îáùàÿ ñïåöèôèêàòàêèõ çàäà÷. Òàê êàê â òàêèõ ñèñòåìàõ ïðåäïîëàãàåòñÿ ïåðåäà÷à äàííûõ,òî ìîæíî ñ óâåðåííîñòüþ ñêàçàòü, ÷òî çàäà÷å ïðèñóòñòâóåò ïîòîêîâàÿñïåöèôèêà. Òåì íå ìåíåå, â íåêîòîðûõ ñëó÷àÿõ ïåðåäà÷à äàííûõ íå ÿâëÿåòñÿ óçêèì ìåñòîì ñèñòåìû, êàê íàïðèìåð â ñèñòåìàõ ñ îáùåé ïàìÿòüþ, ãäå ïåðåäà÷à çàäà÷ îò îäíîãî ïðîöåññîðà (èëè ÿäðà) ê äðóãîìóìîæåò áûòü îñóùåñòâëåíà áåç êîïèðîâàíèÿ / ïåðåäà÷è êîíòåêñòà çàäà÷è.Îäíàêî, äëÿ ôèçè÷åñêè ðàçäåëåííûõ âû÷èñëèòåëüíûõ óñòðîéñòâ âðåìÿ,çàòðà÷èâàåìîå íà ïåðåäà÷ó äàííûõ, ìîæåò áûòü ñîèçìåðèìî âðåìåíè,çàòðà÷èâàåìîìó íà îáðàáîòêó çàäà÷. Ðàñïèøåì áîëåå áîëåå ôîðìàëüíîýòó çàäà÷ó:• Ñåòü ñîñòîèò èç n âû÷èñëèòåëüíûõ óçëîâ.• qi ∈ R+ íà÷àëüíûé óðîâåíü çàãðóçêè i-ãî óçëà, îáîçíà÷èì q =(q1 , q2 , .

. . , qn ) âåêòîð çàãðóçêè.• Ñâÿçè ìåæäó óçëàìè èìåþò îãðàíè÷åííûå ïðîïóñêíûå ñïîñîáíîñòè. Íå óìàëÿÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ìåæäó äâóìÿ óçëàìè ìîæåò ñóùåñòâîâàòü òîëüêî îäíî ðåáðî (äâà â îðèåíòèðîâàííîìñëó÷àå), îáîçíà÷èì ÷åðåç cij ∈ R ïðîïóñêíóþ ñïîñîáíîñòü ïåðåäà÷èèíôîðìàöèè îò óçëà i óçëó j , cij ≥ 0 è ïðè ýòîì îòëè÷íî îò íóëÿòîëüêî â òîì ñëó÷àå, åñëè ìåæäó i, j ñóùåñòâóåò êàíàë ñâÿçè.• pi ∈ R+ ïðîèçâîäèòåëüíîñòü i-ãî óçëà, îáîçíà÷èìp = (p1 , p2 , .

. . , pn ) âåêòîð ïðîèçâîäèòåëüíîñòè.38• u = (uij )(i,j)∈E , íóìåðàöèÿ âåêòîðà u ñîãëàñîâàíà ñ ìàòðèöåé èíöèäåíòíîñòè B , uij êîëè÷åñòâî ïåðåäàâàåìîé íàãðóçêè â åäèíèöóâðåìåíè ïî êàíàëó (i → j). Äðóãèìè ñëîâàìè êîëè÷åñòâî íàãðóçêèïåðåäàííîå ïî êàíàëó (i → j) çà èíòåðâàë âðåìåíè [τ1 , τ2 ] îïðåäåRτëÿåòñÿ êàê τ12 uij (t)dt èëè æå ïðîñòî (τ2 − τ1 )uij åñëè u íå ìåíÿåòñÿñî âðåìåíåì.Âûïîëíåíèå âñåõ çàäàíèé çà ìèíèìàëüíîå âðåìÿ ìîæíî ñôîðìóëèðîâàòü â âèäå çàäà÷å, ñõîæåé ïî ïîñòàíîâêå ñ (1.10).ìèíèìèçèðîâàòü(1.18)ïðè óñëîâèèτ,ẋ = Bu − p̃, x(0) = q; x(τ ) = 0n ,x(t) ≥ 0,0 ≤ p̃i (t) ≤ pi ,0 ≤ uij (t) ≤ cij (t). ýòîé ôîðìóëèðîâêå, ïåðåìåííûìè ÿâëÿþòñÿ u è p̃, ïðè ýòîì p̃ ïðîèçâîäèòåëüíîñòü ïî ôàêòó. (1.18) äîñòàòî÷íî ïðîñòî ñâîäèòñÿ ê (1.10).Ïóñòü V ìíîæåñòâî âñåõ óçëîâ, E ∈ V ×V ìíîæåñòâî êàíàëîâ ñâÿ-çè ìåæäó óçëàìè, ïðîïóñêíûå ñïîñîáíîñòè êîòîðûõ åñòü cij .