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

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG -
- HỒ TRUNG CANG BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VÀ ỨNG DỤNG CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ: 60. 46. 40 TÓM T
T LUN VĂN THC SĨ KHOA HC Đà Nẵng - Năm 2011 2 Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS-TSKH Trn Quc Chi n Phản biện 1: TS. CAO VĂN NUÔI Phản biện 2: TS. HOÀ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 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 toá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 toá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 toán trong thực tế. Vì vậy, tôi ñã chọn ñề tài: “Bài toá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 toán tìm ñường ñi ngắn nhất. Các ứng dụng của bài toá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 toán ñường ñi ngắn nhất và một số ứng dụng của nó. 4 3.2. Phạm vi nghiên cứu: Các thuật toán tìm ñường ñi ngắn nhất và một số ứng dụng của bài toá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 toá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: Ngoà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 TOÁN ĐƯỜNG ĐI NGẮN NHẤT Chương 3 : ỨNG DỤNG 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, e1, v1, e2,v2,….,vn-1,en,w) trong ñó vi(i=1,…,n-1) là các ñỉnh trên dãy và ei(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 Đườ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 (e1, e2,….,en) thỏa mãn ñỉnh cuối cùng của cung ei là ñỉnh ñầu của cung ei+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 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 { }( ) ax ( , w)e v m d v v V= ∈ 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à : { }( ) min ( )r G e v v V= ∈ Đỉnh v V∈ ñược gọi là ñỉnh tâm nếu ( ) ( )e v r G= . 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 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 Chương 2 : BÀI TOÁ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 toá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 0 1 2 1... n nv v v v vµ −= → → → → → có tổng các trọng số 1 1 ( ) w ( , ) n i i i L v vµ − = = ∑ Cho hai ñỉnh a, z của ñồ thị. Bài toán ñặt ra là tìm ñường ñi ngắn nhất từ a ñến z. 2.1.2. Thuật toán Dijkstra : Thật toá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 (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 toán Dijkstra là ñúng. Chứng minh Kí hiệu lần lượt các ñỉnh v chọn bước 2 là v0 = a, v1, v2, ... vm . Ta chứng minh bằng qui nạp rằng L(vi) chính là ñộ dài ñường ñi ngắn nhất từ a ñến vi, i∀ , i = 1, 2, 3, ... , m - Bước cơ sở : Hiển nhiên L(v1) là ñộ dài ngắn nhất từ a ñến v1. - Bước qui nạp : Giả thiết L(vi) là ñộ dài ñường ñi ngắn nhất từ a ñến vi i k∀ ≤ . Ta chứng minh rằng L(vk) là ñộ dài ñường ñi ngắn nhất từ a ñến vk. Gọi P là ñường ñi ngắn nhất từ a ñến vk có ñộ dài l(P). Các ñỉnh trên P trừ vk phải thuộc S = {v1, v2, ... , vk-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 ( ) ( ) w( , ) ( )kL u L v v u L v≤ + ≤ , nên u phải bị loại ra khỏi T ở bước (2) trước vk, hay u phải thuộc S, và ñây là ñiều mâu thuẫn. Bây giờ gọi vh là ñỉnh trước vk trên P. Theo cách tính lại nhãn ta có : ( ) ( ) w( , ) ( )k h h kL v L v v v l P≤ + ≤ Suy ra L(vk) là ñộ dài ñường ñi ngắn nhất từ a ñến vk. 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 toá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 ...0 1 2 1v v v v vnnµ = → → → → →− có tổng các trọng số 1 1 ( ) w ( , ) n i i i L v vµ − = = ∑ Bài toá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 toá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 D0 = [ ]( , )d i j và P0= [ ]0 ( , )p i j là các ma trận xuất phát trong ñó d0(i,j) =w(i,j) nếu tồn tại cung (i,j) và d0(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ì d0(i,i) = +∞ ) và p0(i,j) = j nếu có cung từ i ñến j và p0(i,j) không xác ñịnh nếu không có cung từ i ñến j. 12 Gán k:=0. (2) Kiểm tra kết thúc: Nếu k=n, kết thúc. D= Dn là ma trận ñộ dài ñường ñi ngắn nhất, P = Pn. Ngược lại tăng k lên 1 ñơn vị (k:=k+1) và sang (3). (3) Tính ma trận Dk và Pk theo Dk-1 và Pk-1: Với mọi cặp (i,j), i= 1..n, j=1..n thực hiện: Nếu dk-1(i,j) > dk-1(i,k) + dk-1(k,j) thì ñặt dk(i,j):= dk-1(i,k) + dk-1(k,j) và pk(i,j):=pk-1(i,k) ngược lại ñặt dk(i,j):= dk-1(i,j) và pk(i,j):= pk-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 , i1, i2, i3,…, ik, ik+1,…, im, j thỏa mãn i1= p(i,j), i2 =p(i1, j), … , ik+1 = p(ik,j), … , p(im,j) =j 2.3. Chu trình Hamilton ngắn nhất: 2.3.1. Phát biểu bài toá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 0 1 2 1... n nv v v v vµ −= → → → → → có tổng các trọng số 1 1 ( ) w ( , ) n i i i L v vµ − = = ∑ 13 Bài toá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 toán nhánh cận: Thuật toán nhánh cận là một trong những phương pháp chủ yếu ñể giải bài toá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 toá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 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) Áp dụng thuật toá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 toán cực tiểu tổng ( bài toán chọn vị trí xây dựng trường học) : a b k z c d e f g h 5 2 8 5 8 6 3 1 4 1 4 1 10 6 3 10 4 2 3 5 2 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 toá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: Áp dụng thuật toá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 Do 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 D 42 0 34 25 32 E 34 0 F 25 0 Do = G 32 0 Đắk Nông(F) Sa Long (A) Đắkan(B) Đắk Xú(C) Pleikần(D) Đắk Dục(G) Bờ Y(E) 24 51 42 25 32 34 Đắk Nông(F) 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 117 93 42 0 34 25 32 E 151 127 76 34 0 59 66 F 142 118 67 25 59 0 57 D = D7 = 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 toán cực tiểu trị lớn nhất (bài toá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 toá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 Áp dụng thuật toá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 117 93 42 0 34 25 32 E 151 127 76 34 0 59 66 F 142 118 67 25 59 0 57 D = D7 = 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 Sa Long (A) Đắkan(B) Đắk Xú(C) Pleikần(D) Đắk Nông(F) Đắk Dục(G) Bờ Y(E) 24 51 42 25 32 34 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 toá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 toá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 toá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 Á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 = D6 và sử dụng P = P6 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: Bờ Y(BY) 3 Đắkan(ĐK) ĐắkXú(ĐX) Đắk Dục(ĐD) Sa Long(SL) Đắk Nông(ĐN) 20 1 3 2 8 5 13 4 6 8 9 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 toá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: Để giải quyết bài toán này ta dùng thuật toá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=P7, 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 i1 = P(BX,DT) = KT; i2 = P(KT,DT) = TT, Cầu ĐắkLa(ĐL) 1 Duy Tân(DT) Bến xe(BX) Trung Tín(TT) Ngục Kon Tum (KT) Hòa bình(HB) 4 8 3 1 3 7 1 3 2 5 3 12 3 Cầu Treo(CT) 20 i3= P(TT,DT)=ĐL, i4 = 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. Ta sẽ mô hình hóa bài toá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 1 2 3 4 5 6 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 Tất cả các hành trình Hành trình không chứa (6,3) P2 Hành trình chứa (6,3) Hành trình không chứa (6,3) P2 Hành trình chứa (4,6) Hành trình không chứa (4,6) P12 Hành trình chứa (2,1) Hành trình không chứa (2,1) Hành trình không chứa (4,6) P112 Hành trình chứa (1,4) 81 129 113 101 112 84 81 81 104 P1111 P111 P11 P1 Chọn tiếp 2 cạnh còn lại ta có hành trình: p = (1, 4, 6, 3, 5, 2, 1) và chi phí cp = 104 β = β = P Cận dưới Cận dưới 23 Qua sơ ñồ trên ta thấy các nhánh P2, P12, P1112 có cận dưới lớn hơn cp = 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 P112 có cận dưới là 101 nhỏ hơn cp. 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 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 toá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 toá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 toán tìm ñường ñi ngắn nhất ñể giải quyết nhiều hơn các bài toá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 toán tìm ñường ñi ngắn nhất, ñể từ ñó giải quyết ñược các bài toán thực tế cần tìm các hành trình tiết kiệm.