Tóm tắt luận án Bài toán tìm đường đi ngắn nhất và ứng dụng

Nội dung text: Tóm tắt luận án Bài toán tìm đường đi ngắn nhất và ứng dụng

1. 1 BỘ GIÁO D ỤC VÀ ĐÀO T ẠO ĐẠI HỌC ĐÀ N ẴNG -
   - HỒ TRUNG CANG BÀI TỐN TÌM ĐƯỜNG ĐI NG ẮN NH ẤT VÀ ỨNG D ỤNG CHUYÊN NGÀNH: PH ƯƠ NG PHÁP TỐN S Ơ C ẤP MÃ S Ố: 60. 46. 40 TĨM T
   T LU N V ĂN TH C S Ĩ KHOA H C Đà N ẵng - N ăm 2011
2. 2 Cơng trình được hồn thành t ại ĐẠI HỌC ĐÀ N ẴNG Ng ười h ướng d ẫn khoa h ọc: PGS-TSKH Tr n Qu c Chi n Ph ản bi ện 1: TS. CAO V ĂN NUƠI Ph ản bi ện 2: TS. HỒNG QUANG TUY ẾN Lu ận v ăn được b ảo v ệ tr ước H ội đồng ch ấm Lu ận v ăn t ốt nghi ệp th ạc s ĩ khoa h ọc h ọp t ại Đại h ọc Đà N ẵng vào ngày 17 tháng 08 n ăm 2011 Cĩ th ể tìm hi ểu lu ận v ăn t ại: - Trung tâm Thơng tin - H ọc li ệu, Đại h ọc Đà N ẵng - Th ư vi ện tr ường Đại h ọc S ư ph ạm, Đại h ọc Đà N ẵng.
3. 3 MỞ ĐẦU 1. Lý do ch ọn đề tài: Lý thuy ết đồ th ị là ngành khoa h ọc được phát tri ển t ừ lâu nh ưng l ại cĩ nhi ều ứng d ụng hi ện đại, nĩ là ki ến th ức c ơ s ở cho nhi ều ngành khoa h ọc k ỹ thu ật khác nhau nh ư Điện t ử, Hĩa h ọc, Ngơn ng ữ h ọc, Kinh t ế h ọc, Máy tính, Nhi ều khái ni ệm c ủa lý thuy ết đồ th ị được sinh ra t ừ các v ấn đề th ực ti ễn nh ư: đường đi, chu trình, t ập ổn định, chu s ố, s ắc s ố, duy ệt đồ th ị, đường đi Hamilton, tâm đồ th ị, lu ồng v ận t ải, đồ th ị ph ẳng, cây bao trùm, cây bi ểu th ức, cây mã ti ền t ố t ối ưu, vì v ậy lý thuy ết đồ th ị đã g ắn k ết nhi ều ngành khoa h ọc l ại v ới nhau. Các thu ật tốn ng ắn g ọn và lí thú c ủa lý thuy ết đồ th ị đã giúp chúng ta gi ải quy ết r ất nhi ều bài tốn ph ức t ạp trong th ực t ế, trong đĩ v ấn đề tìm đường đi ng ắn nh ất giúp chúng ta gi ải quy ết được r ất nhi ều bài tốn trong th ực t ế. Vì v ậy, tơi đã ch ọn đề tài: “ Bài tốn tìm đường đi ng ắn nh ất và ứng d ụng” để nghiên c ứu. 2. M ục đích và nhi ệm v ụ nghiên c ứu: Trình bày h ệ th ống lý thuy ết đồ th ị. Trình bày h ệ th ống lý thuy ết v ề đường đi ng ắn nh ất và các thu ật tốn tìm đường đi ng ắn nh ất. Các ứng d ụng c ủa bài tốn tìm đường đi ng ắn nh ất. 3. Đối t ượng và ph ạm vi nghiên c ứu: 3.1. Đối t ượng nghiên c ứu: Đối t ượng nghiên c ứu c ủa đề tài là bài tốn đường đi ng ắn nh ất và m ột s ố ứng d ụng c ủa nĩ.
4. 4 3.2. Ph ạm vi nghiên c ứu: Các thu ật tốn tìm đường đi ng ắn nh ất và m ột s ố ứng d ụng của bài tốn tìm đường đi ng ắn nh ất. 4. Ph ươ ng pháp nghiên c ứu: Cơ b ản s ử d ụng ph ươ ng pháp nghiên c ứu tài li ệu (sách, báo, các m ục trên internet cĩ liên quan đến đề tài) để thu th ập thơng tin nh ằm phân tích, h ệ th ống lý thuy ết, các thu ật tốn v ề đường ng ắn nh ất, các ứng d ụng ph ục v ụ cho đề tài. 5. C ấu trúc lu ận v ăn: Ngồi ph ần m ở đầu, k ết lu ận, tài li ệu tham kh ảo, trong lu ận văn gịm cĩ ba ch ươ ng nh ư sau : Ch ươ ng 1 : ĐẠI C ƯƠ NG V Ề ĐỒ TH Ị Ch ươ ng 2 : BÀI TỐN ĐƯỜNG ĐI NG ẮN NH ẤT Ch ươ ng 3 : ỨNG D ỤNG
5. 5 Ch ươ ng 1 : ĐẠI C ƯƠ NG V Ề ĐỒ TH Ị 1.1. Đồ th ị, đỉnh, c ạnh: 1.2. B ậc, n ửa b ậc vào, n ửa b ậc ra: 1.2.1. B ậc : 1.2.2. N ửa b ậc: 1.2.3. Ví d ụ : 1.2.4. B ổ đề b ắt tay ( Hand Shaking Lemma) : 1.2.5. M ệnh đề 1 : 1.2.6. M ệnh đề 2 : 1.3. Đường đi, chu trình, tính liên thơng 1.3.1. Định ngh ĩa : Cho đồ th ị G= (V,E) Dãy µ t ừ đỉnh v đến đỉnh w là dãy các đỉnh và các c ạnh n ối ti ếp nhau b ắt đầu t ừ đỉnh v và k ết thúc t ại đỉnh w. S ố c ạnh trên dãy µ gọi là độ dài của dãy µ . Dãy µ t ừ đỉnh v đến đỉnh w độ dài n được bi ểu di ễn nh ư sau µ =(v, e 1, v 1, e 2,v 2, .,v n-1,en,w) trong đĩ v i(i=1, ,n-1) là các đỉnh trên dãy và e i(i=1, ,n) là các c ạnh trên dãy liên thu ộc đỉnh k ề tr ước và sau nĩ. Các đỉnh và các c ạnh trên dãy cĩ th ể l ặp l ại. Đường đi từ đỉnh v đến đỉnh w là dãy t ừ đỉnh v đến đỉnh w, trong đĩ các c ạnh khơng lặp l ại
6. 6 Đường đi s ơ c ấp là đường đi khơng đi qua m ột đỉnh quá 1 l ần. Chu trình là đường đi cĩ đỉnh đầu và đỉnh cu ối trùng nhau Chu trình s ơ c ấp là chu trình khơng đi qua m ột đỉnh quá 1 l ần. Dãy cĩ h ướng trong đồ th ị cĩ h ướng là dãy các đỉnh và cung n ối ti ếp nhau (e 1, e 2, .,e n) th ỏa mãn đỉnh cu ối cùng c ủa cung e i là đỉnh đầu c ủa cung e i+1 , i=1, ,n-1. Đường đi cĩ h ướng trong đĩ đồ th ị cĩ h ướng là dãy cĩ h ướng, trong đĩ các cung khơng l ặp l ại. Đường đi cĩ h ướng s ơ c ấp là đường đi cĩ h ướng khơng đi qua một đỉnh quá 1 l ần. Chu trình cĩ h ướng là đường đi cĩ h ướng đỉnh đầu và đỉnh cu ối trùng nhau. Chu trình cĩ h ướng s ơ c ấp là chu trình cĩ h ướng khơng đi qua một đỉnh quá 1 l ần. Đồ th ị vơ h ướng g ọi là liên thơng, nếu m ọi cặp đỉnh c ủa nĩ đều cĩ đường đi n ối chúng v ới nhau. Đồ th ị cĩ h ướng g ọi là liên thơng m ạnh, n ếu m ọi c ặp đỉnh c ủa nĩ đều cĩ đường đi cĩ h ướng n ối chúng v ới nhau. 1.3.2. Định lý 1: 1.3.3. Định lý 2 : 1.3.4. Tr ọng đồ:
7. 7 Tr ọng đồ (cĩ h ướng) là đồ th ị (cĩ h ướng) mà m ỗi c ạnh (cung) c ủa nĩ được gán m ột s ố. Tr ọng đồ được bi ểu di ễn b ởi G=(V,E,w), trong đĩ V là t ập các đỉnh, E là t ập các c ạnh (cung) và w : E→ R là hàm s ố trên E, w(e) là tr ọng s ố c ủa c ạnh (cung) e v ới m ọi e∈ R . Trong tr ọng đồ độ dài tr ọng s ố c ủa đường đi µ là t ổng các tr ọng s ố trên đường đi đĩ. 1.3.5. Đồ th ị con : 1.3.6. Ví d ụ : 1.3.7. Định lý 3 : 1.4. Độ l ệch tâm, bán kính, tâm đồ th ị: Cho đồ th ị G =(V,E,w). Ta định nghĩa kho ảng cách t ừ u đến v, ∀u, v ∈ V , là độ dài đường đi ng ắn nh ất t ừ u đến v và ký hi ệu là d(u,v). Đại l ượng ev()= m ax{ dv (,w) vV ∈ } g ọi là độ l ệch tâm c ủa đỉnh v, ∀v ∈ V . Bán kính c ủa đồ th ị G, kí hi ệu r(G), là độ l ệch tâm nh ỏ nh ất, t ức là : rG( )= min{ evvV () ∈ } Đỉnh v∈ V được g ọi là đỉnh tâm n ếu ev()= rG () . T ập h ợp t ất cả các đỉnh tâm được g ọi là tâm c ủa đồ th ị và ký hi ệu là C(G).
8. 8 1.5. Bi ểu di ễn đồ th ị : 1.5.1. Ma tr ận k ề : 1.5.2. Ma tr ận liên thu ộc:
9. 9 Ch ươ ng 2 : BÀI TỐN ĐƯỜNG ĐI NG ẮN NH ẤT 2.1. Đường đi ng ắn nh ất gi ữa 2 đỉnh: 2.1.1. Phát bi ểu bài tốn : Cho đồ th ị cĩ tr ọng s ố G = (V,E). Kí hi ệu w (i,j) là tr ọng s ố c ủa cạnh (i,j). Độ dài đường đi µ = →→ →→ → vvv012 vn− 1 v n cĩ t ổng các tr ọng s ố n µ = L()∑ w( vi−1 ,) v i i =1 Cho hai đỉnh a, z c ủa đồ th ị. Bài tốn đặt ra là tìm đường đi ng ắn nh ất t ừ a đến z. 2.1.2. Thu ật tốn Dijkstra : Th ật tốn tìm đường đi ng ắn nh ất t ừ đỉnh a đến đỉnh z trong đĩ đồ th ị liên thơng cĩ tr ọng s ố. tr ọng s ố c ạnh (i,j) là w(i,j)>0 và đỉnh x sẽ mang nhãn L(x). Khi k ết thúc thu ật gi ải L(z) chính là chi ều dài ng ắn nh ất t ừ a đến z. + Đầu vào: đồ th ị liên thơng G=(V,E) cĩ tr ọng s ố w(i,j)>0 v ới mọi c ạnh (i,j), đỉnh a và z + Đầu ra : L(z) chi ều dài đường đi ng ắn nh ất t ừ a đến z và đường đi ng ắn nh ất. + Ph ươ ng pháp: (1) Gán L(a):=0, v ới m ọi x khác a gán L(a)= ∞ . Kí hi ệu T:=V (2) Ch ọn v∈ T sao cho L(v) cĩ giá tr ị nh ỏ nh ất. Đặt T:=T-{v}
10. 10 (3) Nếu z∉ T , k ết thúc, L(z) là chi ều dài đường đi ng ắn nh ất t ừ a đến z. T ừ z l ần ng ược theo đỉnh được ghi nh ớ ta cĩ đường đi ng ắn nh ất. Ng ược l ại sang b ước (4) (4) Với m ỗi x∈ T k ề v gán L(x):=min{L(x),L(v)+w(v,x)} Nếu L(x) thay đổi thi ghi nh ớ đỉnh v c ạnh x để sau này xây d ựng đường đi ng ắn nh ất. Quay v ề b ước (2) -Định lí : Thu ật tốn Dijkstra là đúng. Ch ứng minh Kí hi ệu l ần l ượt các đỉnh v ch ọn b ước 2 là v 0 = a, v 1, v 2, vm . Ta ch ứng minh b ằng qui n ạp r ằng L(v i) chính là độ dài đường đi ng ắn nh ất t ừ a đến v i, ∀i , i = 1, 2, 3, , m - Bước c ơ s ở : Hi ển nhiên L(v 1) là độ dài ng ắn nh ất t ừ a đến v 1. - Bước qui n ạp : Gi ả thi ết L(v i) là độ dài đường đi ng ắn nh ất t ừ a đến v i ∀i ≤ k . Ta ch ứng minh r ằng L(v k) là độ dài đường đi ng ắn nh ất t ừ a đến v k. Gọi P là đường đi ng ắn nh ất t ừ a đến v k cĩ độ dài l(P). Các đỉnh trên P tr ừ v k ph ải thu ộc S = {v 1, v 2, , v k-1}. Gi ả s ử ng ược l ại, g ọi u là đỉnh đầu tiên trên P khơng thu ộc S và v là đỉnh thu ộc S tr ước u . Hi ển nhiên ≤ + ≤ Lu() Lv ()w(,) vu Lv ()k , nên u ph ải b ị lo ại ra kh ỏi T ở b ước (2) tr ước v k, hay u ph ải thu ộc S, và đây là điều mâu thu ẫn. Bây gi ờ g ọi v h là đỉnh tr ước v k trên P. Theo cách tính l ại ≤ + ≤ nhãn ta cĩ : Lv()k Lv ()w(,) h vv hk lP () Suy ra L(v k) là độ dài đường đi ng ắn nh ất t ừ a đến v k.
11. 11 2.1.3. Ph ươ ng pháp l ập b ảng ghi nhãn 2.2. Đường đi ng ắn nh ất gi ữa m ọi c ặp đỉnh : 2.2.1. Phát bi ểu bài tốn : Cho đồ th ị cĩ h ướng liên thơng cĩ tr ọng s ố G=(V,E). Kí hi ệu w(i,j) là tr ọng s ố c ủa c ạnh (i,j). Độ dài đường đi µ = →→ →→ → vvv v− v n cĩ t ổng các tr ọng s ố 012n n 1 µ = L()∑ w( vi− 1 ,) v i i = 1 Bài tốn đặt ra là tìm đường đi ng ắn nh ất gi ữa m ọi c ặp đỉnh trong đồ th ị. 2.2.2. Thu ật tốn Floyd –Warshall : Thu ật gi ải tìm đường đi ng ắn nh ất gi ữa m ọi c ặp đỉnh trong đồ th ị cĩ h ướng liên thơng cĩ tr ọng s ố. + Đầu vào : Đồ th ị liên thơng G=(V,E), V= {1,2, , n}, cĩ tr ọng s ố v ới m ọi cung (i,j). + Đầu ra : Ma tr ận D = [d( i , j ) ] , trong đĩ d(i,j) là chi ều dài đường đi ng ắn nh ất t ừ i đến j v ới m ọi c ặp (i,j). Ma tr ận P= [ p( i , j ) ] dùng để xác định đường đi ng ắn nh ất. + Ph ươ ng pháp: [ ] [ ] (1) Bước kh ởi t ạo: Kí hi ệu D 0 = d( i , j ) và P 0= p0 ( i , j ) là các ma tr ận xu ất phát trong đĩ d 0(i,j) =w(i,j) n ếu t ồn t ại cung (i,j) và d 0(i,j) = + ∞ n ếu khơng t ồn t ại cung (i,j) ( đặc bi ệt n ếu khơng cĩ khuyên t ại i thì d 0(i,i) = + ∞ ) và p 0(i,j) = j n ếu cĩ cung t ừ i đến j và p 0(i,j) khơng xác định n ếu khơng cĩ cung t ừ i đến j.
12. 12 Gán k:=0. (2) Ki ểm tra k ết thúc: Nếu k=n, k ết thúc. D= D n là ma tr ận độ dài đường đi ng ắn nh ất, P = P n. Ng ược l ại t ăng k lên 1 đơ n v ị (k:=k+1) và sang (3). (3) Tính ma tr ận D k và P k theo D k-1 và P k-1: Với m ọi c ặp (i,j), i= 1 n, j=1 n th ực hi ện: Nếu d k-1(i,j) > d k-1(i,k) + d k-1(k,j) thì đặt dk(i,j):= d k-1(i,k) + dk-1(k,j) và p k(i,j):=p k-1(i,k) ng ược l ại đặt d k(i,j):= d k-1(i,j) và p k(i,j):= p k-1(i,j) Quay l ại b ước (2). Ph ươ ng pháp xác định đường đi ng ắn nh ất t ừ đỉnh i đến đỉnh j : Đường đi ng ắn nh ất t ừ i đến j g ồm dãy các đỉnh i , i 1, i 2, i 3, , i k, i k+1 , , i m, j th ỏa mãn i 1= p(i,j), i 2 =p(i 1, j), , i k+1 = p(i k,j), , p(i m,j) =j 2.3. Chu trình Hamilton ng ắn nh ất: 2.3.1. Phát bi ểu bài tốn : Cho đồ th ị cĩ tr ọng s ố G=(V,E). Kí hi ệu w(i,j) là tr ọng s ố c ủa cạnh (i,j). Độ dài đường đi µ = →→ →→ → vvv012 vn− 1 v n cĩ t ổng các tr ọng s ố n µ = L()∑ w( vi−1 ,) v i i =1
13. 13 Bài tốn đặt ra là tìm đường đi ng ắn nh ất đi qua m ọi đỉnh c ủa đồ th ị và tr ở v ề đỉnh ban đầu (chu trình Hamilton ng ắn nh ất). 2.3.2. Thu ật tốn nhánh c ận: Thu ật tốn nhánh c ận là m ột trong nh ững ph ươ ng pháp ch ủ yếu để gi ải bài tốn t ối ưu t ổ h ợp. T ư t ưởng c ơ b ản c ủa nĩ là trong quá trình tìm ki ếm ta phân ho ạch các ph ươ ng án c ủa bài tốn ra thành 2 hay nhi ều t ập con nh ư là các nút cây tìm ki ếm và c ố g ắng đánh giá c ận cho các nút, lo ại b ỏ nh ững nhánh mà ta bi ết ch ắc ch ắn là khơng ch ứa ph ươ ng án t ối ưu.
14. 14 Ch ươ ng 3 : ỨNG D ỤNG 3.1. Ch ọn hành trình ti ết ki ệm nh ất. Mạng l ưới giao thơng n ối các điểm du l ịch trong m ột khu du lịch sinh thái cĩ th ể mơ hình hĩa b ằng m ột đồ th ị cĩ tr ọng s ố, trên đĩ độ dài m ỗi cung cĩ th ể là kho ảng cách ho ặc th ời gian c ần thi ết để đi từ điểm du l ịch này đến điểm du l ịch kia. Trên hình sau là 10 điểm du l ịch được ký hi ệu là :a, b, c, d, e , f, g, h, k, z các cung n ối các cặp đỉnh để ch ỉ ra r ằng gi ữa các c ặp điểm đĩ cĩ đường n ối tr ực ti ếp chúng v ới nhau, các s ố trên các cung là độ dài c ủa cung đĩ. Hãy xác định l ộ trình đi du l ịch ti ết ki ệm nh ất t ừ điểm a đến điểm z ( khơng nh ất thi ết ph ải đi qua t ất c ả các điểm du lich) b 4 k 10 1 1 2 5 c 10 4 h 2 z a 4 1 6 5 8 d 3 g 5 3 2 6 3 8 e f Áp d ụng thu ật tốn Dijkstra để tìm đường đi ng ắn nh ất t ừ a đến z. Ta suy ra đường đi ng ắn nh ất là : a→ b → k → h → z và độ dài đường đi ng ắn nh ất t ừ a đến z là L(z) = 9. 3.2. Bài tốn c ực ti ểu t ổng ( bài tốn ch ọn v ị trí xây d ựng tr ường học) :
15. 15 Ng ười ta mu ốn xây d ựng 1 tr ường h ọc t ại m ột trong 7 xã c ủa huy ện Ng ọc H ồi để cho h ọc sinh 7 xã đến h ọc, ch ọn xã nào để đặt tr ường h ọc cho phù h ợp ( t ổng chi phí t ất c ả h ọc sinh đi đến tr ường học là nh ỏ nh ất). Để gi ải bài tốn này ta xem m ỗi xã là 1 đỉnh c ủa đồ th ị, m ỗi c ạnh bi ểu th ị đường đi t ừ xã này đến xã kia, trên m ỗi c ạnh ta điền t ổng chi phí đi l ại c ủa h ọc sinh xã đĩ đến xã k ề. Gi ả s ử v ị trí các xã được mơ hình hĩa thành đồ th ị sau: Đắk Nơng(F) Đắ 25 k Nơng(F) 24 51 42 34 Bờ Y(E) Sa Long (A) Đắkan(B) Đắk Xú(C) Pleik ần(D) 32 Đắk D ục(G) Áp d ụng thu ật tốn Floyd để tìm đường đi ng ắn nh ất gi ữa t ất c ả các cặp đỉnh c ủa đồ th ị trên. C ụ th ể Ma tr ận kho ảng cách xu ất phát D o là ( các ơ tr ống là ∞ ): Đỉnh A B C D E F G A 0 24 B 24 0 51 C 51 0 42 Do = D 42 0 34 25 32 E 34 0 F 25 0 G 32 0
16. 16 Đỉnh A B C D E F G A 0 24 75 117 151 142 149 B 24 0 51 93 127 118 125 C 75 51 0 42 76 67 74 D = D 7 = D 117 93 42 0 34 25 32 E 151 127 76 34 0 59 66 F 142 118 67 25 59 0 57 G 149 125 74 32 66 57 0 Cu ối cùng D là ma tr ận kho ảng cách ng ắn nh ất gi ữa các đỉnh. Tổng các hàng t ươ ng ứng là : 658, 538, 385, 343, 513, 468, 503. Nh ư v ậy đỉnh D là đỉnh c ự ti ểu t ổng duy nh ất và t ập đỉnh c ực ti ểu tổng là {D}. Do đĩ chúng ta nên xây d ựng tr ường h ọc ở xã Pleik ần. 3.3. Bài tốn c ực ti ểu tr ị l ớn nh ất (bài tốn tìm tâm đồ th ị): Ng ười ta mu ốn xây d ựng 1 b ệnh vi ện t ại m ột trong 7 xã c ủa huy ện Ng ọc H ồi để ph ục v ụ cho ng ười dân c ủa 7 xã, ch ọn xã nào để đặt b ệnh vi ện là h ợp lý nh ất? (ng ười dân ở xã xa nh ất đến b ệnh vi ện được g ần nh ất). Để gi ải bài tốn này ta xem m ỗi xã là 1 đỉnh c ủa đồ th ị, m ỗi c ạnh bi ểu th ị đường đi gi ữa 2 xã, trên m ỗi c ạnh ta điền kho ảng cách t ừ xã đĩ đến xã k ề. Gi ả sử v ị trí các xã được mơ hình hĩa thành đồ th ị sau:
17. 17 Đắk Nơng(F) 25 24 51 42 34 Bờ Y(E) Sa Long (A) Đắkan(B) Đắk Xú(C) Pleik ần(D) 32 Đắk D ục(G) Áp d ụng thu ật tốn Floyd để tìm đường đi ng ắn nh ất gi ữa t ất cả các c ặp đỉnh c ủa đồ th ị trên. C ụ th ể ta cĩ ma tr ận kho ảng cách ng ắn nh ất gi ữa các đỉnh là D: Đỉnh A B C D E F G A 0 24 75 117 151 142 149 B 24 0 51 93 127 118 125 C 75 51 0 42 76 67 74 D = D 7 = D 117 93 42 0 34 25 32 E 151 127 76 34 0 59 66 F 142 118 67 25 59 0 57 G 149 125 74 32 66 57 0 Độ l ệch tâm c ủa các đỉnh t ươ ng ứng là : A - 151, B -127, C - 76, D – 117, E - 151, F - 142, G - 149
18. 18 Nh ư v ậy đỉnh C là đỉnh c ực ti ểu độ l ệch tâm duy nh ất và tâm đồ th ị là {C} Do đĩ ta nên xây b ệnh vi ện ở xã Đắk Xú. 3.4. Bài tốn tìm đường đi ng ắn nh ất gi ữa các c ặp điểm: Làm th ế nào để giúp Trung tâm Taxi qu ản lý được các xe Taxi hi ệu qu ả và giúp cho các tài x ế lái Taxi ch ọn con đường t ừ v ị trí xe đậu đến đĩn khách và tr ả khách ng ắn nh ất ? Đây là v ấn đề đặt ra của các hãng Taxi. Để gi ải quy ết v ấn đề này ta hãy bi ểu di ễn b ản đồ thành ph ố thành m ột đồ th ị và dùng thu ật tốn Floyd-Warshall để tìm hành trình ng ắn nh ất và độ dài c ủa chúng. 3.4.1. Bài tốn 1 : Dùng gi ải thu ật Floyd-Warshall tìm đường đi ng ắn nh ất gi ữa các địa điểm trong th ị tr ấn Pleik ần – Ng ọc H ồi bi ết đường đi gi ữa các địa điểm là đường đi m ột chi ều được cho b ởi s ơ đồ sau Đắ Đ Đắ Đ kXú( X) kan( K) 8 9 3 2 5 6 8 Đắk D ục( ĐD) 20 13 Sa Long(SL) Bờ Y(BY) 1 3 4 Đắk Nơng( ĐN) Áp d ụng gi ải thu ật Floyd-Warshall ta được ma tr ận kho ảng cách ng ắn nh ất gi ữa các đỉnh D = D 6 và s ử d ụng P = P 6 ta cĩ th ể tìm đường đi ng ắn nh ất gi ữa các địa điểm. Ch ẳng h ạn : tìm đường đi t ừ Sa Long c ần đến Đắk Xú, ta tìm đường đi nh ư sau:
19. 19 P(SL, ĐX) = ĐK , P( ĐK, ĐX) = ĐD , P( ĐD, ĐX) = ĐX. Vậy ta nên đi nh ư sau : Sa Long Đắkan Đắk D ục với chi ều dài là D(SL, ĐX) = 16 Đắk Xú, 3.4.2. Bài tốn 2 : Dùng gi ải thu ật Floyd-Warshall tìm đường đi ng ắn nh ất gi ữa các địa điểm trong Thành ph ố Kon Tum bi ết đường đi gi ữa các địa điểm là đường đi m ột chi ều được cho b ởi s ơ đồ sau: 3 Duy Bến xe(BX) Trung Tín(TT) Tân(DT) 4 8 3 1 3 7 1 3 C ầu ĐắkLa( ĐL) 1 2 Cầu Treo(CT) 5 3 Hịa bình(HB) Ng ục Kon Tum (KT) 12 Để gi ải quy ết bài tốn này ta dùng thu ật tốn Floyd-Warshall. Ta cĩ ma tr ận kho ảng cách ng ắn nh ất gi ữa các địa điểm D = D7. S ử d ụng ma tr ận P=P 7, ta cĩ th ể tìm đường đi ng ắn nh ất gi ữa các địa điểm. Ch ẳng h ạn, để tìm đường đi t ừ B ến xe đến Duy Tân ta làm nh ư sau: Đặt i 1 = P(BX,DT) = KT; i 2 = P(KT,DT) = TT,
20. 20 i 3= P(TT,DT)= ĐL, i 4 = P( ĐL,DT)=DT Từ đĩ ta nh ận được đường đi ng ắn nh ất t ừ B ến xe đến Duy Tân v ới độ dài b ằng 8 và đi nh ư sau: Bến xe Ng ục Kon Tum Trung Tín C ầu Đắk La Qua 2 ma tr ận D và P thì trung tâm Taxi cĩ th ể qu ản lý được các xe c ủa trung tâm, ra các m ức giá và chi phí để các xe đi t ừ địa điểm này đến địa điểm kia m ột cách phù h ợp và c ũng giúp các ng ười lái xe tìm đường đi hi ệu qu ả nh ất. 3.5. Ch ọn chu trình Hamilton ti ết ki ệm nh ất: Trong quá trình gia cơng ch ế t ạo máy, ng ười ta c ần khoan các l ỗ trên m ột t ấm thép để sau đĩ b ắt vít các chi ti ết máy. Các l ỗ khoan cĩ th ể được th ực hi ện d ưới s ự điều khi ển c ủa máy tính. Nh ằm ti ết ki ệm chi phí quá trình khoan c ần được th ực hi ện càng nhanh càng t ốt. 1 6 2 3 4 5 Ta s ẽ mơ hình hĩa bài tốn đặt ra b ằng đồ th ị cĩ tr ọng s ố nh ư sau : Các đỉnh c ủa đồ th ị t ươ ng ứng v ới các l ỗ khoan. M ỗi c ặp
21. 21 đỉnh được n ối v ới nhau b ởi 1 cung là c ạnh c ủa đồ th ị. Trên m ỗi c ạnh ta vi ết các s ố t ươ ng ứng th ời gian d ịch chuy ển t ừ l ỗ khoan này đến l ỗ khoan kia. Ta thu được đồ th ị cĩ tr ọng s ố và được bi ểu di ễn qua ma tr ận chi phí sau ( ph ải đi qua t ất c ả các đỉnh). 1 2 3 4 5 6 1 ∞ 3 93 13 33 9 2 4 ∞ 77 42 21 16 3 45 17 ∞ 36 16 28 4 39 90 80 ∞ 56 7 5 28 46 88 33 ∞ 25 6 3 88 18 46 92 ∞ Ti ến hành tìm c ận d ưới và rút g ọn ma tr ận: Quá trình đĩ cĩ th ể bi ểu di ễn b ằng s ơ đồ sau:
22. 22 Cận d ưới Cận d ưới β β P = = Tất c ả các hành P2 Hành trình 81 129 trình khơng ch ứa (6,3) P1 Hành trình ch ứa P2 Hành trình 81 (6,3) khơng ch ứa (6,3) 113 P 11 Hành trình ch ứa P12 Hành trình 81 (4,6) khơng ch ứa (4,6) 101 P111 Hành trình ch ứa P112 Hành trình 84 (2,1) khơng ch ứa (2,1) 112 Hành trình khơng ch ứa (4,6) P1111 Hành trình ch ứa Ch ọn ti ếp 2 c ạnh cịn l ại ta cĩ 104 (1,4) hành trình: p = (1, 4, 6, 3, 5, 2, 1) và chi phí c p = 104
23. 23 Qua s ơ đồ trên ta th ấy các nhánh P 2, P 12 , P 1112 cĩ c ận d ưới l ớn h ơn c p = 104 vì th ế các hành trình c ủa các nhánh đĩ cĩ t ổng chi phí l ớn h ơn cp. ch ỉ cĩ nhánh P 112 cĩ c ận d ưới là 101 nh ỏ h ơn c p. Ti ếp theo ta tìm hành trình m ới theo nhánh này và làm t ươ ng tự ta được hành trình : (5,1),(1,4),(4,6),(6,3),(3,2),(2,5) v ới t ổng chi phí là 104. Vậy cĩ 2 hành trình tìm được qua t ất c ả các đỉnh c ủa đồ th ị v ới chi phí th ấp nh ất là : 104 là : (1,4);(4,6);(6,3);(3,5);(5,2);(2,1) và (1,4);(4,6);(6,3);(3,2);(2,5);(5,1)
24. 24 KẾT LU ẬN - Qua quá trình nghiên c ứu đề tài tơi đã nh ận được m ột s ố k ết qu ả sau: 1. Với b ản thân đã h ệ th ống được m ột s ố ki ến th ức v ề Lý thuy ết đồ th ị và hi ểu sâu h ơn v ề các bài tốn tìm đường đi ng ắn nhất. 2. Đư a ra được các ph ươ ng án v ận d ụng. 3. Gi ải được m ột s ố bài tốn th ực t ế v ề tìm đường đi ng ắn nh ất. 4. H ướng phát tri ển c ủa đề tài: Ti ếp t ục nghiên c ứu v ận d ụng lý lu ận và k ết qu ả c ủa lý thuy ết đồ th ị, các thu ật tốn tìm đường đi ng ắn nh ất để gi ải quy ết nhi ều h ơn các bài tốn th ực t ế. - Lu ận v ăn này được vi ết v ới mong mu ốn tìm hi ểu sâu h ơn nh ững ứng d ụng c ủa các thu ật tốn tìm đường đi ng ắn nh ất, để t ừ đĩ gi ải quy ết được các bài tốn th ực t ế c ần tìm các hành trình ti ết ki ệm.