Báo cáo khoa học: "Kỹ thuật tìm đ-ờng đi ngắn nhất trên bản đồ"

Chia sẻ: Nguyễn Phương Hà Linh Nguyễn Phương Hà Linh | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

38
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

đặ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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: "Kỹ thuật tìm đ-ờng đi ngắn nhất trên bản đồ"

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♦