Диссертация (1149954), страница 9
Текст из файла (страница 9)
Èñïîëüçóåì â ïðåîáðàçîâàííîé ñåòè àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòèñ ëèíåéíûìè óñèëåíèÿìè.Ïîëó÷àåì àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî ïñåâäîïîòîêà, ñëîæíîñòü êîòîðîãî òàæå, ÷òî è â ïðåäûäóùåì ñëó÷àå.Îáùèé ñëó÷àéÏóñòü ÍÊË-óíêöèÿíà îòðåçêå[ai−1 ; ai ].òî÷êîé âîãíóòîñòèg(x)çàäàíà íà îòðåçêàõÁóäåì íàçûâàòüòî÷êóËþáàÿ ÍÊË-óíêöèÿai ,òî÷êîé âûïóêëîñòèâ êîòîðîég(x)0 = a0 < a1 < a2 < · · · < ak : g(x) = pi x + qâ êîòîðîépi < pi+1 ,èpi > pi+1 .ïðåäñòàâèìà â âèäåg i (x) âîãíóòûå óíêöèè. Áóäåì íàçûâàòü ýòîýòîìk1âðåìÿai ,òî÷êóg(x) = max(g 1 (x), g 2(x), .
. . g k1 (x)),max-ïðåäñòàâëåíèåìãäåÍÊË-óíêöèè. Ïðè êîëè÷åñòâî òî÷åê âûïóêëîñòè + 1, à max-ïðåäñòàâëåíèå ìîæåò áûòü ïîëó÷åíî çàO(k ln k)(ñì. ïðèëîæåíèå 1).Àíàëîãè÷íî,ëþáàÿmin(p1 (x), p2 (x), . . . pk2 (x)),ïðåäñòàâëåíèåìÍÊË-óíêöèÿãäåpi (x)p(x)ïðåäñòàâèìàâûïóêëûåÍÊË-óíêöèè. Ïðè ýòîìk2óíêöèè. êîëè÷åñòâîmin-ïðåäñòàâëåíèå ìîæåò áûòü ïîëó÷åíî çà âðåìÿO(k ln k)âÁóäåìòî÷åêâèäåíàçûâàòüp(x)ýòîâîãíóòîñòè(ñì.
ïðèëîæåíèå 1).=min-+ 1, à39àññìîòðèì ïîëóïåðåáîðíûéàëãîðèòìíàõîæäåíèÿ îïòèìàëüíîãî ïñåâäîïîòîêà â ñåòèñ ÍÊË-óñèëåíèÿìè è ñòîèìîñòÿìè:1. Âñå óíêöèè óñèëåíèÿ ïðåäñòàâëÿþòñÿ êàê ìàêñèìóìû âîãíóòûõ óíêöèé óñèëåíèÿ(çà âðåìÿO(mk ln k)).2. Âñå óíêöèè ñòîèìîñòè ïðåäñòàâëÿþòñÿ êàê ìèíèìóìû âûïóêëûõ óíêöèé ñòîèìîñòè(çà âðåìÿO(mk ln k)).3. Ïðîèçâîäèòñÿ ïåðåáîð ïî âñåì àðãóìåíòàì ìàêñèìóìîâ è ìèíèìóìîâ, è äëÿ êàæäîãîèç íèõ ðåøàåòñÿ çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî ïñåâäîïîòîêà â ñåòè ñ âîãíóòûìèêóñî÷íî-ëèíåéíûìè óñèëåíèÿìè è âûïóêëûìè êóñî÷íî-ëèíåéíûìè ñòîèìîñòÿìè.Òåîðåìà 4(àëãîðèòì ðåøåíèÿ âûïóêëîé çàäà÷è íàõîæäåíèÿ ïîòîêà ìèíèìàëüíîé ñòîèìî-ñòè â ñåòè ñ óñèëåíèÿìè â äóãàõ).Ïîëóïåðåáîðíûé àëãîðèòì äåéñòâèòåëüíî íàõîäèò îïòè-ìàëüíûé ïñåâäîïîòîê.
Ñëîæíîñòü òàêîãî ïîëóïåðåáîðíîãî àëãîðèòìà O(k1m l2m )F ((k2 +l1 )m, n), ãäå k1 , k2 êîëè÷åñòâî òî÷åê âûïóêëîñòè è âîãíóòîñòè ó óíêöèé óñèëåíèÿ,l1 , l2 ó óíêöèé ñòîèìîñòè.Äîêàçàòåëüñòâî.Îïòèìàëüíîñòü ïñåâäîïîòîêà ñëåäóåò èç òåîðåìû 1 î äîñòèæåíèè ìàêñè-ìàëüíîãî çíà÷åíèÿ. Ñëîæíîñòü àëãîðèòìà èç òîãî, íóæíî ïåðåáðàòü äëÿ êàæäîé äóãèâàðèàíòîâ, ïðè÷åì â êàæäîé èç ïîëó÷åííûõ äóã áóäåò íå áîëüøåk2k 1 l2êóñî÷êîâ â óíêöèÿõóñèëåíèÿ è íå áîëüøå l1 êóñî÷êîâ â óíêöèÿõ ñòîèìîñòè.Çàìå÷àíèåm1.2.4. Ïåðåáîð ìîæíî ñîêðàòèòü, åñëè ïðè ðàññìîòðåíèèj -ãîïðèíèìàòü íèæíþþ ïðîïóñêíóþ ñïîñîáíîñòü äóãè çà ìèíèìàëüíûélmaxl gm(x)Çàìå÷àíèåèxâàðèàíòà äëÿ äóãèòàêîé, ÷òîjgm(x) =pjm (x) = minl plm (x).1.2.5.  [23℄ ïðåäëîæåí ìåòîä âåòâåé è ãðàíèö äëÿ íàõîæäåíèÿ îïòèìàëüíîãîïîòîêà â ñåòè, â êîòîðîéñòåéøåãî âèäà:käóã èìåþò âîãíóòûå êóñî÷íî-ëèíåéíûå óíêöèè ñòîèìîñòè ïðî-pm (x) = min(ax, b)ãàåò ïåðåáîð â õóäøåì ñëó÷àå2k òî åñòü ñîñòîÿùèå èç 2 êóñî÷êîâ.
Ýòîò ìåòîä ïðåäïîëàâàðèàíòîâ è ðåøåíèå äëÿ êàæäîãî èç íèõ çàäà÷è î ïîòîêåìèíèìàëüíîé ñòîèìîñòè.Îáîáùèì ýòîò ìåòîä íà çàäà÷ó î ïîòîêå ìèíèìàëüíîé ñòîèìîñòè ñ ïðîèçâîëüíûìè ÍÊËóíêöèÿìè ñòîèìîñòè. Òàêæå ïðåäïîëîæèì, ÷òî èìååòñÿkäóãm1 , . . . , mkâ êîòîðûõ óíê-öèè ñòîèìîñòè íåâûïóêëûå, à â îñòàëüíûõ äóãàõ îíè âûïóêëûå. Ïðè ýòîì óíêöèÿ ñòîèìîñòè â äóãåmiièìååò l2 òî÷åê âîãíóòîñòè.Ïîëó÷èì ñëåäóþùèéàëãîðèòì:401. Ôóíêöèÿ ñòîèìîñòèpmiâ êàæäîé äóãåmiïðåäñòàâëÿåòñÿ êàê ìèíèìóì èç âûïóêëûõêóñî÷íî-ëèíåéíûõ óíêöèé:pmi (x) = min(pi1 (x), . . .
, pil2i (x)).2. Óñòàíàâëèâàåì â êàæäîé äóãåmiíà÷àëüíóþ óíêöèþ ñòîèìîñòè, ðàâíóþ3. Ïåðåáèðàåì ïîñëåäîâàòåëüíî âñå âîçìîæíûå âûïóêëûå óíêöèèpkjkâ äóãåmk ,øåíèé. Äëÿpiji ,ïîäñòàâëÿÿ èõ âìåñòî èñõîäíûõ ñòîèìîñòåé(i + 1)-ãîpmi .p1j1pi1 (x).â äóãåm1 ,...,Ïîëó÷àåì äåðåâî ðå-óðîâíÿ äåðåâà, íà êîòîðîì ðàññìàòðèâàåòñÿ óíêöèÿ ñòîèìîñòèâåðõíÿÿ îöåíêà ðåøåíèÿ ðåøåíèå çàäà÷è ñ ïîäñòàâëåííûìè óíêöèÿìè ñòîè-ìîñòè (ýòî äåéñòâèòåëüíî âåðõíÿÿ îöåíêà, ïîñêîëüêó óíêöèÿ ìèíèìóìà íå áîëüøå,÷åì ëþáàÿ èç óíêöèé, ñòîÿùèõ ïîä çíàêîì ìèíèìóìà).
Âñå îíè âûïóêëûå, ïîýòîìóíàõîæäåíèå âåðõíåé îöåíêè ïóòåì ðàñïàðàëëåëèâàíèÿ äóã ñâîäèòñÿ ê îáû÷íîé çàäà÷åî ïîòîêå ìèíèìàëüíîé ñòîèìîñòè.Íèæíÿÿ îöåíêà ðåøåíèÿ ðåøåíèå çàäà÷è, â êîòîðîì â äóãàõmi+1 , . . . , mkóñòàíîâëåíàñòîèìîñòü, ðàâíàÿ 0. Òàêèì îáðàçîì, íàõîæäåíèå íèæíåé îöåíêè òàêæå ñâîäèòñÿ êçàäà÷å î ïîòîêå ìèíèìàëüíîé ñòîèìîñòè.Íåñëîæíî âèäåòü, ýòîò ìåòîä òðåáóåò ïåðåáðàòüO(l21 . . . l2k ) = O(l2k )âàðèàíòîâ, ðåøèâ âêàæäîì èç íèõ çàäà÷ó î ïîòîêå ìèíèìàëüíîé ñòîèìîñòè, à ìåòîä, ïðåäëîæåííûé â [23℄ åãî÷àñòíûé ñëó÷àé.Ïñåâäîïîòîêè è âîçðàñòàþùèå óíêöèèÄî ýòîãî ìû ðàññìàòðèâàëè çàäà÷ó ñ ïñåâäîâîòîêàìè è âîçðàñòàþøèìè óíêöèÿìè óñèëåíèÿ.
Ïîïðîáóåì òåïåðü îáîáùèòü ýòó çàäà÷ó íà ïîòîêè è ïðîèçâîëüíûå óíêöèè. Îêàçûâàåòñÿ, ÷òî îáîáùèòü ìîæíî òîëüêî â îäíîì íàïðàâëåíèè, íî íå â îáîèõ ñðàçó. Ñóùåñòâóåòñâÿçü ìåæäó ïñåâäîïîòîêàìè è âîçðàñòàþùèìè óíêöèÿìè óñèëåíèÿ è ñòîèìîñòè, êîòîðàÿâûðàæàåòñÿ â ñëåäóþùèõ òðåõ óòâåðæäåíèÿõ:Óòâåðæäåíèå 1.2.3. Åñëè âñå óíêöèè óñèëåíèÿ gm è âñå ñòîèìîñòè pm âîçðàñòàþ-ùèå, òî äëÿ êàæäîãî ïñåâäîïîòîêà ñóùåñòâóåò ïîòîê, èìåþùèé òàêóþ æå âåëè÷èíó è íåáîëüøóþ ñòîèìîñòü.Äîêàçàòåëüñòâî.ðÿþò óñëîâèþÍå óìàëÿÿ îáùíîñòè, áóäåì ñ÷èòàòü, ÷òî âñå óíêöèè óñèëåíèÿ óäîâëåòâî-g(0) = 0, ïîñêîëüêó, åñëè åñòü òàêèå óíêöèè gm , ÷òî gm (0) = g0 > 0, ìîæíî èõìîäèèöèðîâàòü, ââåäÿ äîïîëíèòåëüíóþ äóãó, âåäóùóþ âe(m),ñ ïðîïóñêíîé ñïîñîáíîñòüþ41g0 ,è ïåðåéòè ê óíêöèè∗gm(x) = gm (x) − g0 .Ìíîæåñòâî ïîòîêîâ è ìíîæåñòâî ïñåâäîïîòîêîâîò òàêîé ìîäèèêàöèè íå èçìåíèòñÿ.
àññìîòðèì ïñåâäîïîòîêf ′′′′ ,f.Ïîñòðîèì äëÿ íåãî ïîòîêèìåþùèé òó æå âåëè÷èíó è íå áîëüøóþ ñòîèìîñòü, ñëåäóþùèì îáðàçîì:1. Èñïîëüçóÿ òåîðåìó î äîñòèæåíèè ìàêñèìóìà, ñâîäèì ïñåâäîïîòîêïñåâäîïîòîêó2. Ïñåâäîïîòîêf′f′fâ èñõîäíîé ñåòè êâ âèðòóàëüíîé ñåòè ñ âîãíóòûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè.ñ ïîìîùüþ òåîðåìû î êîìïîçèöèè äóã ñâîäèòñÿ ê ïñåâäîïîòîêóf ′′âñåòè ñ ëèíåéíûìè óñèëåíèÿìè.3. Äëÿ ïñåâäîïîòîêàñòâóåò ïîòîêf ′′′ ,f ′′ ,ñîãëàñíî ñâîéñòâàì ñåòåé ñ ëèíåéíûìè óñèëåíèÿìè [86℄, ñóùå-èìåþùèé òàêóþ æå âåëè÷èíó è íå áîëüøóþ ñòîèìîñòü.4.
Èñïîëüçóÿ òåîðåìó î êîìïîçèöèè äóã è òåîðåìó î äîñòèæåíèè ìàêñèìóìà, ñâîðà÷èâàåì ñåòü, ïðèâîäÿ åå â èñõîäíîå ñîñòîÿíèå. Çàìåòèì, ÷òî âñåãäà ìîæíî âûáðàòü òàêîéäîñòàòî÷íî ìàëûé ïîòîêf ′′′ ,÷òîáû ïðè ïðèìåíåíèè òåîðåìû î êîìïîçèöèè äóã îíîñòàëñÿ ïîòîêîì, à íå ïðåâðàòèëñÿ â ïñåâäîïîòîê.Òàêèì îáðàçîì, ïîëó÷àåì òðåáóåìûé ïîòîêÇàìå÷àíèåf ′′′′â èñõîäíîé ñåòè.1.2.6.
Äîêàçàòåëüñòâî êîíñòðóêòèâíî è äàåòàëãîðèòìïðåîáðàçîâàíèÿ ïñåâäî-ïîòîêà â ýêâèâàëåíòíûé ïîòîê. Íåñìîòðÿ íà ïðèìåíåíèå òåîðåìû î äîñòèæåíèè ìàêñèìóìà,ýòîò àëãîðèòì íå òðåáóåò ïåðåáîðà è èìååò ñëîæíîñòüO(mnk).Óòâåðæäåíèå 1.2.4. Äëÿ ëþáîé ñåòè N ñ óíêöèÿìè óñèëåíèÿ gm è âîçðàñòàþùèìè óíê-öèÿìè ñòîèìîñòè pm ñóùåñòâóåò ýêâèâàëåíòíàÿ ñåòü N ′ ñ òåìè æå ïàðàìåòðàìè è âîçðàñòàþùèìè óíêöèÿìè óñèëåíèÿ g m , â êîòîðîé ìíîæåñòâî çíà÷åíèé è ìèíèìàëüíûõñòîèìîñòåé ïñåâäîïîòîêîâ ñîâïàäàåò ñ ìíîæåñòâîì çíà÷åíèé è ìèíèìàëüíûõ ñòîèìîñòåé ïñåâäîïîòîêîâ â èñõîäíîé ñåòè N .Äîêàçàòåëüñòâî.àññìîòðèì ìîäèèöèðîâàííûå óñèëåíèÿ, çàäàííûå òàê:g m (z) = maxgm (z) =′z ∈[0;z]ÔóíêöèèIzgm (z ′ ) dz ′0g m , ïî îïðåäåëåíèþ, âîçðàñòàþò. Äîêàæåì òåïåðü, ÷òî îíè íå ìåíÿþò ìíîæåñòâîïñåâäîïîòîêîâ. Äåéñòâèòåëüíî, ïîñêîëüêó ìû ïåðåõîäèì îò ìåíüøèõ óñèëåíèé ê áîëüøèì,ìíîæåñòâî çíà÷åíèé ïñåâäîïîòîêîâ íå óìåíüøèòñÿ. Íî îíî è íå óâåëè÷èòñÿ, ïîñêîëüêó äëÿêàæäîãî ïñåâäîïîòîêàðåòü çíà÷åíèåf ′ â ìîäèèöèðîâàííîé ñåòè äëÿ êàæäîé äóãè m ∈ Mf ′′ (m) ≤ f ′ (m), íà êîòîðîììîæíî ðàññìîò-äîñòèãàåòñÿ ìàêñèìóì â îïðåäåëåíèè óñèëåíèÿgm ,42è ïåðåéòè ê ìåíüøåìó ïñåâäîïîòîêóf ′′ .Ïî îïðåäåëåíèþ, îí îñòàíåòñÿ êîððåêòíûì ïñåâäî-ïîòîêîì â ìîäèèöèðîâàííîé ñåòè íî îí óæå áóäåò êîððåêòíûì è â èñõîäíîé ñåòè è áóäåòèìåòü òî æå çíà÷åíèå è íå áîëüøóþ ñòîèìîñòü.Çàìå÷àíèå1.2.7.
Ïîñêîëüêó âñå óñèëåíèÿgêóñî÷íî-ëèíåéíû, ìîäèèöèðîâàííûå óñèëåíèÿòàêæå êóñî÷íî-ëèíåéíû, è èõ ìîæíî íàéòè çà âðåìÿO(mk 2 ),ãäåk êîëè÷åñòâà êóñî÷êîââ óíêöèÿõ, èíòåãðèðóÿ ñîîòâåòñòâóþùèå èäåìïîòåíòíûå ðàöèîíàëüíûå óíêöèè [66℄. Åñëèâñå óñèëåíèÿçà âðåìÿgâîãíóòû, òî ìîäèèöèðîâàííûå óñèëåíèÿ òàêæå âîãíóòû è èõ ìîæíî íàéòèO(mk).Àíàëîãè÷íî äîêàçûâàåòñÿ óòâåðæäåíèå:Óòâåðæäåíèå 1.2.5. Äëÿ ëþáîé ñåòè N ñ âîçðàñòàþùèìè óíêöèÿìè óñèëåíèÿ gm è óíê-öèÿìè ñòîèìîñòè pm ñóùåñòâóåò ýêâèâàëåíòíàÿ ñåòü N ′ ñ òåìè æå ïàðàìåòðàìè è âîçðàñòàþùèìè óíêöèÿìè ñòîèìîñòè pm , â êîòîðîé ìíîæåñòâî çíà÷åíèé è ìèíèìàëüíûõñòîèìîñòåé ïñåâäîïîòîêîâ ñîâïàäàåò ñ ìíîæåñòâîì çíà÷åíèé è ìèíèìàëüíûõ ñòîèìîñòåé ïñåâäîïîòîêîâ â èñõîäíîé ñåòè N .Íàõîæäåíèå íà÷àëüíîãî ïîòîêàÅñëè âñå óñèëåíèÿ è ñòîèìîñòè âîçðàñòàþò, çàäà÷à ñ íåëèíåéíûìè óñèëåíèÿìè èìååò íåêîòîðûå ñâîéñòâà, àíàëîãè÷íûå ñâîéñòâàì çàäà÷è ñ ëèíåéíûìè óñèëåíèÿìè.
Íàïðèìåð, ìîæíîîïðåäåëèòü óâåëè÷èâàþùèå ïóòè. Òàêæå âåðíî óòâåðæäåíèå:Óòâåðæäåíèå 1.2.6. Åñëè â ñåòè ñ óñèëåíèÿìè â äóãàõ è ñ íèæíèìè ïðîïóñêíûìè ñïî-ñîáíîñòÿìè âñå óñèëåíèÿ è ñòîèìîñòè âîçðàñòàþò, òî ñóùåñòâóåò àëãîðèòì ñâåäåíèÿçàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà ê çàäà÷å íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà âñåòè áåç íèæíèõ ïðîïóñêíûõ ñïîñîáíîñòåé.Äîêàçàòåëüñòâî.àññìîòðèì ñëåäóþùèéàëãîðèòìíàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà âñåòè ñ íèæíèìè ïðîïóñêíûìè ñïîñîáíîñòÿìè:1. Íàéòè íà÷àëüíûé ïîòîêf0 ýòî ìîæíî ñäåëàòü òåì æå ñïîñîáîì, ÷òî è â ëèíåéíîéçàäà÷å [30℄.2. Ïðîèçâåñòè âû÷èòàíèå ïîòîêàf0èç ñåòè.3. Íàéòè îïòèìàëüíûé ïîòîê â ñåòè ñ ïîëîæèòåëüíûìè âåðõíèìè ïðîïóñêíûìè ñïîñîáíîñòÿìè èñïîëüçóåìûì ðàíåå àëãîðèòìîì (îí ïðèìåíèì íå òîëüêî ê ïñåâäîïîòîêàì, íîè ê ïîòîêàì, ïîñêîëüêó óíêöèè óñèëåíèÿ è ñòîèìîñòè âîçðàñòàþò).43Äîêàçàòåëüñòâî òîãî, ÷òî â èòîãå ïîëó÷èòñÿ îïòèìàëüíûé ïîòîê, àíàëîãè÷íî òàêîâîìó âëèíåéíîé çàäà÷å [30℄.1.3Àëãîðèòìû íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïîòîêà â ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè1.3.1Îïðåäåëåíèå äèíàìè÷åñêîãî ïîòîêà â ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè ðàçäåëå 1.1 ìû äàëè îïðåäåëåíèå äèíàìè÷åñêîé óïðàâëÿåìîé ðàñïðåäåëåííîé ñèñòåìû âäèñêðåòíîì ïðîñòðàíñòâå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
