Tóm tắt luận văn thạc sĩ khoa học: Bài toán tìm đường ngắn nhất và ứng dụng

Chia sẻ: Lang Nguyen | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

340
lượt xem 55
download

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

Tóm tắt luận văn thạc sĩ khoa học: Bài toán tìm đường ngắn nhất và ứng dụng nhằm trình bày về 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 ngắn nhất.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn thạc sĩ khoa học: Bài toán tìm đường 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 LU N VĂN TH C SĨ KHOA H C Đà 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 Tr n Qu c 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 e(v) = max d (v, w) 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à : r (G ) = min {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 µ = v0 → v1 → v2 → ... → vn−1 → vn có t ng các tr ng s n L (µ ) = ∑ w (v i − 1 , v i ) i =1 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 L(u ) ≤ L(v) + w(v, u ) ≤ L(vk ) , 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ó : L(vk ) ≤ L(vh ) + w(vh , vk ) ≤ 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 µ = v0 →v1 →v2 →... →vn−1 →vn có t ng các tr ng s n L (µ ) = ∑ w (v i − 1 , v i ) i =1 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= [ p0 (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 µ = v0 → v1 → v2 → ... → vn−1 → vn có t ng các tr ng s n L (µ ) = ∑ w (v i − 1 , v i ) i =1
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) b 4 k 10 1 1 2 5 c 10 4 h 2 4 1 z a 5 8 6 d 3 g 5 3 2 6 3 8 e f Á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) :
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: Đ k Nông(F) Đ 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 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 Do = D 42 0 34 25 32 E 34 0 F 25 0 G 32 0
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 = D7 = 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 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 Đ 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 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 = D7 = 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 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 Đ 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 = 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:
19 P(SL,ĐX) = ĐK , P(ĐK,ĐX) = ĐD , P(ĐD,ĐX) = ĐX. V y ta nên ñi như sau : Sa Long Đ kan Đ kD 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: 3 Duy B n xe(BX) Tân(DT) 4 8 Trung Tín(TT) 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 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,
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. 1 6 2 3 4 5 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