Xem mẫu
- Kü thuËt t×m ®−êng ®i ng¾n nhÊt
trªn b¶n ®å
KS. l−u v¨n giang
Trung t©m biªn tËp vμ c«ng nghÖ cao
Nhμ xuÊt b¶n B¶n ®å
Tãm t¾t: Bμi b¸o nãi vÒ kü thuËt t×m ®−êng ®i cã ®é dμi ng¾n nhÊt cña hai ®iÓm bÊt kú
trªn b¶n ®å vμ ®Ò xuÊt mét sè øng dông kü thuËt nμy trong thùc tÕ.
Summary: In this paper we consider the details of the routing algorith (the shortest path
on the graph) and some applications from the result in the practice.
i. ®Æt vÊn ®Ò
Trong mét sè tr−êng hîp sö dông b¶n ®å ®Ó tra cøu ®−êng ®i tíi ®iÓm nµo ®ã th−êng xuÊt
hiÖn c©u hái lµm thÕ nµo ®Ó x¸c ®Þnh ®−êng ®i ®Õn ®ã lµ ng¾n nhÊt? Trong ph¹m vi hÑp hoÆc
m¹ng l−íi giao th«ng ®¬n gi¶n Ýt ®−êng ®i th× cã thÓ t×m ngay ®−îc c©u tr¶ lêi. HÇu hÕt c¸c
tr−êng hîp cßn l¹i lµ khã kh¨n. VÊn ®Ò ®Æt ra lµ cÇn x©y dùng c¬ së kü thuËt t×m ®−êng ®i ng¾n
nhÊt gi÷a hai ®iÓm x¸c ®Þnh trªn b¶n ®å trong thêi gian nhá nhÊt ®¸p øng ngay yªu cÇu sö
dông.
ii. c¬ së cña kü thuËt t×m ®−êng ®i ng¾n nhÊt trªn b¶n ®å
Ph¸t biÓu bµi to¸n: Cho hai ®iÓm bÊt k× trªn b¶n ®å. H·y chØ ra ®−êng ®i cã ®é dµi ng¾n
nhÊt gi÷a hai ®iÓm ®ã trªn c¬ së hÖ thèng giao th«ng cña b¶n ®å.
1. C¬ së to¸n häc gi¶i bµi to¸n
C¬ së to¸n häc cña vÊn ®Ò nµy thùc ra ®· ®−îc to¸n häc gi¶i quyÕt tõ rÊt l©u. Cã rÊt nhiÒu
ph−¬ng ph¸p kh¸c nhau, trong bµi nµy giíi thiÖu kü thuËt t×m ®−êng ®i ng¾n nhÊt dùa trªn lý
thuyÕt to¸n ®å thÞ. Ph−¬ng ph¸p nµy cã nhiÒu −u ®iÓm h¬n khi ¸p dông trong c¸c b¶n ®å sè bëi
v× c¸c b¶n ®å sè d¹ng vÐc t¬ ®Òu x©y dùng trªn c¬ së lý thuyÕt ®å thÞ.
Cho ®å thÞ G = {V,E} cã träng sè kh«ng ©m lµ c¸c cij
V lµ tËp ®Ønh
E lµ tËp c¹nh
C{u,v} lµ ma trËn träng sè
u,v ∈ V
(xem h×nh vÏ 1)
- 3 4
2
1 2 3 4 5 6
1 1
1 ∞ ∞ ∞ ∞⎤
1 ⎡0
⎥6
⎢
2
2 ⎢∞ 5 0 2 2 ∞ ∞⎥
1
3
2
∞ 0 5 ∞1 ∞ ⎥
3 ⎢2
⎥
⎢
4 ⎢∞4 ∞ ∞ 0 2 1⎥
3 5
∞ 4 ∞ 0 ∞⎥
5 ⎢∞
⎥
⎢
6 ⎢∞ 4 ∞ ∞ 1 0⎥ ⎦
⎣
H×nh 1.
TÊt c¶ c¸c thuËt to¸n t×m ®−êng ®i ng¾n nhÊt trªn ®å thÞ ®Òu dùa trªn mét tÝnh chÊt “Mäi
®−êng con cña ®−êng ®i ng¾n nhÊt còng lµ ®−êng ®i ng¾n nhÊt”. Gi¶ sö t×m ®−êng ®i ng¾n nhÊt
tõ ®Ønh s tíi ®Ønh t, s, t ∈ V ng−êi ta lu«n t×m ®−îc ®Ønh v tr−íc t sao cho kho¶ng c¸ch tõ s ®Õn t
sÏ b»ng (d(s,t) = d(s,v) + c(v,t) . §Ønh v sÏ lµ tr−íc t ng¾n nhÊt: Mäi ®o¹n sÏ tõng b−íc kiÕn thiÕt
mét c©y ®−êng ®i “ng¾n nhÊt”, cã gèc t¹i nót nguån hay cßn gäi nót khëi ®Çu cho tíi khi nót cuèi
cïng trong ®å thÞ ®· ®−îc ®−a vµo. ë b−íc thø k c¸c con ®−êng “ng¾n” nhÊt tíi k nót gÇn nguån
nhÊt sÏ ®−îc tÝnh. C¸c nót ®ã ®−îc ®Þnh nghÜa thuéc mét tËp N. Cã thÓ kÓ ra c¸c thuËt to¸n tiªu
biÓu nh− Dijkstra, ford - Bellman, hoÆc thuËt to¸n Floyd v.v... D−íi ®©y tr×nh bµy thuËt to¸n
Dijkstra ®Ó minh häa cho c¸ch gi¶i bµi to¸n nµy.
- ThuËt to¸n Dijkstra
Nk lµ tËp hîp t¹o thµnh bëi k +1 phÇn tö: Nguån vµ k nót gÇn nguån nhÊt sau k b−íc thùc
hiÖn gi¶i thuËt. Dk(n) lµ ®é dµi tõ nguån ®Õn nót n theo con ®−êng ng¾n nhÊt bao hµm trong Nk.
Gi¶ sö nót 1 lµ nót nguån. §Ó t×m c¸c con ®−êng ng¾n nhÊt tõ nót 1 tíi c¸c nót cßn l¹i cña ®å thÞ
ta b¾t ®Çu duyÖt ®å thÞ t¹i ®Ønh 1 cho ®é dµi ®Ønh 1 tíi 1 lµ 0, xÐt tíi hai ®Ønh kÒ liªn th«ng víi 1.
§é dµi ®−êng ®i ®−îc céng liªn tiÕp sau mét b−íc tÝnh nÕu tæng ®é dµi ng¾n nhÊt ®−îc ®−a vµo
tËp N:
B−íc 0 (khëi ®éng)
N0 = {1}
D0 = C(1,v) v ∉ N0
B−íc k (tÝnh vμ cËp nhËt)
Nk = Nk-1 ∪ {u}
trong ®ã u lu«n tho¶ m·n biÒu thøc: Dk-1(u) = minDk-1(v), v ≠ Nk-1
Dk(v) = min[Dk-1(v), Dk-1(u) + C(u,v)]
v ≠ Nk
ThuËt to¸n dõng l¹i khi tÊt c¶ c¸c nót ®· n»m trong N. KÕt qu¶ gi¶i thuËt cho phÐp t×m
®−êng ®i ng¾n nhÊt tõ mét ®Ønh cho tr−íc tíi tÊt c¶ ®Ønh cßn l¹i.
Ch¼ng h¹n víi ®å thÞ h×nh 1 chän ®iÓm xuÊt ph¸t lµ ®Ønh 1. ThuËt to¸n Dijkstra sÏ chØ ra
®−êng ®i ng¾n nhÊt xuÊt ph¸t tõ ®Ønh 1 tíi ®Ønh cßn l¹i
- KÕt qu¶ thÓ hiÖn h×nh 2a ®−êng ®i ng¾n nhÊt ®−îc t« ®Ëm.
5
3 5
4
2
1 1 3 3
2 3 3
2
2 2
6 1 10
2 5 2
1 1
2 1
3
2 2
1 1
6 3
1 6
1
2
1
4 5 2
a b c
4 1
3 5 4 5
H×nh 2.
Trong tr−êng hîp ®å thÞ lµ v« h−íng c¸ch tÝnh còng t−¬ng tù. Trong tr−êng hîp nµy träng
sè ®−îc tÝnh cho c¶ hai chiÒu ch¼ng h¹n ta cho ®å thÞ h×nh 2b sau, träng sè tÝnh ®−îc c¶ hai
chiÒu nót khëi ®Çu t¹i 1. KÕt qu¶ thÓ hiÖn h×nh 2c ®−êng ®i ng¾n nhÊt ®−îc t« ®Ëm.
NhËn xÐt:
- Ng−êi ta ®· chøng minh r»ng thuËt to¸n Dijkstra t×m ®−îc ®−êng ®i ng¾n nhÊt trªn ®å thÞ
sau kho¶ng thêi gian cì O(n2). §iÒu nµy c¶nh b¸o nÕu sè ®Ønh cña ®å thÞ mµ lín th× kh¶ n¨ng
tÝnh to¸n sÏ rÊt h¹n chÕ.
- NÕu ta ¸p dông lÇn l−ît n ®Ønh ta sÏ t×m ®−îc ®−êng ®i ng¾n nhÊt ë bÊt kú cÆp ®Ønh nµo.
Trong tr−êng hîp nµy ng−êi ta cßn dïng thuËt to¸n Ford – Bellman hoÆc thuËt to¸n Floyd. Chi
tiÕt c¸c thuËt to¸n nµy cã thÓ xem thªm trong lý thuyÕt to¸n ®å thÞ. §é phøc t¹p cña c¸c thuËt
to¸n nµy cì O(n3), O(n4).
2. X©y dùng kü thuËt t×m kiÕm ®−êng ®i ng¾n nhÊt trªn b¶n ®å
Trong bµi to¸n nµy cÇn gi¶i quyÕt hai vÊn ®Ò:
- X©y dùng m« h×nh ®å thÞ ®Ó ¸p dông
- ChØ ra ®−êng ®i thùc tÕ trªn b¶n ®å
- Kh¾c phôc ®é phøc t¹p cña bµi to¸n.
2.1. X©y dùng m« h×nh ®å thÞ
Trong lý thuyÕt b¶n ®å sè mäi ®èi t−îng ®å häa trong b¶n ®å ®Òu quy vÒ ba ®èi t−îng c¬
b¶n lµ: ®iÓm, ®−êng, vïng (point, polyline, polygon) chóng ®−îc l−u tr÷ vµ biÓu thÞ theo lý thuyÕt
®å thÞ. Mèi quan hÖ gi÷a ba ®èi t−îng nµy ®· ®−îc ph©n tÝch ®Þnh nghÜa trong lý thuyÕt b¶n ®å
sè. ë ®©y nªu l¹i kh¸i niÖm segment cã liªn quan tíi bµi to¸n.
- Mét ®o¹n ®−êng ®éc lËp (kh«ng rÏ nh¸nh) ®−îc gäi segment (t¹m dÞch ph©n ®o¹n) t−¬ng
®−¬ng víi ®−êng ®i ®é dµi cña ®å thÞ víi ®iÒu kiÖn c¸c ®Ønh cã bËc kh«ng v−ît qu¸ 2 (bËc cña
®Ønh lµ sè c¹nh nèi c¸c ®Ønh kÒ). Trong mét segment lu«n tån t¹i mét ®iÓm ®Çu vµ ®iÓm cuèi
j
H×nh 3 d−íi ®©y lµ cÊu tróc vÐc t¬ m
b d
cña mét ®o¹n ®−êng giao th«ng cïng
e
lo¹i cïng líp (a,b,c,d,e), (e,j,h,m) ®−îc h
g
gäi lµ mét segment. c
a
§å thÞ G ={V,E} ®−¬c lËp nh− sau: n
f
i
H×nh 3.
- TËp ®Ønh V∈G t¹o bëi nh÷ng ®iÓm giao nhau cña hÖ thèng giao th«ng. Tøc lµ nã sÏ lµ c¸c
ng· ba, ng· t− ...trªn b¶n ®å.
TËp c¹nh E ∈ G t¹o bëi cÆp ®Ønh cã ®−êng giao th«ng ®i qua
Ma trËn träng sè {cij} ®−îc x¸c lËp theo c«ng thøc:
n
∑
2 2
( x k − x k +1 ) + (y k − y k +1 )
Cij=Sij=
k =1
Sij lµ chiÒu dµi ®¹i sè cña mét segment
xk, yk lµ c¸c gi¸ trÞ täa ®é ph¼ng cña vÐc t¬ thø k thuéc segment S.
C¸c ®Ønh kh«ng kÒ nhau cã träng sè Cij = ∞.
H×nh vÏ sau m« t¶ mét ®o¹n giao th«ng ®« thÞ dïng t¹o lËp ra ®å thÞ G, chiÒu ®i ®−êng giao
th«ng chÝnh lµ h−íng cña ®å thÞ (h×nh 4). Gi¶ thiÕt c¸c träng sè cho nh− h×nh 4.
3
4
2
4
2
1
1
1
1 6
6 2 5 2
2
1
4
3
5 5
3
H×nh 4.
Hai ®iÓm bÊt kú ®−îc chän trªn b¶n ®å ch¼ng h¹n lµ S, T khi ®ã x¶y ra hai tr−êng hîp:
- S,T ∈ V th× bµi to¸n t×m ®−êng ®i ng¾n nhÊt trªn b¶n ®å gièng nh− bµi to¸n c¬ b¶n ®· nªu trªn.
- S,T∉V.
Trong tr−êng hîp nµy xÐt bµi to¸n bæ sung lµ cho mét ®iÓm S(x,y) t×m t¹i l©n cËn S mét
®Ønh u ∈ V; V ∈ G sao cho kho¶ng c¸ch S → u lµ ng¾n nhÊt. Sau khi cã u xÐt tÊt c¶ c¹nh qua u
víi ®iÒu kiÖn kho¶ng c¸ch tõ S ®Õn c¸c c¹nh qua u nhá nhÊt t×m ra S’ (h×nh 5b). T−¬ng tù nh−
vËy víi ®iÓm T t×m ra ®Ønh v vµ T’. Nh− vËy bµi to¸n sÏ ®−îc ®−a vÒ bµi to¸n c¬ b¶n ë trªn.
Kho¶ng c¸ch ng¾n nhÊt gi÷a hai ®iÓm S,T sÏ lµ d(sT) = d(ss’) + d(s’u) + d(uv) + d(vv’) + d(v’T)
(h×nh 5).
3 4
2
u
v
1 1
u
6
2 5 2
1
s
s
T' s'
s' T
1
2
4
3 5
a b
H×nh 5.
2.2. Kh¾c phôc ®é phøc t¹p tÝnh to¸n
- §Ó gi¶m ®é phøc t¹p tÝnh to¸n tøc lµ lµm gi¶m thêi gian t×m ra kÕt qu¶ cña bµi to¸n. Trong
tr−êng hîp cô thÓ ¸p dông trªn b¶n ®å nhËn thÊy m¹ng l−íi giao th«ng lµ cè ®Þnh hay ®å thÞ G
®· cho lµ cè ®Þnh v× vËy cã thÓ tÝnh tr−íc mäi kh¶ n¨ng cã thÓ hay t×m ®−êng ®i cho cÆp ®Ønh bÊt
kú sau ®ã lËp b¶ng tra. Khi t×nh huèng yªu cÇu th× kh«ng ph¶i tÝnh n÷a mµ chØ cÇn tra kÕt qu¶.
ChiÕn l−îc thø 2 lµm gi¶m ®é phøc t¹p bµi to¸n tøc lµ lµm cho ®å thÞ G cã sè ®Ønh phï hîp.
Trong tr−êng hîp nµy ng−êi ta chia ®å thÞ G cã sè ®Ønh lín ra nhiÒu ®å thÞ con cã sè ®Ønh nhá h¬n.
Víi bµi to¸n cô thÓ ë h×nh 4, ¸p dông thuËt gi¶i trªn triÓn khai d¹ng b¶ng cã kÕt qu¶ sau:
B−íc lÆp §Ønh 1 §Ønh 2 §Ønh 3 §Ønh 4 §Ønh 5 §Ønh 6
∞,1 ∞,1 ∞,1 ∞,1
§Ønh1 Khëi t¹o 0,1 1,1*
∞,1 ∞,1
1 - - 3,2* 4,2*
∞,1 ∞,1
2 - - - 7,3
3 - - - - 6.4 5,4*
4 - - - - -
6,6*
5
B−íc lÆp §Ønh 2 §Ønh 3 §Ønh 4 §Ønh 5 §Ønh 6 §Ønh 1
∞,2 ∞,2 ∞,2
§Ønh2 Khëi t¹o 0,2 3,2* 4,2*
∞,2 ∞,2
1 - - 7,3 4,3*
∞,2 ∞,2 ∞,2
2 - - -
3 - - - 6,4 -
5.4*
4 - - - - -
6,5*
5
TiÕp tôc cho ®Õn hÕt ta cã kÕt qu¶ sau d¹ng c©y khung sau:
s
4
2 4
2
4
2
s 6 6
1 1 6
1
3 5 3 5
3 5
s
s
4
2
4
2 4
2
6
1
s
6
1 6
1
3 5
3 5 3 5
s
H×nh 6.
Cuèi cïng ta lËp ®−îc b¶ng tra s½n cho cÆp ®Ønh bÊt kú l−u l¹i d−íi d¹ng file sè liÖu:
§Ønh 1 §Ønh 2 §Ønh 3 §Ønh 4 §Ønh 5 §Ønh 6
§Ønh1 0 1,2 1,2,3 1,2,4 1,2,4,6,5 1,2,4,6
§Ønh2 2,3,1 0 2,3 2,4 2,4,5 2,4,6
§Ønh3 3,1 3,1,2 0 3,1,2,4 3,1,2,4,5 3,1,2,4,6
§Ønh4 4,5,3,1 4,5,3,1,2 4,5,3 0 4,5 4,6
§Ønh5 5,3,1 5,3,1,2 5,3 5,3,4 0 5,3,4,6
- §Ønh6 6,5,3,1 6,5,3,1,2 6,5,3 6,5,3,4 6,5 0
- Khi sè ®iÓm qu¸ lín tiÕn hµnh chia ®å thÞ lín
thµnh c¸c ®å thÞ con sao cho sè ®Ønh chung nhau
lµ nhá nhÊt. Trong mét sè tr−êng hîp chØ ra mét
G1 G2 G3
®Ønh nµo ®Êy lµm ®Ønh chung.
NÕu hai ®iÓm ®−a vµo xÐt thuéc mét ®å thÞ
con Gi bµi to¸n vÒ d¹ng c¬ b¶n ®· xÐt ë trªn.
NÕu hai ®iÓm ®−a vµo xÐt thuéc hai ®å thÞ
H×nh 7.
kh¸c nhau khi ®ã coi c¸c ®å thÞ con vµ c¸c ®Ønh
chung ®· ph©n tÝch ë trªn nh− ®Ønh cña ®å thÞ míi (h×nh 8)
G4
®å thÞ nµy còng ®−îc thiÕt kÕ tõ tr−íc, träng sè ®−îc tÝnh
l¹i theo c¸c tr−êng hîp cô thÓ. Bµi to¸n chia thµnh hai bµi v1 v6
to¸n con.
- T×m ®−êng ®i ng¾n nhÊt gi÷a c¸c ®å thÞ con theo m« G2
v2
G1
h×nh tæng thÓ (h×nh 8) kÕt qu¶ chØ ra c¸c ®Ønh chung vµ tËp
v4
®Ønh lµ c¸c ®å thÞ con.
v5
v3
- T×m ®−êng ®i ng¾n nhÊt lÇn l−ît cña tÊt c¶ cÆp trong G3
c¸c ®å thÞ thµnh phÇn vµ c¸c ®Ønh chung kÒ nhau cña ®å
H×nh 8.
thÞ thÞ lín.
- C¶ hai bµi to¸n nµy ®Òu cã thÓ tÝnh tr−íc vµ lËp b¶ng tra nh− ®· tr×nh bµy ë trªn nh− vËy
bµi to¸n lÆp l¹i c¸ch gi¶i nh− ®· tr×nh bµy
2.3. ChØ ra ®−êng ®i
Kü thuËt nµy rÊt ®¬n gi¶n, tËp c¹nh ®å thÞ G ®· biÕt thiÕt lËp mèi liªn kÕt víi c¸c segment
thiÕt lËp nªn c¹nh ®ã. Khi ®· x¸c ®Þnh c¸c ®Ønh chøa ®−êng ®i ng¾n nhÊt tøc lµ x¸c ®Þnh ®−îc
c¸c segment gäi l¹i thñ tôc vÏ c¸c vÐc t¬ cña segment ®ã tøc lµ ®· vÏ ®å häa l¹i chÝnh con
®−êng ®ã trong hÖ giao th«ng cña b¶n ®å (bµi to¸n ®ang xÐt trong b¶n ®å sè vµ øng dông sù trî
gióp tÝnh to¸n cña m¸y tÝnh).
III. KÕt luËn
ThuËt to¸n ®· tr×nh bµy ë trªn kh«ng ph¶i lµ duy nhÊt mµ cßn rÊt nhiÒu thuËt to¸n kh¸c
nhau trong chiÕn l−îc t×m ®−êng ®i ng¾n nhÊt. V× vËy viÖc giíi thiÖu mang tÝnh chÊt tham kh¶o,
tïy tõng tr−êng hîp cô thÓ mµ ¸p dông. Cã thÓ kÓ ra mét sè øng dông kü thuËt t×m ®−êng ®i
ng¾n nhÊt nh−:
- DÞch vô chØ dÉn ®−êng ®i qua m¹ng ®iÖn tho¹i cè ®Þnh hoÆc di ®éng. T¹i tæng ®µi cµi ®Æt
s½n m¸y tÝnh cã øng dông trªn khi ®ã sÏ s½n sµng tr¶ lêi khi cã yªu cÇu.
- Trî gióp cho c¸c ph−¬ng ¸n t¸c chiÕn qu©n sù, an ninh, phßng ch¸y ch÷a ch¸y
- C¸c øng dông trªn cã thÓ ph¸t triÓn thªm c¸c ®iÒu kiÖn lµ ph−¬ng tiÖn ®i lµ kh¸c nhau
nh− « t«, xe m¸y, hay mét ph−¬ng tiÖn nµo ®ã v.v... khi ®ã chØ thay c¸c m« h×nh ®å thÞ. Vµ thùc
tÕ sinh ra nhiÒu øng dông kh¸c n÷a .
Tµi liÖu tham kh¶o
- [1]. NguyÔn §øc NghÜa, NguyÔn T« Thμnh. To¸n rêi r¹c. Nhµ xuÊt b¶n §¹i häc quèc gia. Hµ néi, 2003.
[2]. TS. Vò BÝch V©n. B¶n ®å häc ®iÖn to¸n. Gi¸o tr×nh cao häc ngµnh b¶n ®å. Hµ néi, 2000♦
nguon tai.lieu . vn
