Составители:
Рубрика:
50
 òî æå âðåìÿ ïî ïîñòðîåíèþ ïóòè
µ
èìååì L(µ) = λ
n
, îòêóäà ñëåäóåò
L(µ) ≤ L( v
0,
v
i
1
, v
i
2
,,v
i
m
,
v
n
),
ò. å. µ = ( v
0
=v
p
k
,v
p
k1
, ... ,v
p
2
, v
p
1
, v
n
) ìèíèìàëüíûé ïóòü.
Êàê ïîêàçàíî â ïðèìåðå, ìèíèìàëüíûé ïóòü â ãðàôå ìîæåò áûòü íå
îäèí.
3.1.3. Ïîñòðîåíèå ìàøèííîãî àëãîðèòìà ïîèñêà
ìèíèìàëüíûõ ïóòåé â ãðàôå
Èñõîäíûìè äàííûìè ÿâëÿþòñÿ ìàòðèöà ñìåæíîñòè ãðàôà äëÿ n âåð-
øèí (||S||
n×n
) è ìàòðèöà äëèí äóã ãðàôà (||L||
n×n
), íàïðèìåð äëÿ ãðàôà íà
ðèñ. 3.2 ýòè ìàòðèöû èìåþò âèä, ïðèâåäåííûé íà ðèñ. 3.3.
Ìàòðèöà äëèí äóã ãðàôà ïî ñóòè âêëþ÷àåò âñþ èíôîðìàöèþ î ãðà-
ôå, ÷òî äåëàåò ìàòðèöó ñìåæíîñòè èçëèøíåé äëÿ äàííîé çàäà÷è. Äëÿ
ïîñòðîåíèÿ àëãîðèòìà íåîáõîäèìû âåêòîð ìåòîê âåðøèí (Ì) è ìàòðèöà
ðåçóëüòàòîâ, ñîäåðæàùàÿ âåðøèíû êðàò÷àéøèõ ïóòåé (||Ê||
n×n
).
Ïîñòðîåíèå ìàøèííîãî àëãîðèòìà îñíîâàíî íà àíàëèçå ìàòðèöû
äëèí äóã ãðàôà (L), ïîñòåïåííîì çàïîëíåíèè âåêòîðà ìåòîê âåðøèí
(Ì) íîâûìè ìåòêàìè è ïîëó÷åíèè ìàòðèöû êðàò÷àéøèõ ïóòåé (Ê).
 ðåçóëüòàòå âåêòîð ìåòîê (Ì) îòðàæàåò ìèíèìàëüíûå ðàññòîÿ-
íèÿ ìåæäó íà÷àëüíîé âåðøèíîé v
0
è îñòàëüíûìè âåðøèíàìè. Ìàò-
ðèöà êðàò÷àéøèõ ïóòåé (Ê) îòðàæàåò èíôîðìàöèþ î ïîäãðàôå ìèíè-
ìàëüíûõ ïóòåé èñõîäíîãî ãðàôà ìåæäó íà÷àëüíîé âåðøèíîé v
0
è êî-
íå÷íîé âåðøèíîé v
n.
S : L :
0123456 0123456
00111100 00789 5100
10000100 10000400
21001010 27003060
31000111 3500024 61
40000001 40000008
50001001 50002006
60000010 60000040
Ðèñ. 3.3. Ìàòðèöû ñìåæíîñòè è äëèí äóã ãðàôà
Страницы
- « первая
- ‹ предыдущая
- …
- 48
- 49
- 50
- 51
- 52
- …
- следующая ›
- последняя »
