Математические методы в экономике. Копылов Г.Н - 37 стр.

UptoLike

ВУЗ: 

ВолГУ | Волгоград

Составители: 

Рубрика: 

37
Íàõîæäåíèå äëèí êðàò÷àéøèõ ïóòåé, âûõîäÿùèõ èç âåðøè-
íû À, áóäåì ïðîèçâîäèòü, èñïîëüçóÿ àëãîðèòì ðàññòàíîâêè ìå-
òîê. Â ïðîöåññå ðàáîòû àëãîðèòìà êàæäîé âåðøèíå áóäåò ïðèïè-
ñàíî íåêîòîðîå ÷èñëî, â äàëüíåéøåì ýòè ÷èñëà ìû áóäåì íàçû-
âàòü ìåòêàìè. Åñëè êàêîé-òî âåðøèíå ïðèïèñàíà ìåòêà, ðàâíàÿ
d, òî ýòî çíà÷èò, ÷òî ñóùåñòâóåò ïóòü èç âåðøèíû À â ýòó âåð-
øèíó äëèíîé d. Åñëè íàéäåí áîëåå êîðîòêèé ïóòü, òî çíà÷åíèå
ìåòêè çàìåíÿåòñÿ íà ìåíüøåå. Ìåòêè ìîãóò áûòü âðåìåííûìè
èëè ïîñòîÿííûìè. Ïîñòîÿííûå ìåòêè áóäåì îòìå÷àòü çíà÷êîì
*
,
íå îòìå÷åííûå òàêèì çíà÷êîì — âðåìåííûå. Íàïðèìåð, l
i
— âðå-
ìåííàÿ, à l
i
*
— ïîñòîÿííàÿ. Ìåòêà ñòàíîâèòñÿ ïîñòîÿííîé â òîì
ñëó÷àå, åñëè îíà ñîîòâåòñòâóåò ñàìîìó êîðîòêîìó ïóòè èç âåð-
øèíû À â äàííóþ âåðøèíó. Çàäà÷à ðåøåíà, åñëè âñå ìåòêè ñòàëè
ïîñòîÿííûìè.
Èòàê, âûïèøåì øàãè íàøåãî àëãîðèòìà.
Øàã 1. Êàæäîé âåðøèíå i ïðèïèñûâàåì íåêîòîðîå ÷èñëî l
i
,
ðàâíîå äëèíå ñàìîãî êîðîòêîãî, èçâåñòíîãî íà äàííûé ìîìåíò
ïóòè èç âåðøèíû À â äàííóþ âåðøèíó. Âíà÷àëå ýòî l
À
= 0, à l
2
=
l
3
=... = l
Â
= ∞. Íå îãðàíè÷èâàÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî
âåðøèíå À ñîîòâåòñòâóåò âåðøèíà ñ íîìåðîì 1, à âåðøèíå Â —
âåðøèíà ñ ñàìûì áîëüøèì íîìåðîì. Íà äàííîì ýòàïå âñå ìåòêè
âðåìåííûå.
Øàã 2. Ñðåäè âðåìåííûõ ìåòîê èùåì ìèíèìàëüíóþ. Íàïðè-
ìåð, ýòî âåðøèíà i. Ïðîñìàòðèâàåì âñå ðåáðà, âûõîäÿùèå èç
âåðøèíû i, è ïðîâåðÿåì âûïîëíåíèå íåðàâåíñòâà
l
i
+ a
ij
< l
j
. (3.1)
Äëÿ òåõ âåðøèí j, äëÿ êîòîðûõ îíî ñïðàâåäëèâî, çàìåíÿåì
ìåòêó l
j
íà l
i
+ a
ij
, ýòà âåëè÷èíà ñîîòâåòñòâóåò ïóòè èç À â âåðøè-
íó i äëèíîé l
i
, à çàòåì ïî ðåáðó a
ij
â âåðøèíó j. Ìåòêà l
i
ñòàíîâèò-
ñÿ ïîñòîÿííîé.
Çàäà÷à ðåøåíà, åñëè âñå ìåòêè ïîñòîÿííûå. Åñëè æå ñðåäè
ìåòîê åñòü âðåìåííûå, òî ïîâòîðÿåì øàã 2.
Äëèíà êðàò÷àéøåãî ïóòè èç À â  ðàâíà l
Â
*
.
Ïðèìåð. Ðàññìîòðèì ãðàô, èìåþùèé äåâÿòü âåðøèí è 12
ðåáåð (ñì. ÷åðòåæ).  íåì âûäåëåíû âåðøèíû À è Â, íåîáõîäèìî
íàéòè êðàò÷àéøèé ïóòü èç À â Â.
      Íàõîæäåíèå äëèí êðàò÷àéøèõ ïóòåé, âûõîäÿùèõ èç âåðøè-
íû À, áóäåì ïðîèçâîäèòü, èñïîëüçóÿ àëãîðèòì ðàññòàíîâêè ìå-
òîê. Â ïðîöåññå ðàáîòû àëãîðèòìà êàæäîé âåðøèíå áóäåò ïðèïè-
ñàíî íåêîòîðîå ÷èñëî, â äàëüíåéøåì ýòè ÷èñëà ìû áóäåì íàçû-
âàòü ìåòêàìè. Åñëè êàêîé-òî âåðøèíå ïðèïèñàíà ìåòêà, ðàâíàÿ
d, òî ýòî çíà÷èò, ÷òî ñóùåñòâóåò ïóòü èç âåðøèíû À â ýòó âåð-
øèíó äëèíîé d. Åñëè íàéäåí áîëåå êîðîòêèé ïóòü, òî çíà÷åíèå
ìåòêè çàìåíÿåòñÿ íà ìåíüøåå. Ìåòêè ìîãóò áûòü âðåìåííûìè
èëè ïîñòîÿííûìè. Ïîñòîÿííûå ìåòêè áóäåì îòìå÷àòü çíà÷êîì *,
íå îòìå÷åííûå òàêèì çíà÷êîì — âðåìåííûå. Íàïðèìåð, li — âðå-
ìåííàÿ, à li* — ïîñòîÿííàÿ. Ìåòêà ñòàíîâèòñÿ ïîñòîÿííîé â òîì
ñëó÷àå, åñëè îíà ñîîòâåòñòâóåò ñàìîìó êîðîòêîìó ïóòè èç âåð-
øèíû À â äàííóþ âåðøèíó. Çàäà÷à ðåøåíà, åñëè âñå ìåòêè ñòàëè
ïîñòîÿííûìè.
      Èòàê, âûïèøåì øàãè íàøåãî àëãîðèòìà.
      Øàã 1. Êàæäîé âåðøèíå i ïðèïèñûâàåì íåêîòîðîå ÷èñëî li,
ðàâíîå äëèíå ñàìîãî êîðîòêîãî, èçâåñòíîãî íà äàííûé ìîìåíò
ïóòè èç âåðøèíû À â äàííóþ âåðøèíó. Âíà÷àëå ýòî lÀ = 0, à l2 =
l3 =... = l = ∞. Íå îãðàíè÷èâàÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî
âåðøèíå À ñîîòâåòñòâóåò âåðøèíà ñ íîìåðîì 1, à âåðøèíå Â —
âåðøèíà ñ ñàìûì áîëüøèì íîìåðîì. Íà äàííîì ýòàïå âñå ìåòêè
âðåìåííûå.
      Øàã 2. Ñðåäè âðåìåííûõ ìåòîê èùåì ìèíèìàëüíóþ. Íàïðè-
ìåð, ýòî âåðøèíà i. Ïðîñìàòðèâàåì âñå ðåáðà, âûõîäÿùèå èç
âåðøèíû i, è ïðîâåðÿåì âûïîëíåíèå íåðàâåíñòâà
                               li + aij < lj .                  (3.1)
      Äëÿ òåõ âåðøèí j, äëÿ êîòîðûõ îíî ñïðàâåäëèâî, çàìåíÿåì
ìåòêó lj íà li + aij, ýòà âåëè÷èíà ñîîòâåòñòâóåò ïóòè èç À â âåðøè-
íó i äëèíîé li, à çàòåì ïî ðåáðó aij â âåðøèíó j. Ìåòêà li ñòàíîâèò-
ñÿ ïîñòîÿííîé.
      Çàäà÷à ðåøåíà, åñëè âñå ìåòêè ïîñòîÿííûå. Åñëè æå ñðåäè
ìåòîê åñòü âðåìåííûå, òî ïîâòîðÿåì øàã 2.
      Äëèíà êðàò÷àéøåãî ïóòè èç À â  ðàâíà lÂ*.
      Ïðèìåð. Ðàññìîòðèì ãðàô, èìåþùèé äåâÿòü âåðøèí è 12
ðåáåð (ñì. ÷åðòåæ).  íåì âûäåëåíû âåðøèíû À è Â, íåîáõîäèìî
íàéòè êðàò÷àéøèé ïóòü èç À â Â.




                                 37

Страницы