Составители:
Рубрика:
46
 äàëüíåéøåì ìû áóäåì ïîëüçîâàòüñÿ òåðìèíîëîãèåé, ñîîòâåòñòâó-
þùåé ðàññòîÿíèÿì, õîòÿ âñåãäà íóæíî ïîìíèòü è î äðóãèõ èíòåðïðåòà-
öèÿõ. Îòìåòèì äâå âàæíåéøèå õàðàêòåðèñòèêè äëèíû, ñóùåñòâåííûå
äëÿ äàëüíåéøåãî ðàññìîòðåíèÿ.
1. Äëèíà äîëæíà áûòü àääèòèâíà (äëèíà ñîâîêóïíîñòè äóã ðàâíà
ñóììå äëèí îòäåëüíûõ äóã).
2. Äëèíà äîëæíà èñïîëüçîâàòüñÿ â êà÷åñòâå öåëåâîé ôóíêöèè, êîòî-
ðóþ íåîáõîäèìî îïòèìèçèðîâàòü (ìèíèìèçèðîâàòü èëè ìàêñèìèçèðî-
âàòü) ïðè îãðàíè÷åíèÿõ íà äîïóñòèìûå ìíîæåñòâà äóã.
Äëÿ ãðàôà ñ êîíòóðàìè (öèêëè÷åñêîãî) ìîæíî ãîâîðèòü òîëüêî î çà-
äà÷å îòûñêàíèÿ ìèíèìàëüíûõ ïóòåé ãðàôà, à â àöèêëè÷åñêîì ãðàôå ìîæíî
èñêàòü êàê ìèíèìàëüíûé, òàê è ìàêñèìàëüíûé ïóòü ìåæäó âåðøèíàìè
ãðàôà.
3.1. Ïîèñê ìèíèìàëüíûõ ïóòåé â ãðàôå
Ïîñòàíîâêà çàäà÷è. Äëÿ ïðîèçâîëüíîãî îðãðàôà G(V, U), ãäå äëÿ
∀u ∈U ñîïîñòàâëåíî ÷èñëî L(u) > 0 (äëèíà äóãè), íåîáõîäèìî íàéòè
ïóòü
µ
ìèíèìàëüíîé äëèíû, ñîåäèíÿþùèé âåðøèíó v
0
c âåðøèíîé v
n
.
3.1.1. Ìåòîä ðåøåíèÿ çàäà÷è ïîèñêà ìèíèìàëüíîãî ïóòè
Ñóùåñòâóåò íåñêîëüêî ìåòîäîâ ðåøåíèÿ ýòîé çàäà÷è, ñðåäè êîòîðûõ
ðàññìîòðèì àëãîðèòì Ôîðäà, îïèñûâàåìûé ñëåäóþùèìè ïðàâèëàìè,
êîòîðûå ìîæíî ðàçäåëèòü íà äâà ýòàïà: ïðÿìîé õîä âû÷èñëåíèå è íà-
çíà÷åíèå ìåòîê âåðøèíàì ãðàôà; îáðàòíûé õîä îïðåäåëåíèå ìèíè-
ìàëüíîãî ïóòè.
Ïðÿìîé õîä.
1. Íàçíà÷åíèå íîìåðîâ âåðøèíàì. Ïåðåèìåíîâàòü âåðøèíû ãðà-
ôà G òàê, ÷òîáû èñõîäíàÿ âåðøèíà ïîëó÷èëà íîìåð 0, åñëè ýòî íåîá-
õîäèìî.
2. Ïðèñâîåíèå íà÷àëüíûõ ìåòîê. Ïðèñâîèòü êàæäîé âåðøèíå v
i
ìåò-
êó λ
i
òàê, ÷òîáû λ
0
= 0, λ
i
= ∞ ïðè i > 0 (ïîä ñèìâîëîì ∞ çäåñü ñëåäóåò
ïîíèìàòü äîñòàòî÷íî áîëüøîå ïîëîæèòåëüíîå çíà÷åíèå).
3. Óìåíüøåíèå ìåòîê. Íàéòè òàêóþ äóãó
(, )
ij
vv
, äëÿ êîòîðîé
λ
j
λ
i
> L
(, )
ij
vv
. Ó âåðøèíû
j
v
çàìåíèòü ìåòêó λ
j
íà íîâóþ ìåòêó
λ
'
j
= λ
i
+ L
(, )
ij
vv
, åñëè λ
'
j
< λ
j
.
4. Ïåðåñ÷åò ìåòîê. Ïðèìåíÿòü ïðàâèëî 3 äî òåõ ïîð, ïîêà äëÿ êàæäîé
äóãè
(, )
ij
vv
íå ñòàíåò ñïðàâåäëèâûì íåðàâåíñòâî λ
j
λ
i
≥ L
(, )
ij
vv
.
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
