Диссертация (1149954), страница 4
Текст из файла (страница 4)
Íîåå ìîæíî ïðèâåñòè ê îáîáùåííîé ÎÄÑ ñ ïîñòîÿííîé ïðîäîëæèòåëüíîñòüþ âðåìåíè, äîáàâèâ ê êàæäîé òåðìèíàëüíîé âåðøèíåy1 , y2 , . . . ykyãðàà äîñòàòî÷íîå êîëè÷åñòâî èêòèâíûõ âåðøèíòàê, ÷òîáû äëèíû âñåõ íåïðîäîëæàåìûõ ïóòåé ñòàëè îäèíàêîâû.15Êðîìå òîãî, â ïðîèçâîëüíîì âûðîâíåííîì ãðàå ïðîñòðàíñòâî ýòî ìíîæåñòâî äîñòèæèìîñòè â ìîìåíòtX(t)ñîñòîÿíèé ñèñòåìûèç âñåõ êîðíåâûõ âåðøèí ãðàà.  îáùåì ñëó-÷àå, îíî íåïîñòîÿííîå (ìåíÿþùååñÿ ñî âðåìåíåì). Íî ìîæíî ñ÷èòàòü, ÷òî ìíîæåñòâî âñåõñîñòîÿíèé ñèñòåìû X=St∈TX(t). áåñêîíå÷íîì ãðàå äëèíû ïóòåé ìîãóò áûòü íåîãðàíè÷åíû.
Íî â íàñòîÿùåé ðàáîòåìû ðàññìàòðèâàåì ñèñòåìû íà êîíå÷íûõ (ñðåäíåñðî÷íûõ) èíòåðâàëàõ âðåìåíè è ïîýòîìóïðåäïîëàãàåì, ÷òî äëèíû âñåõ ïóòåé â ÎÄÑ îãðàíè÷åíû.  ÷àñòíîñòè, åñëè â êàæäîé ïîçèöèèÎÄÑ ñ êîíå÷íûì âðåìåíåì ñóùåñòâóåò òîëüêî êîíå÷íîå ÷èñëî âàðèàíòîâ âûáîðà, òî ãðàêîíå÷åí è, ñëåäîâàòåëüíî, äëèíû âñåõ ïóòåé îãðàíè÷åíû [7℄. Íî ìû áóäåì ðàññìàòðèâàòü èâîçìîæíîñòü áåñêîíå÷íîãî ÷èñëà âàðèàíòîâ âûáîðà è îãðàíè÷åííîãî ìíîæåñòâà äëèí ïóòåé.Áåñêîíå÷íûé ãðà ñ îãðàíè÷åííûì ìíîæåñòâîì äëèí ïóòåé, êàê è êîíå÷íûé, ìîæíî ñâåñòè êãðàó ÎÄÑ, äîáàâèâ â êîíåö èêòèâíûå âåðøèíû è îïðåäåëèâ ìíîæåñòâî ñîñòîÿíèé ñèñòåìûêàêX=St∈TX(t).Íàêîíåö, ïðîèçâîëüíûé (íåâûðîâíåííûé) áåñêîíòóðíûé ãðà(X ′ , M)ñ îãðàíè÷åííûììíîæåñòâîì äëèí ïóòåé ìîæíî ñâåñòè ê âûðîâíåííîìó ñëåäóþùèì îáðàçîì:1.
Ïðèñâîèòü êàæäîé âåðøèíååò äóãà(x1 , x2 ) ∈ M ,òîx∈Xòàêóþ âðåìåííóþ ìåòêót(x1 ) < t(x2 ).t(x) ∈ T , ÷òî åñëè ñóùåñòâó-Ñóùåñòâîâàíèå òàêèõ ìåòîê äëÿ áåñêîíòóðíîãîãðàà ñëåäóåò èç ñóùåñòâîâàíèÿ åãî òîïîëîãè÷åñêîé ñîðòèðîâêè [30℄.2. àñïîëîæèòüíàêàæäîéäóãå((x, t(x)), (y, t(y)))èêòèâíûåâåðøèíû(x, t(x) +1), (x, t(x) + 2, . . . , (x, t(y) − 1)). ðàçäåëå 2.3.2 ïðèâåäåí ïðèìåð ñâåäåíèÿ ïðîèçâîëüíîãî íåâûðîâíåííîãî ãðàà ê ãðàó ÎÄÑ. ðàáîòå ðàññìàòðèâàþòñÿ îïòèìèçàöèîííûå çàäà÷è, â êîòîðûõ ìíîæåñòâî àëüòåðíàòèâ ýòî ïó÷îê òðàåêòîðèéåêòîðèé Äëÿ ÎÄÑP (x, t).Ïðîñòåéøèé ñëó÷àé êðèòåðèÿ îïòèìàëüíîñòè íà ïó÷êå òðà-èíòåãðàëüíûé âûèãðûø H(xt , xt+1 , .
. . , xm ) = gt (xt ) + gt+1 (xt+1 ) + · · · + gm (xm ).(D, x0 ) ñçàäàííûì íà÷àëüíûì ñîñòîÿíèåìx0çàäà÷à ìàêñèìèçàöèè èíòåãðàëüíîãîâûèãðûøà ñâîäèòñÿ ê ïîèñêó îïòèìàëüíîãî ïóòè â áåñêîíòóðíîì ãðàå [1℄. Åãî ìîæíî íàéòèàëãîðèòìîì Áåëëìàíà-Ôîðäà [1℄ èëè áîëåå ïðîñòûì àëãîðèòìîì äëÿ áåñêîíòóðíûõ ãðàîâ[30℄.161.1.3Îáîáùåííûå äèíàìè÷åñêèå ñèñòåìû, ðàñïðåäåëåííûå â ïðîñòðàíñòâå äàííîì ðàçäåëå îïðåäåëåíû óïðàâëÿåìûå äèíàìè÷åñêèå ñèñòåìû, ðàñïðåäåëåííûå â ïðîñòðàíñòâå. Îíè ìîäåëèðóþò ðàñïðåäåëåííûå ìåíÿþùèåñÿ âî âðåìåíè óïðàâëÿåìûå ñèñòåìû(íàïðèìåð, ñîöèàëüíûå èëè ýêîíîìè÷åñêèå). Âîçìîæíû 2 ðàçëè÷íûõ ñåòåâûõ ïðåäñòàâëåíèÿïðîñòðàíñòâà-âðåìåíè ñèñòåìû:1. Ïðåäñòàâëåíèå â âèäå ãðàà ÎÄÑ ñ äèñêðåòíûì âðåìåíåì, ðàññìîòðåííîå â ïðåäûäóùåì ðàçäåëå;2. Ïðåäñòàâëåíèå â âèäå ãðàà ñèñòåìû, ðàçâåðíóòîãî âî âðåìåíè.Âòîðîå ïðåäñòàâëåíèå íóæíî, íàïðèìåð, äëÿ óìåíüøåíèÿ êîëè÷åñòâà âîçìîæíûõ ñîñòîÿíèé ñèñòåìû.
Ïóñòü óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà ñîñòîèò èç|L| = nóçëîâ, ðàñ-ïðåäåëåííûõ â ïðîñòðàíñòâå, êàæäûé èç êîòîðûõ ìîæåò íàõîäèòüñÿ â îäíîì èçñîñòîÿíèé. Êðîìå òîãî, èìååòñÿ|M| = m|X| = xñîåäèíåíèé óçëîâ, ñîñòîÿíèÿ êîòîðûõ îïðåäåëÿ-þò âçàèìîäåéñòâèÿ ìåæäó óçëàìè. Ïóñòü êàæäîå ñîåäèíåíèå ìîæåò íàõîäèòüñÿ â îäíîì èç|U| = uñîñòîÿíèé. Ôîðìàëüíî ìíîæåñòâî ñîñòîÿíèé ñèñòåìû ýòî äåêàðòîâî ïðîèçâåäåíèåìíîæåñòâ ñîñòîÿíèé óçëîâ è ìíîæåñòâ ñîñòîÿíèé ñîåäèíåíèé. Òîãäà ýòà ñèñòåìà èìååò î÷åíüìíîãî âîçìîæíûõ ñîñòîÿíèé:èìååòèsxn umO(sm)âåðøèí èxn um ,O(sx2n u2m )à ñëåäîâàòåëüíî, äëÿ|T | = sìîìåíòîâ âðåìåíè åå ãðàäóã. ðà æå, ðàçâåðíóòûé âî âðåìåíè, èìååòsnâåðøèíäóã, ÷òî ãîðàçäî ìåíüøå.Îïðåäåëåíèå 7. Ñòàòè÷åñêàÿ ðàñïðåäåëåííàÿ ñèñòåìà â äèñêðåòíîì ïðîñòðàíñòâåíàáîð(L, M, {Sl }l∈L , {U(i,j)}(i,j)∈M , {Si (u)}i∈L , {Ui (s))}i∈L ,• (L, M) ýòîãäå ãðà, îïèñûâàþùèé äèñêðåòíîå ïðîñòðàíñòâî, â êîòîðîì ðàñïîëîæåíà ñèñòå-ìà;• Sl ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèés l ∈ Sll∈L(ïðîèçâîëüíîå íåïóñòîå(i, j) ∈ M(ïðîèçâîëüíîå íåïóñòîåâåðøèíûìíîæåñòâî);• U(i,j) ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèéu(i,j)äóãèìíîæåñòâî);• Si :QU(j,i) → 2Si(j,i)∈M• Ui : Si → 2Q(i,j)∈MU(j,i) ìíîæåñòâåííîå îòîáðàæåíèå; ìíîæåñòâåííîå îòîáðàæåíèå.17Ñîñòîÿíèåñòàòè÷åñêîé ðàñïðåäåëåííîé ñèñòåìû ýòî íàáîð ïàðàìåòðîâ âåðøèí è äóã({si }i∈L , {u(i,j)}(i,j)∈M )òàêîé, ÷òîsi ∈ Si ({u(j,i)}(j,i)∈M )ui = {u(i,j) }(i,j)∈M ∈ Ui (si )Ìîæíî ðàññìàòðèâàòü àíàëîãè÷íûå îïðåäåëåíèÿ óïðàâëÿåìîé ñåòåâîé ñèñòåìû íà ìóëüòèãðàå òî åñòü ãðàå ñ êðàòíûìè äóãàìè.
Íî ñîñòîÿíèå íàáîðà äóã ìîæíî ðàññìàòðèâàòüêàê âåêòîð ñîñòîÿíèé äóã, è òîãäà ìóëüòèãðà ñâîäèòñÿ ê ïðîñòîìó ãðàó.àññìîòðèì òåïåðü äèíàìè÷åñêèå ñèñòåìû, ðàñïðåäåëåííûå â ïðîñòðàíñòâå, â êîòîðûõâîçäåéñòâèå ïåðåäàåòñÿ îò îäíîé âåðøèíû ê äðóãîé ïî äóãå çà êîíå÷íîå âðåìÿ. Ñîñòîÿíèåñèñòåìû ýòî íàáîð ñîñòîÿíèé åå âåðøèí è äóã:S=Ql∈LSl ×Qm∈MUm . Äóãà ïåðåíîñ÷èêâîçäåéñòâèÿ. Ïîñêîëüêó âðåìÿ ìû ñ÷èòàåì äèñêðåòíûì, ìîæíî ñâåñòè âîçäåéñòâèå ýëåìåíòàaíà ýëåìåíòbçà âðåìÿnên-êðàòíîìóâîçäåéñòâèþ çà åäèíè÷íîå âðåìÿ, ââåäÿ èêòèâíûåñîñòîÿíèÿ, êàê îïèñàíî â ïðåäûäóùåì ðàçäåëå. Òîãäà ñîñòîÿíèå ñèñòåìû â ïîñëåäóþùèéìîìåíò âðåìåíèìåíès(t).s(t + 1)çàâèñèò òîëüêî îò ñîñòîÿíèÿ ñèñòåìû â ïðåäûäóùèé ìîìåíò âðå-Îòñþäà ïîëó÷àåì îïðåäåëåíèå (â äàííîì îïðåäåëåíèè èç ñîîáðàæåíèé óäîáñòâàóïðàâëåíèÿ íå çàäàíû ÿâíî):Îïðåäåëåíèå 8.
Äèíàìè÷åñêàÿ ðàñïðåäåëåííàÿ ñèñòåìà â äèñêðåòíîì ïðîñòðàíñòâåýòî íàáîð(L, M, T, {Sl (t)}l∈L,• (L, M)t∈T , {U(i,j) (t)}(i,j)∈M, t∈T , {Si (u, t)}i∈L , {Ui (s, t))}i∈L , ãäå ãðà, îïèñûâàþùèé äèñêðåòíîå ïðîñòðàíñòâî, â êîòîðîì ðàñïîëîæåíà ñèñòå-ìà;• T äèñêðåòíîå ìíîæåñòâî ìîìåíòîâ âðåìåíè;• Sl (t) ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèéâðåìåíè• U(i,j) (t)Qtâ êàæäûé ìîìåíòu(i,j)äóãè(i, j) ∈ Mâ êàæäûé ìîìåíò(ïðîèçâîëüíîå íåïóñòîå ìíîæåñòâî);(j,i)∈MU(j,i) × T → 2Si• Ui : Si × T → 2Ñîñòîÿíèål ∈ Lâåðøèíû(ïðîèçâîëüíîå íåïóñòîå ìíîæåñòâî); ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèéâðåìåíè• Si :ts l ∈ SlQ(i,j)∈MU(j,i) ìíîæåñòâåííîå îòîáðàæåíèå; ìíîæåñòâåííîå îòîáðàæåíèå.äèíàìè÷åñêîé ðàñïðåäåëåííîé ñèñòåìû ýòî íàáîð ïàðàìåòðîâ âåðøèí è äóã18({si (t)}i∈L , {u(i,j)(t)}(i,j)∈M )òàêîé, ÷òîsi (0) ∈ Si (0)si (t) ∈ Si ({u(j,i)(t − 1)}(j,i)∈M , t)ui (t) = {u(i,j) (t)}(i,j)∈M ∈ Ui (si (t), t)Óòâåðæäåíèå 1.1.2.
Äèíàìè÷åñêàÿ ñèñòåìà ýêâèâàëåíòíà ñòàòè÷åñêîé ñèñòåìå â ãðà-å, ðàçâåðíóòîì âî âðåìåíè [34℄ òî åñòü â ãðàå, ìíîæåñòâî âåðøèí êîòîðîãî ïðîñòðàíñòâî-âðåìÿ ñèñòåìûL′ = L × T , àäèíàìè÷åñêèå äóãè Γ(y, t) = {(y ′, t + 1) | y ′ ∈Γ(y)} ïîêàçûâàþò äèíàìèêó âçàèìíîãî âëèÿíèÿ ýëåìåíòîâ äðóã íà äðóãà. Ïðè ýòîì âåð-øèíå l â ìîìåíò âðåìåíè t ñîîòâåòñòâóåò âåðøèíà (l, t) â ãðàå, ðàçâåðíóòîì âî âðåìåíè,à äóãå (i, j) â ìîìåíò âðåìåíè t ñîîòâåòñòâóåò äóãà ((i, t), (j, t + 1)) â ãðàå, ðàçâåðíóòîìâî âðåìåíè.Äîêàçàòåëüñòâî.Çàìå÷àíèåÑëåäóåò èç îïðåäåëåíèÿ 8.1.1.5. Ïî ñóòè, äèíàìè÷åñêàÿ ñèñòåìà, ðàñïðåäåëåííàÿ â ïðîñòðàíñòâå ýòî àâ-òîìàòíàÿ ñåòü [59℄ èëè êëåòî÷íûé àâòîìàò íà ãðàå. Êëåòî÷íûå àâòîìàòû íà ãðààõ èñïîëüçóþòñÿ òàêæå â èçè÷åñêèõ ìîäåëÿõ äëÿ îïèñàíèÿ äèñêðåòíîãî ïðîñòðàíñòâà-âðåìåíè[88℄.Çàìå÷àíèå1.1.6. Ìîæíî òàêæå ðàññìàòðèâàòü ñèñòåìó, ñòðóêòóðà êîòîðîé äèíàìè÷åñêè ìå-íÿåòñÿ ò.å.
ýëåìåíòû ïîÿâëÿþòñÿ, èñ÷åçàþò, ðàçìíîæàþòñÿ è ñëèâàþòñÿ, à ñâÿçè ìåæäóýëåìåíòàìè ïîÿâëÿþòñÿ è èñ÷åçàþò. Ýòà ñèñòåìà àíàëîãè÷íî èçîáðàæàåòñÿ ãðàîì, ðàçâåðíóòûì âî âðåìåíè. Íî ìû ðàññìàòðèâàåì òîëüêî ñèñòåìû ñ èêñèðîâàííîé ñòðóêòóðîé.Çàìå÷àíèå1.1.7. Âîîáùå ãîâîðÿ, ñîñòîÿíèå âåðøèíûlâ ìîìåíò âðåìåíèçàâèñåòü îò ñîñòîÿíèÿ òîé æå âåðøèíû â ìîìåíò âðåìåíèt.t+1íå îáÿçàíîÒàêàÿ çàâèñèìîñòü åñòü òîëüêîâ òîì ñëó÷àå, â ýòîé âåðøèíå åñòü äèíàìè÷åñêàÿ äóãà-ïåòëÿ.Ïðèìåð 1.àññìîòðèì ðàñïðåäåëåííóþ â ïðîñòðàíñòâå ÎÄÑ, ïðîñòðàíñòâî êîòîðîé îä-íîìåðíûé ïóòü(L, M) = (a1 , a2 , .
. . am ),âñå äóãè â êîòîðîì äèíàìè÷åñêèå. Ïóñòü êàæäàÿâåðøèíà ìîæåò íàõîäèòüñÿ â 2 ñîñòîÿíèÿõ: âêëþ÷åíî è âûêëþ÷åíî, ïðè÷åì âåðøèíàâ ìîìåíòtâêëþ÷åíà òîãäà è òîëüêî òîãäà, êîãäà âêëþ÷åíà âåðøèíàt−1. Òàêàÿ ÎÄÑ ìîäåëèðóåòai−1aiâ ìîìåíò âðåìåíèäâèæåíèå îáúåêòîâ ñëåâà íàïðàâî ñî ñêîðîñòüþ 1.  íà÷àëüíûéìîìåíò âðåìåíè îáúåêòîâ ìîæåò áûòü ñêîëüêî óãîäíî è îíè ìîãóò áûòü ðàñïîëîæåíû êàêóãîäíî. Íî â äàëüíåéøåì ïåðâîíà÷àëüíîå ðàñïîëîæåíèå îáúåêòîâ íå ìåíÿåòñÿ è îíè íå âëèÿþò äðóã íà äðóãà.
Ïðè ýòîì êàæäûé îáúåêò ìîæåò, â ñâîþ î÷åðåäü, ïðåäñòàâëÿòü ñîáîé ñåòü19ñî ñêîëü óãîäíî ñëîæíûì âçàèìîäåéñòâèåì îáúåêòîâ. Ñîîòâåòñòâåííî êàæäàÿ íåïîäâèæíàÿâåðøèíà1.2aiíå âëèÿåò ñàìà íà ñåáÿ çàòî êàæäûé äâèæóùèéñÿ îáúåêò âëèÿåò ñàì íà ñåáÿ.Àëãîðèòìû íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêà â ñåòèñ íåëèíåéíûìè óñèëåíèÿìè1.2.1Ôîðìàëèçàöèÿ è îïòèìèçàöèÿ ïîòîêîâ â ëîãèñòè÷åñêîé ñèñòåìå ðàçäåëå 1.1.3 äàíî îïðåäåëåíèå ñòàòè÷åñêîé óïðàâëÿåìîé ðàñïðåäåëåííîé ñèñòåìû â äèñêðåòíîì ïðîñòðàíñòâå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
