Диссертация (1150610), страница 5
Текст из файла (страница 5)
. . , fm (çäåñüè äàëåå f = (f1 , . . . , fm )T ), in(i) ìíîæåñòâî âõîäÿùèõ â i äóã, out(i) ìíîæåñòâî äóã, èñõîäÿùèõ èç i. Ïåðâîå óñëîâèå îçíà÷àåò, ÷òî ïîòîê íåçàäåðæèâàåòñÿ â ïðîìåæóòî÷íûõ âåðøèíàõ. Åäèíñòâåííûå äâå âåðøèíûñ íåîòðèöàòåëüíîé ðàçíîñòüþ âõîäÿùèõ / èñõîäÿùèõ ïîòîêîâ s è t.Áîëåå òîãî,Xe∈in(t)fe −Xe∈out(t)fe = − Xe∈in(s)fe −Xfe .e∈out(s)Âïåðâûå â òàêîì âèäå çàäà÷à áûëà ñôîðìóëèðîâàíà â [63].  ýòîéæå ðàáîòå ïîÿâëÿåòñÿ ôóíäàìåíòàëüíàÿ òåîðåìà çàäà÷è ìàêñèìàëüíîãîïîòîêà (ò. Ôîðäà-Ôàëêåðñîíà).Ðàññìîòðèì íåêîòîðîå ðàçáèåíèå ìíîæåñòâà V íà äâà ïîäìíîæåñòâàS, V \ S òàêèõ, ÷òî s ∈ S, t ∈ V \ S . Òàêîå ðàçáèåíèå ïðèíÿòî íàçûâàòüs − t ðàçðåçîì èëè ïðîñòî ðàçðåçîì. Îáîçíà÷èì ÷åðåç Cut(S) âåëè÷èíóòàêîãî ðàçðåçà(1.14)XCut(S) =ce .e=(i,j)∈E,i∈S,j∈V \SÄðóãèìè ñëîâàìè, Cut(S) ñóììà ïðîïóñêíûõ ñïîñîáíîñòåé äóã, íà÷àëîêîòîðûõ ëåæèò â S , à êîíåö â V \ S .
Ëåãêî óâèäåòü, ÷òî äëÿ ëþáîãîäîïóñòèìîãî ïîòîêà f è ðàçðåçà S âûïîëíÿåòñÿ val(f ) ≤ Cut(S).Äàëåå, îñòàòî÷íîé ñåòüþ ïîòîêà f ñ ïðîïóñêíûìè ñïîñîáíîñòÿìè cíàçûâàåòñÿ ìíîæåñòâîEcf = {(i, j)|e = (i, j) ∈ E, fe < ce } ∪ {(j, i)|e = (i, j) ∈ E, fe > 0}.Ñëåäóþùàÿ òåîðåìà ïîêàçûâàåò, ÷òî ââåäåííûå âåëè÷èíû òåñíî ñâÿçàíû ìåæäó ñîáîé.Ò å î ð å ì à1.1(Ôîðäà-Ôàëêåðñîíà [63]). Ñëåäóþùèå òðè óòâåð-æäåíèÿ ýêâèâàëåíòíû:271.
Ïîòîê f ÿâëÿåòñÿ ìàêñèìàëüíûì.2. Äëÿ íåêîòîðîãî ðàçðåçà S âûïîëíÿåòñÿ val(f ) = Cut(S).3.  îñòàòî÷íîé ñåòè Ecf íå ñóùåñòâóåò ïóòè èç s â t.Ñòîèò îòìåòèòü, ÷òî åñëè f ìàêñèìàëüíûé ïîòîê, òî ñîîòâåòñòâóþùèé åìó ðàçðåç ìîæíî âçÿòü êàê ìíîæåñòâî äîñòèæèìûõ èç s âåðøèíïî ðåáðàì îñòàòî÷íîé ñåòè Ecf . Äëÿ íàõîæäåíèÿ òàêîãî ðàçðåçà äîñòàòî÷íî âûïîëíèòü ñëåäóþùóþ ïðîöåäóðó:Function Minimum cut(G, c, f )S ← ∅;Q ← {s};D ← {s};while Q 6= ∅ doi ← any element of Q;Q ← Q \ {i};S ← S ∪ {i};for (i, j) ∈ Ecf doif j ∈/ D thenQ ← Q ∪ {j};D ← D ∪ {j};return S ;Ñ òî÷êè çðåíèÿ ñîâðåìåííîé òåîðèè ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ, òåîðåìà??ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì äâîéñòâåííîñòè â çàäà÷àõëèíåéíîãî ïðîãðàììèðîâàíèÿ.
Ýêâèâàëåíòíîñòü 1-2 ïîêàçûâàåò, ÷òî åñëè ïîëó÷åíû äîïóñòèìûå òî÷êè ïðÿìîé è äâîéñòâåííîé çàäà÷è, òàêèå÷òî çíà÷åíèÿ ôóíêöèîíàëîâ ïðÿìîé è äâîéñòâåííîé çàäà÷è ðàâíû, òîýòè òî÷êè ÿâëÿþòñÿ ðåøåíèÿìè ïðÿìîé è äâîéñòâåííîé çàäà÷è ñîîòâåòñòâåííî. Ïóíêò 3 âûâîäèòñÿ èç óñëîâèé äîïîëíÿþùåé íåæåñòêîñòè. Òåìíå ìåíåå, ôîðìà òåîðåìû áîëåå ïðîñòà íåæåëè äâîéñòâåííîñòü ëèíåéíîãî ïðîãðàììèðîâàíèÿ è, áîëåå òîãî, äàåò êîìáèíàòîðíûé êðèòåðèé îïòèìàëüíîñòè ðåøåíèÿ.28Íàèáîëåå ïîäðîáíûé îáçîð ìåòîäîâ ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãîïîòîêà ïðåäîñòàâëåí â [69].
Ìåòîä ïðîòàëêèâàíèÿ ïðåäïîòîêà áûë âïåðâûå ïðèìåíåí â [20] è ïîçäíåå îôîðìëåí â [68] êàê ñàìîñòîÿòåëüíûéìåòîä. Äî âîçíèêíîâåíèÿ ìåòîäà ïðîòàëêèâàíèÿ ïðåäïîòîêà îñíîâíûìñïîñîáîì ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ïîòîêà ÿâëÿëèñü ðàçëè÷íûåàëãîðèòìû ïîñëåäîâàòåëüíîãî íàõîæäåíèÿ äîïîëíÿþùèõ ïóòåé â îñòàòî÷íîé ñåòè. Èç ïóíêòà 3 è îïðåäåëåíèÿ îñòàòî÷íîé ñåòè ìîæíî âûâåñòèáàçîâûé àëãîðèòì Ôîðäà-Ôàëêåðñîíà: ïîêà â îñòàòî÷íîé ñåòè åñòü ïóòüèç s â t, óâåëè÷èòü ïîòîê âäîëü ïóòè íà íåêîòîðóþ ïîëîæèòåëüíóþ âåëè÷èíó.
Åñëè òàêîé àëãîðèòì ñõîäèòñÿ, òî ðåçóëüòèðóþùèé ïîòîê ÿâëÿåòñÿìàêñèìàëüíûì1 .Ïåðåéäåì ê îïèñàíèþ ìåòîäà ïðîòàëêèâàíèÿ ïðåäïîòîêà [68]. Ïðåä-ïîòîêîì íàçûâàåòñÿ âåêòîð (f1 , . . . , fm )T , óäîâëåòâîðÿþùèé ñëåäóþùèìóñëîâèÿì(excess(i, f ) =0 ≤ fe ≤ ce ,Pe∈in(i) fe−Pe∈out(i) fe≥ 0, i ∈ V, i 6= s,Îñòàòî÷íàÿ ñåòü äëÿ ïðåäïîòîêà îïðåäåëÿåòñÿ òî÷íî òàê æå, êàê è äëÿïîòîêà.
Äàëåå, ðàññìîòðèì âåêòîð h = (h1 , . . . , hn )T ∈ Zn+ (hi ïðèíèìàåòòîëüêî öåëûå íåîòðèöàòåëüíûå çíà÷åíèÿ). Áóäåì ãîâîðèòü, ÷òî ïðåäïîòîê f äîïóñêàåò âåêòîð h, åñëèhs = n, ht = 0,∀(i, j) ∈ Ecf : hi ≤ hj + 1.Îáùàÿ èäåÿ ìåòîäà ïðåäïîòîêîâ ñîñòîèò â òîì, ÷òî åñëè ïðåäïîòîêäîïóñêàåò h, òî â îñòàòî÷íîé ñåòè îòñóòñòâóåò äîïîëíÿþùèé ïóòü. Åñëèïðè ýòîì ïðåäïîòîê ÿâëÿåòñÿ ïîòîêîì, òî âûïîëíåíà òåîðåìà ÔîðäàÔàëêåðñîíà, è ýòîò ïîòîê èìååò ìàêñèìàëüíóþ âåëè÷èíó. Âñå èçìåíåíèÿâ àëãîðèòìå ïðîèñõîäÿò ñ ïîìîùüþ äâóõ ôóíêöèé push è relabel (áóäóò1 Ïîòàêîìó ïðèíöèïó óñòðîåíû ïåðâûå àëãîðèòìû íàõîæäåíèÿ ìàêñèìàëüíîãî ïîòîêà.
Áîëååòîãî, îêàçûâàåòñÿ, ÷òî ñèìïëåêñ-ìåòîä â ïðèìåíåíèè ê ýòîé çàäà÷å äåéñòâóåò àíàëîãè÷íî.29îïèñàíû äàëåå). Àëãîðèòì èíèöèàëèçèðóåòñÿ ñëåäóþùåé ïðîöåäóðîéProcedureforInitialize(G, c, f , h)e ∈ E doif e = (s, i), i ∈ Vfe ← ce ;thenelsefe ← 0;fori 6= s dohi ← 0;hs ← n;Çàìåòèì, ÷òî ïîñëå ïðèìåíåíèÿ òàêîé ïðîöåäóðû, f äîïóñêàåò h. Äàëåå, îïåðàöèÿ push èçìåíÿåò f , à relabel èçìåíÿåò h.Procedure push(G, i, e, c, f , h)ifhi = hj + 1 then // e = (i, j)val ← min(excess(i, f ), ce − fe );fe ← fe + val;Procedurerelabel(G, i, c, f , h)val ← 2n;for (i, j) ∈ Ecf doval ← min(val, hj );hi ← val + 1;Îáùàÿ ïðîöåäóðà ïðîòàëêèâàíèÿ ïðåäïîòîêà çàêëþ÷àåòñÿ â ïîñëåäîâàòåëüíîì ïðèìåíåíèè push è relabel, ïîêà âîçìîæíî èçìåíåíèå ïðåäïîòîêà ýòèìè îïåðàöèÿìè.
Îòìåòèì òîò ôàêò, ÷òî relabel(u) íèêîãäàíå óìåíüøàåò çíà÷åíèå hu . Áîëåå òîãî, åñëè ê âåðøèíå i ïðèìåíèìà (âòîì ñìûñëå, ÷òî â ðåçóëüòàòå ïðèìåíåíèÿ èçìåíèòñÿ f èëè h) îïåðàöèÿpush(i, e) äëÿ íåêîòîðîãî e ∈ Ecf ∩ (in(i) ∪ out(i)), òî äëÿ ýòîé æå âåðøèíû i íå ïðèìåíèìà îïåðàöèÿ ralebel(i) è íàîáîðîò: åñëè ïðèìåíèìàîïåðàöèÿ relabel(i), òî íè äëÿ êàêîãî e íå ïðèìåíèìà îïåðàöèÿ push(i, e).30FunctionPreow push(G, c)Initialize(G, f , h);∃i ∈ V, i 6= s, t : excess(i) > 0 doApply push(G, i, e, c, f , h) or relabel(G, i, c, f , h) whichever isapplicable;whilereturn f ; ýòîé ðàáîòå ìû íå áóäåì ïîâòîðÿòü ïîëíûé àíàëèç ýòîãî àëãîðèòìà, òåì íå ìåíåå ñòîèò âûäåëèòü êëþ÷åâûå ñâîéñòâà. Äàëåå ñ÷èòàåì,÷òî îäíà èòåðàöèÿ àëãîðèòìà ïðîòàëêèâàíèÿ ïðåäïîòîêà çàêëþ÷àåòñÿ âîäíîì ïðèìåíåíèè îïåðàöèè push èëè relabel.1.
Íà ëþáîé èòåðàöèè àëãîðèòìà ïðåäïîòîê f äîïóñêàåò h.2. Íà ëþáîé èòåðàöèè àëãîðèòìà äëÿ ëþáîé âåðøèíû i ñ ïîëîæèòåëüíûì èçáûòêîì (excess(i)>0) ñóùåñòâóåò ïóòü äî s â îñòàòî÷íîé ñåòè. Ó÷èòûâàÿ îïðåäåëåíèå îñòàòî÷íîé ñåòè è òîò ôàêò, ÷òîrelabel(i) ïðèìåíÿåòñÿ òîëüêî ê âåðøèíàì ñ ïîëîæèòåëüíûì èçáûòêîì, ïîëó÷àåì, ÷òî íà ëþáîé èòåðàöèè àëãîðèòìà äëÿ ëþáîéâåðøèíû i âûïîëíÿåòñÿ hi ≤ 2n − 1. Òàêæå, â ÷àñòíîñòè, ýòî ïîêàçûâàåò, ÷òî ó âåðøèíû ñ ïîëîæèòåëüíûì èçáûòêîì ñóùåñòâóåòèñõîäÿùàÿ äóãà, ïðèíàäëåæàùàÿ îñòàòî÷íîé ñåòè, à çíà÷èò, ê íåéïðèìåíèì push èëè relabel.3. Íà ëþáîé èòåðàöèè àëãîðèòìà â îñòàòî÷íîé ñåòè íå ñóùåñòâóåòïóòè èç s â t.4.
Åñëè îïåðàöèè ïðèìåíÿþòñÿ â ïðîèçâîëüíîì ïîðÿäêå, òî àëãîðèòìçàêîí÷èò ðàáîòó çà O(n2 m) èòåðàöèé. Åñëè àëãîðèòì çàâåðøàåò-ñÿ, òî âñå âåðøèíû êðîìå ñòîêà è èñòîêà èìåþò íóëåâîé èçáûòîê.Ñëåäîâàòåëüíî, ïîñëå çàâåðøåíèÿ àëãîðèòìà ïðåäïîòîê f ÿâëÿåòñÿïîòîêîì. Èç ïðåäûäóùåãî ñâîéñòâà è ò. Ôîðäà-Ôàëêåðñîíà ïîëó÷àåì, ÷òî f ìàêñèìàëüíûé ïîòîê.Îêàçûâàåòñÿ, ÷òî ïîðÿäîê ïðèìåíåíèÿ îïåðàöèé ñèëüíî âëèÿåò íàâðåìÿ ðàáîòû àëãîðèòìà. Íà äàííûé ìîìåíò â [92] ïîêàçàíà òåîðåòè31÷åñêàÿ îöåíêà O(nm) íà êîëè÷åñòâî èòåðàöèé àëãîðèòìà (è, ÷òî áîëååâàæíî, òàêàÿ æå îöåíêà íà êîëè÷åñòâî àðèôìåòè÷åñêèõ äåéñòâèé ñëîæåíèé è ñðàâíåíèé).1.2.2Çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêåÏóñòü òåïåðü ïðîïóñêíûå ñïîñîáíîñòè ÿâëÿþòñÿ ôóíêöèÿìè íåêîòîðîãî ãëîáàëüíîãî íåîòðèöàòåëüíîãî ïàðàìåòðà, ce : [0, +∞) → [0, +∞). Âîáùåì ñìûñëå çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå çàêëþ÷àåòñÿ â íàõîæäåíèè ìàêñèìàëüíîãî ïîòîêà äëÿ âñåõ çíà÷åíèé ýòîãî ïàðàìåòðà.
Áîëååôîðìàëüíî, äàí ãðàô G è íàáîð ïðîïóñêíûõ ñïîñîáíîñòåé c1 (·), . . . , cm (·) ôóíêöèé îäíîãî ñêàëÿðíîãî ïàðàìåòðà. Äëÿ êàæäîãî âîçìîæíîãî λíóæíî íàéòè ðåøåíèå çàäà÷è î ìàêñèìàëüíîì ïîòîêå íà ãðàôå G ñ ïðîïóñêíûìè ñïîñîáíîñòÿìè c1 (λ), . . . , cm (λ). Òàêàÿ ôîðìóëèðîâêà ïðèíÿòàâ òåîðèè, îäíàêî íà ïðàêòèêå îáû÷íî âñòðå÷àþòñÿ áîëåå êîíêðåòíûå çàäà÷è. Íàïðèìåð, ïîñòðîèòü ìàêñèìàëüíûé ïîòîê äëÿ êîíå÷íîãî ìíîæåñòâà λ1 , .
. . , λk . Êàê îêàçûâàåòñÿ, òàêóþ çàäà÷ó ìîæíî ðåøèòü áûñòðåå,÷åì ïîñëåäîâàòåëüíûì ðåøåíèåì k ýêçåìïëÿðîâ çàäà÷ î ìàêñèìàëüíîìïîòîêå (ïî çàäà÷å íà êàæäîå çíà÷åíèå λi ). Äàëåå áóäóò îïèñàíû îñíîâíûåêîíöåïöèè, ïðåäëîæåííûå â [65] äëÿ ïîñòðîåíèÿ ýôôåêòèâíîãî ìåòîäàçàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå.Ñðåäè âñåõ çàäà÷ î ïàðàìåòðè÷åñêîì ïîòîêå âûäåëÿþòñÿ äâà êëþ÷åâûõ ïîäêëàññà:• Ïðîïóñêíûå ñïîñîáíîñòè îáëàäàþòòîííîñòè ce (λ) íå óáûâàåò(1.15)ce (λ) íå âîçðàñòàåòce (λ) ïîñòîÿííàñëåäóþùèìè ñâîéñòâàìè ìîíî-ïðè e = (s, i), i 6= t,ïðè e = (i, t), i 6= s,â îñòàëüíûõ ñëó÷àÿõ .• Ïðîïóñêíûå ñïîñîáíîñòè ëèíåéíû ïî λ.Ñòîèò îòìåòèòü, ÷òî ýòè äâà êëàññà ïåðåñåêàþòñÿ, è, áîëåå òîãî, äàëåå â32ðàáîòå áóäóò ïðèâåäåíû ïðàêòè÷åñêèå ïðèìåðû çàäà÷, ãäå îáà ñâîéñòâààêòèâíî èñïîëüçóþòñÿ.Ðàññìîòðèì çàäà÷ó î ïàðàìåòðè÷åñêîì ïîòîêå, óäîâëåòâîðÿþùåé (1.15).Ïðåäïîëîæèì, ÷òî äëÿ çíà÷åíèÿ λ áûë ïîñòðîåí ìàêñèìàëüíûé ïîòîêìåòîäîì ïðåäïîòîêîâ, è â ðåçóëüòàòå áûëè ïîëó÷åíû äâà âåêòîðà f è h,f äîïóñêàåò h.
Îêàçûâàåòñÿ, ÷òîáû ïîñ÷èòàòü ìàêñèìàëüíûé ïîòîê äëÿλ0 > λ, ìîæíî èñïîëüçîâàòü ðåçóëüòàò, ïîëó÷åííûé äëÿ λ. Ðàññìîòðèì(1.16)0 max(ce (λ ), fe ),fe0 =min(ce (λ0 ), fe ),fe ,e = (s, i), hi < n,e = (i, t),äëÿ îñòàëüíûõ äóã.Ïî ñðàâíåíèþ ñ f ïîòîê íà äóãàõ, âûõîäÿùèõ èç èñòîêà, ìîæåò òîëüêîóâåëè÷èòüñÿ, à ïîòîê íà äóãàõ, âõîäÿùèõ â ñòîê, ìîæåò òîëüêî óìåíüøèòüñÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
