Диссертация (1149954), страница 8
Текст из файла (страница 8)
. . , pn .c1 , . . . , cn ,óíêöèè óñèëåíèÿnäóãàìè, â êîòîðûõg1 , . . . , gnè óíêöèèàññìîòðèì ñïåðâà çàäà÷ó ìàêñèìèçàöèè ïîòîêà.Ìàêñèìàëüíûé (ïñåâäî)ïîòîê â òàêîé ñåòè ýòî ðåøåíèå çàäà÷èmax0≤xi ≤cix1 +···+xn ≤V(g1 (x1 ) + · · · + gn (xn ))(1.6)Çàäà÷ó ìîæíî ðåøàòü ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ [6℄. Ââîäÿ âñïîìîãàòåëüíóþ óíêöèþh,ïîëó÷èì ðåêóððåíòíûå ñîîòíîøåíèÿhn (x) = maxy∈[0;x] gn (min(y, cn ))hn−1 (x) = maxy∈[0;x] (gn−1 (min(y, cn−1)) + hn (x − y))...hi (x) = maxy∈[0;x] (gi (min(y, ci )) + hi+1 (x − y))...h0 = h1 (V )h0ãäå⊚ ýòî è åñòü èñêîìîå ìàêñèìàëüíîå çíà÷åíèå.
Èíà÷å ãîâîðÿ,hi = gi ⊚ gi+1 ⊚ · · · ⊚ gn , êîíâîëþöèÿ óíêöèé. Åñëè ââåñòè èäåìïîòåíòíóþ max-plus-àëãåáðó ò.å. ïîëóàë-ãåáðó âåêòîðîâ íàä èäåìïîòåíòíûì ïîëóêîëüöîì(R, max, +) [66℄ òî ìîæíî ïåðåïèñàòü ýòèñîîòíîøåíèÿ òàê:Hxn) dygn ( cn yc−1⊕eHxhn−1 (x) = 0 (gn−1( cn−1cn−1)hn (x/y)) dyy −1 ⊕ehn (x) =0...hi (x) =...Hx0cih (x/y)) dy(gi ( ci y−1⊕e i+1h0 = h1 (V )àññìîòðèì ðåøåíèå ýòîé çàäà÷è äëÿ ðàçëè÷íûõ êëàññîâ óíêöèé óñèëåíèÿ1. Åñëè âñågi âîãíóòûå óíêöèè, òîhgi : âîãíóòàÿ óíêöèÿ (ýòî ñëåäóåò èç òîãî, ÷òî34êîíâîëþöèÿ âîãíóòûõ óíêöèé âîãíóòà).2. Åñëè âñågi êóñî÷íî-ëèíåéíûå óíêöèè èçëèíåéíàÿ óíêöèÿ èçO(k n )O(k)êóñî÷êîâ, òîh òàêæå êóñî÷íî-êóñî÷êîâ. Ýòî ñëåäóåò èç ñâîéñòâ èíòåãðèðîâàíèÿ èäåì-ïîòåíòíûõ ðàöèîíàëüíûõ óíêöèé [66℄.
Ïðè ýòîì ìàêñèìóì ñóììû äâóõ êóñî÷íîëèíåéíûõ óíêöèé èçi+jèjêóñî÷êîâ ìîæíî íàéòè äëÿ êîíêðåòíîãîx,ïåðåáðàâ âñåèíòåðâàëîâ ëèíåéíîñòè è ñðàâíèâ çíà÷åíèÿ â ìåñòàõ ñîåäèíåíèÿ èíòåðâàëîâ. Äëÿîáùåãî æåx,ix èíòåðâàëûëèíåéíîñòè 2-é óíêöèèhi+1 (x − y) ñäâèãàþòñÿïðè èçìåíåíèèïðè÷åì, ïîêà ïàðû ïåðåñåêàþùèõñÿ èíòåðâàëîâ íå ìåíÿþòñÿ, çàâèñèìîñòü ìàêñèìó-ìà îòxîñòàåòñÿ ëèíåéíîé. Çíà÷èò, íóæíî ïåðåáðàòü âñåijçíà÷åíèéx,ïðè êîòîðûõñîåäèíåíèÿ èíòåðâàëîâ 1-é è 2-é óíêöèè ñîâïàäàþò, è íàéòè äëÿ êàæäîãî èç íèõ, êàêìåíÿåòñÿ çàâèñèìîñòü ìàêñèìóìà îòO(k 2 + k 3 + · · · + k n ) = O(k n )3.
Åñëè âñågix.Ýòî òðåáóåòO(ij)îïåðàöèé. Èòîãî ýòî òðåáóåòîïåðàöèé. âîãíóòûå êóñî÷íî-ëèíåéíûå óíêöèè èçâîãíóòàÿ êóñî÷íî-ëèíåéíàÿ óíêöèÿ èçO(k)êóñî÷êîâ, òîh òàêæåO(kn) êóñî÷êîâ, êîòîðóþ ìîæíî íàéòè çà âðåìÿO(kn). Âîãíóòîñòü ñëåäóåò èç ï.1, à êîëè÷åñòâî êóñî÷êîâ èç ñâîéñòâ èíòåãðèðîâàíèÿýëåìåíòàðíûõ èäåìïîòåíòíûõ ðàöèîíàëüíûõ óíêöèé.Çàäà÷à î ïîòîêå ìèíèìàëüíîé ñòîèìîñòè, à òàêæå çàäà÷à ñ ëèíåéíîé êîìáèíàöèåé âåëè÷èíû ïîòîêà è ñòîèìîñòè ðåøàåòñÿ àíàëîãè÷íî, ïðîñòî âìåñòî óíêöèéóíêöèè1.2.5giïîäñòàâëÿåìgi − api .Àãðåãèðîâàííûå ñåòè ñ íåëèíåéíûìè óñèëåíèÿìè. Òåîðåìà îêîìïîçèöèè äóãÈòàê, â íåëèíåéíîì ñëó÷àå íåëüçÿ âîñïîëüçîâàòüñÿ ïðèåìîì ðàçëîæåíèÿ ïîòîêà íà ýëåìåíòàðíûå ïîòîêè.
Ìû âîñïîëüçóåìñÿ äðóãèì ïðèåìîì, êîòîðûé íåðåäêî èñïîëüçóåòñÿ äëÿ ðåøåíèÿ ñåòåâûõ çàäà÷ áîëüøîé ðàçìåðíîñòè [83℄ à èìåííî,àãðåãèðîâàíèåì. äàííîì ñëó÷àå,ðàçëîæåíèåì äóã ãðàà íà ïàðàëëåëüíûå ñ ñîîòâåòñòâóþùèì óïðîùåíèåì óíêöèé óñèëåíèÿ.Êàê èçâåñòíî, ñåòè ìîæíî àãðåãèðîâàòü, îáúåäèíÿÿ ìíîæåñòâà âåðøèí è ìíîæåñòâà äóã.Îá àãðåãèðîâàíèè âåðøèí ìóëüòèãðàà ñêàçàíî â ðàçäåëå 3.2.6, ïîñâÿùåííîì ñåòåâûì èãðàì.À ñåé÷àñ ðàññìîòðèì îïåðàöèþàãðåãèðîâàíèÿ ñåòè ïî äóãàì, îïðåäåëÿåìóþ ñëåäóþùèìðàçîì: äóãèm1 , .
. . , mkg1m , . . . , gkmïðåîáðàçóþòñÿ â óñèëåíèåìåæäó âåðøèíàìègmaèbîáúåäèíÿþòñÿ â îäíó äóãóïî ïðàâèëó:gmm,îá-à èõ óñèëåíèÿ ýòî ðåøåíèå çàäà÷è (1.6). Ýòî35àãðåãèðîâàíèåñòÿì äóã,ïî óñèëåíèÿì äóã.êîãäàÒåîðåìà 2pmÀíàëîãè÷íî, ìîæíî îïðåäåëèòüàãðåãèðîâàíèå ïî ñòîèìî- ðåøåíèå çàäà÷è (1.6) ñ ìèíèìèçàöèåé ñòîèìîñòè.1. Êàæäîìó ïñåâäîïîòîêó â èñõîäíîé ñåòè ñîîò-(î êîìïîçèöèè äëÿ äóã).âåòñòâóåò ïñåâäîïîòîê â àãðåãèðîâàííîé ïî óñèëåíèÿì äóã ñåòè.
Åñëè ñòîèìîñòèïàðàëëåëüíûõ äóã ðàâíûå ëèíåéíûå óíêöèè, òî îí èìååò òó æå ñòîèìîñòü.2. Êàæäîìó (ïñåâäî)ïîòîêó â àãðåãèðîâàííîé ñåòè ñîîòâåòñòâóåò (ïñåâäî)ïîòîê â èñõîäíîé ñåòè. Åñëè ñòîèìîñòè ïàðàëëåëüíûõ äóã ðàâíûå ëèíåéíûå óíêöèè, òî îíèìååò òó æå ñòîèìîñòü.3. Ïóñòü âñå ñòîèìîñòè äëÿ ïàðàëëåëüíûõ äóã ðàâíûå ëèíåéíûå óíêöèè. Òîãäà êàæäîìó îïòèìàëüíîìó ïñåâäîïîòîêó â èñõîäíîé ñåòè ñîîòâåòñòâóåò îïòèìàëüíûéïñåâäîïîòîê â àãðåãèðîâàííîé ïî óñèëåíèÿì äóã ñåòè, è íàîáîðîò.4. Ïóñòü âñå óñèëåíèÿ äëÿ ïàðàëëåëüíûõ äóã ðàâíûå ëèíåéíûå óíêöèè. Òîãäà êàæäîìóîïòèìàëüíîìó ïñåâäîïîòîêó â èñõîäíîé ñåòè ñîîòâåòñòâóåò îïòèìàëüíûé ïñåâäîïîòîê â àãðåãèðîâàííîé ïî ñòîèìîñòè äóã ñåòè.Äîêàçàòåëüñòâî.1.
Ïñåâäîïîòîêìàðíûé ïñåâäîïîòîêf ′ , â êîòîðîì àãðåãèðîâàííîé äóãå m ñîîòâåòñòâóåò ñóì-f1 (m) + f2 (m) + · · · + fk (m),áóäåò äîïóñòèìûì â àãðåãèðîâàííîéñåòè, åñëè ìû çàìåíèì ñóììó íà åå ìàêñèìàëüíîå çíà÷åíèå ðåøåíèå çàäà÷è (1.6),ïîñêîëüêó çíà÷åíèå ïñåâäîïîòîêà ïðè ýòîì íå óìåíüøèòñÿ.2. Åñëèf′ îïòèìàëüíûé (ïñåâäî)ïîòîê â àãðåãèðîâàííîé ñåòè, åãî ìîæíî ðàçëîæèòü âêàæäîé àãðåãèðîâàííîé äóãå íà òàêóþ ñóììó (ïñåâäî)ïîòîêîâf1 (m)+f2 (m)+· · ·+fk (m),íà êîòîðîé äîñòèãàåòñÿ ìàêñèìóì â çàäà÷å (1.6).3. Ïóñòüf′f îïòèìàëüíûé ïñåâäîïîòîê â èñõîäíîé ñåòè.
Åìó ñîîòâåòñòâóåò ïñåâäîïîòîêâ àãðåãèðîâàííîé ñåòè ñ òîé æå ñòîèìîñòüþ, ïîñêîëüêó ñòîèìîñòè ïàðàëëåëüíûõäóã îäèíàêîâû. Ñëåäîâàòåëüíî,Àíàëîãè÷íî, åñëèïîòîêff′f′ îïòèìàëüíûé ïñåâäîïîòîê â àãðåãèðîâàííîé ñåòè. îïòèìàëüíûé ïîòîê â àãðåãèðîâàííîé ñåòè, åìó ñîîòâåòñòâóåòâ èñõîäíîé ñåòè, êîòîðûé èìååò òó æå ñòîèìîñòü è, ñëåäîâàòåëüíî, îïòèìàëåí.4.
Äîêàçûâàåòñÿ àíàëîãè÷íî.Òåîðåìó î êîìïîçèöèè ìîæíî ïðèìåíÿòü äâîÿêî: âî-ïåðâûõ, óïðîñòèòü ãðà, àãðåãèðîâàâ åãî è óìåíüøèâ òàêèì îáðàçîì êîëè÷åñòâî äóã. Âî-âòîðûõ, óïðîñòèòü óíêöèè óñèëåíèÿ,36äåçàãðåãèðîâàâ ãðà ðàçëîæèâ êàæäóþ äóãó íà äóãè ñ áîëåå ïðîñòûìè óíêöèÿìè óñèëåíèÿ. ÷àñòíîñòè, åñëè óíêöèè óñèëåíèÿ ëèíåéíûå:gi (x) = gi x,ãäåg1 , . . . gnîòñîðòèðîâàíûïî óáûâàíèþ, òî àãðåãèðîâàííàÿ óíêöèÿ èìååò âèäh(x) = min(g1 x, g2 x + (g1 − g2 )c1 , g3 x + (g1 − g3 )c1 + (g2 − g3 )c2 , .
. . ,PPn−1(gi − gn )ci , ni=1 gi ci ) =gn x + i=1Nn−1 gi −gn gn Nn gi= xg1 ⊕ c1g1 −g2 xg2 ⊕ cg11 −g3 cg22 −g3 xg3 ⊕ · · · ⊕ ( i=1ci)x ⊕ i=1 ci(1.7)Ýòîò ðåçóëüòàò ìîæíî ïîëó÷èòü, êàê âîñïîëüçîâàâøèñü àïïàðàòîì èäåìïîòåíòíîé àëãåáðû [66℄, òàê è èç îáùèõ ñîîáðàæåíèé.Îáðàòíî, ïóñòü â äóãå çàäàíî óñèëåíèåg(x) = min(g1 x + b1 , . . . gn x + bn , bn+1 )ãäå êîýèöèåíòûg1 , . . . gnîòñîðòèðîâàíû â ïîðÿäêå óáûâàíèÿ. Êîìïîíåíòóäîáñòâà è ìîæåò áûòü ðàâåíbn+1ââåäåí äëÿ+∞.Ïîñêîëüêó ìû ðàññìàòðèâàåì ïñåâäîïîòîêè, ìîæíî, íå óìàëÿÿ îáùíîñòè, ñ÷èòàòü, ÷òîg(x)bn+1 >âîçðàñòàåò. Èç óñëîâèÿ íåîòðèöàòåëüíîñòè óñèëåíèé è âîçðàñòàíèÿ ñëåäóåò, ÷òîbn > bn−1 > · · · > b1 ≥ 0.
Åñëè b1 > 0, ìîæíî óâåëè÷èòü äîïóñòèìûé äåèöèò â âåðøèíå íà b1 ,çàìåíèòü âñåbiíàbi −b1è äàëåå ñ÷èòàòü, ÷òîïàðàëëåëüíûõ äóã ñ óñèëåíèÿìèa1 , . . . anb1 = 0. Ïîñëå ýòîãî äóãó ìîæíî ðàçëîæèòü íà nè ïðîïóñêíûìè ñïîñîáíîñòÿìè, êîòîðûå íàõîäÿòñÿïî ðåêóððåíòíûì îðìóëàìc1 = b1 /(g1 − g2 )c2 = (b2 − (g1 − g3 )c1 )/(g2 − g3 )...(1.8)ci = (bi − (g1 − gi+1 )c1 − · · · − (gi−1 − gi+1 )ci−1 )/(gi − gi+1 )...cn = (bn+1 − g1 c1 − · · · − gn−1 cn−1 )/gnÒî, ÷òî âñå ïðîïóñêíûå ñïîñîáíîñòè ïîëó÷àòñÿ ïîëîæèòåëüíûìè, ñëåäóåò èç óñëîâèé ñóùåñòâåííîñòè ñëàãàåìûõ èäåìïîòåíòíîãî ïîëèíîìà, ïðåäñòàâëÿþùåãî âîãíóòóþ êóñî÷íîëèíåéíóþ óíêöèþ.
Òî åñòü äëÿ ðàçëîæåíèÿ îäíîé äóãè íànïàðàëëåëüíûõ òðåáóåòñÿîïåðàöèé. Òàêèì îáðàçîì, ñëîæíîñòü ðàçëîæåíèÿ âñåõ äóã íà ïàðàëëåëüíûå ðàâíàãäåm èñõîäíîåêîëè÷åñòâî äóã,knO(mk), êîëè÷åñòâî êóñî÷êîâ â êàæäîé óíêöèè. ÈëèO(m′ ),37ãäåm′ ñóììàðíîå êîëè÷åñòâî äóã, ñ÷èòàÿ ïàðàëëåëüíûå. ñëó÷àå, êîãäà óíêöèè è óñèëåíèÿ, è ñòîèìîñòè ðàçíûå, òåîðåìà î êîìïîçèöèè íåïðèìåíèìà.Ïðèìåð 4.àññìîòðèì ãðà, â êîòîðîì åñòü äâå âåðøèíû 1, 2, ñîåäèíåííûå äóãàìè1, 2.
Óñèëåíèå, ïðîïóñêíàÿ ñïîñîáíîñòü è ñòîèìîñòü â ïåðâîé äóãå:x, p1 (x) = x.c1 = 1, g1 (x) =Óñèëåíèå, ïðîïóñêíàÿ ñïîñîáíîñòü è ñòîèìîñòü âî âòîðîé äóãå:0.5x, p1 (x) = 0.Òîãäà àãðåãèðîâàííîå óñèëåíèå, ñîãëàñíî ñîîòíîøåíèÿì (1.7), èìååò âèäg(x) = maxx1 +x2 ≤x (min(x, 1) + min(0.5x2 , 0.5)) = min(x, 0.5x + 0.5, 1.5).ìîñòü èìååò âèäc2 = 1, g2 (x) =p(x) = min(x, 1).Àãðåãèðîâàííàÿ ñòîè-Ìîæíî ïî-ðàçíîìó êîìáèíèðîâàòü óñèëåíèÿ è ñòîèìîñòèè ïîëó÷àòü êàæäûé ðàç íîâîå îïòèìàëüíîå çíà÷åíèåx.Âòî æå âðåìÿ, íå èìåÿ èíîðìà-öèè îá îñòàëüíîì ãðàå, ìû íå ìîæåì îïðåäåëèòü, êàêèå óñèëåíèÿ è ñòîèìîñòè ÿâëÿþòñÿîïòèìàëüíûìè.1.2.6Íàõîæäåíèå îïòèìàëüíîãî ïñåâäîïîòîêà â ñåòè ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìèÊëàññ ÍÊË-óíêöèé çàìêíóò îòíîñèòåëüíî îïåðàöèé êîíâîëþöèè è ìàêñèìóìà.
Áîëåå òîãî,ïðèìåíÿÿ òåîðåìó î êîìïîçèöèè è òåîðåìó î äîñòèæåíèè ìàêñèìóìà, ìîæíî ñâåñòè çàäà÷óñ ÍÊË-óñèëåíèÿìè ê çàäà÷å ñ ëèíåéíûìè óñèëåíèÿìè, êàê áûëî ïîêàçàíî àâòîðîì â [47℄.Ñëó÷àé âîãíóòûõ êóñî÷íî-ëèíåéíûõ óñèëåíèé è âûïóêëûõ êóñî÷íî-ëèíåéíûõñòîèìîñòåéÑåòü ñ âîãíóòûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè è ëèíåéíûìè ñòîèìîñòÿìè ìîæíî äåçàãðåãèðîâàòü â ñåòü ñ ëèíåéíûìè óñèëåíèÿìè, ïîëüçóÿñü îðìóëàìè (1.8).
Àíàëîãè÷íî, ñåòüñ ëèíåéíûìè óñèëåíèÿìè è âûïóêëûìè êóñî÷íî-ëèíåéíûìè ñòîèìîñòÿìè ìîæíî äåçàãðåãèðîâàòü â ñåòü ñ ëèíåéíûìè ñòîèìîñòÿìè. Ýòîò ìåòîä ðàíåå íåîäíîêðàòíî èñïîëüçîâàëñÿ äëÿâûïóêëûõ óíêöèé ñòîèìîñòè [63, 60℄. Äåçàãðåãàöèÿ óíêöèè èçïî îðìóëàì (1.8) çà âðåìÿkêóñî÷êîâ âûïîëíÿåòñÿO(k).Çàòåì ìîæíî èñïîëüçîâàòü âñå óïîìÿíóòûå àëãîðèòìû ìàêñèìèçàöèè ïîòîêà è íàõîæäåíèÿ ïîòîêà ìèíèìàëüíîé ñòîèìîñòè. Ýòî ïîòðåáóåò âðåìåíèO(F (km, n)),ñëîæíîñòü ñîîòâåòñòâóþùåãî àëãîðèòìà äëÿ ëèíåéíûõ óñèëåíèé,kãäåF (m, n) ìàêñèìàëüíîå êîëè÷å-ñòâî êóñî÷êîâ â êàæäîé óíêöèÿõ óñèëåíèÿ èëè ñòîèìîñòè.Òåîðåìà 3(àëãîðèòì ðåøåíèÿ âûïóêëîé çàäà÷è íàõîæäåíèÿ ïîòîêà ìèíèìàëüíîé ñòîèìî-ñòè â ñåòè ñ óñèëåíèÿìè â äóãàõ).Åñëè óñèëåíèå âîçðàñòàåò, âîãíóòî è êóñî÷íî-ëèíåéíî, à38ñòîèìîñòü âîçðàñòàåò, âûïóêëà è êóñî÷íî-ëèíåéíà, òî ñóùåñòâóåò àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî ïñåâäîïîòîêà ñëîæíîñòè O(F (km, n)), ãäå F (m, n) ñëîæíîñòü ñîîòâåòñòâóþùåãî àëãîðèòìà äëÿ ëèíåéíûõ óñèëåíèé, k êîëè÷åñòâî êóñî÷êîâ â óíêöèÿõóñèëåíèÿ è ñòîèìîñòè âìåñòå.Äîêàçàòåëüñòâî.àññìîòðèì ñëåäóþùèéàëãîðèòì ðåøåíèÿ âûïóêëîé çàäà÷è íàõîæäåíèÿîïòèìàëüíîãî ïîòîêà â ñåòè ñ óñèëåíèÿìè â äóãàõ:1.
Ïðîèçâîäèì â èñõîäíîé ñåòè äåçàãðåãàöèþ äóã òàê æå, êàê è â ïðåäûäóùåì ñëó÷àå,íî äóãà ðàçáèâàåòñÿ íà ÷àñòè äâîÿêî: êóñî÷êàìè óñèëåíèé è êóñî÷êàìè ñòîèìîñòåé.Òàêèì îáðàçîì, åñëè â äóãå çàäàíà êóñî÷íî-ëèíåéíàÿ óíêöèÿ óñèëåíèÿèçng êóñî÷êîâ(a, b)ïðåâðàòÿòñÿ âO(n)Òàêèì îáðàçîì, â ïðåîáðàçîâàííîé ñåòèâûïîëíÿåòñÿ çà âðåìÿO(km)ñîñòîÿùàÿpa , ñîñòîÿùàÿ èç np êóñî÷êîâ,è êóñî÷íî-ëèíåéíàÿ óíêöèÿ ñòîèìîñòèòî â ïðåîáðàçîâàííîé ñåòè âñå äóãèga ,ng + npâåðøèí èO(km)(÷òî çàâåäîìî ìåíüøå, ÷åìïàðàëëåëüíûõ äóã.äóã, à ïðåîáðàçîâàíèåO(F (km, n))).Òî, ÷òî çàäà÷àâ ïðåîáðàçîâàííîé ñåòè ýêâèâàëåíòíà çàäà÷å â èñõîäíîé ñåòè, äîêàçûâàåòñÿ ïîëíîñòüþàíàëîãè÷íî òåîðåìå î êîìïîçèöèè.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
