[Giáo trình Toán rời rạc] - Chương5 - Một số bài toán Tối ưu trên Đồ thị

Tài liệu " [Giáo trình Toán rời rạc] - Chương5 - Một số bài toán Tối ưu trên Đồ thị " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.
Nội dung trích xuất từ tài liệu:
[Giáo trình Toán rời rạc] - Chương5 - Một số bài toán Tối ưu trên Đồ thị http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG V M TS BÀI TOÁN T I ƯU TRÊN ð TH5.1. ð TH CÓ TR NG S VÀ BÀI TOÁN ðƯ NG ðI NG N NH T.5.1.1. M ñ u: Trong ñ i s ng, chúng ta thư ng g p nh ng tình hu ng như sau: ñ ñi t ñ añi m A ñ n ñ a ñi m B trong thành ph , có nhi u ñư ng ñi, nhi u cách ñi; có lúc tach n ñư ng ñi ng n nh t (theo nghĩa c ly), có lúc l i c n ch n ñư ng ñi nhanh nh t(theo nghĩa th i gian) và có lúc ph i cân nh c ñ ch n ñư ng ñi r ti n nh t (theo nghĩachi phí), v.v... Có th coi sơ ñ c a ñư ng ñi t A ñ n B trong thành ph là m t ñ th , v i ñ nhlà các giao l (A và B coi như giao l ), c nh là ño n ñư ng n i hai giao l . Trên m ic nh c a ñ th này, ta gán m t s dương, ng v i chi u dài c a ño n ñư ng, th i gianñi ño n ñư ng ho c cư c phí v n chuy n trên ño n ñư ng ñó, ... ð th có tr ng s là ñ th G=(V,E) mà m i c nh (ho c cung) e∈E ñư c gán b im t s th c m(e), g i là tr ng s c a c nh (ho c cung) e. Trong ph n này, tr ng s c a m i c nh ñư c xét là m t s dương và còn g i làchi u dài c a c nh ñó. M i ñư ng ñi t ñ nh u ñ n ñ nh v, có chi u dài là m(u,v), b ngt ng chi u dài các c nh mà nó ñi qua. Kho ng cách d(u,v) gi a hai ñ nh u và v là chi udài ñư ng ñi ng n nh t (theo nghĩa m(u,v) nh nh t) trong các ñư ng ñi t u ñ n v. Có th xem m t ñ th G b t kỳ là m t ñ th có tr ng s mà m i c nh ñ u cóchi u dài 1. Khi ñó, kho ng cách d(u,v) gi a hai ñ nh u và v là chi u dài c a ñư ng ñi tu ñ n v ng n nh t, t c là ñư ng ñi qua ít c nh nh t.5.1.2. Bài toán tìm ñư ng ñi ng n nh t: Cho ñơn ñ th liên thông, có tr ng s G=(V,E). Tìm kho ng cách d(u0,v) t m tñ nh u0 cho trư c ñ n m t ñ nh v b t kỳ c a G và tìm ñư ng ñi ng n nh t t u0 ñ n v. Có m t s thu t toán tìm ñư ng ñi ng n nh t; ñây, ta có thu t toán do E.Dijkstra, nhà toán h c ngư i Hà Lan, ñ xu t năm 1959. Trong phiên b n mà ta s trìnhbày, ngư i ta gi s ñ th là vô hư ng, các tr ng s là dương. Ch c n thay ñ i ñôi chútlà có th gi i ñư c bài toán tìm ñư ng ñi ng n nh t trong ñ th có hư ng. Phương pháp c a thu t toán Dijkstra là: xác ñ nh tu n t ñ nh có kho ng cáchñ n u0 t nh ñ n l n. Trư c tiên, ñ nh có kho ng cách ñ n a nh nh t chính là a, v i d(u0,u0)=0. Trongcác ñ nh v ≠ u0, tìm ñ nh có kho ng cách k1 ñ n u0 là nh nh t. ð nh này ph i là m ttrong các ñ nh k v i u0. Gi s ñó là u1. Ta có: d(u0,u1) = k1. 67http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t pTrong các ñ nh v ≠ u0 và v ≠ u1, tìm ñ nh có kho ng cách k2 ñ n u0 là nh nh t. ð nhnày ph i là m t trong các ñ nh k v i u0 ho c v i u1. Gi s ñó là u2. Ta có: d(u0,u2) = k2.Ti p t c như trên, cho ñ n bao gi tìm ñư c kho ng cách t u0 ñ n m i ñ nh v c a G.N u V={u0, u1, ..., un} thì: 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un).5.1.3. Thu t toán Dijkstra:procedure Dijkstra (G=(V,E) là ñơn ñ th liên thông, có tr ng s v i tr ng s dương) {G có các ñ nh a=u0, u1, ..., un=z và tr ng s m(ui,uj), v i m(ui,uj) = ∞ n u (ui,uj) không là m t c nh trong G} for i := 1 to n L(ui) := ∞ L(a) := 0 S := V {a} u := a while S ≠ ∅ begin for t t c các ñ nh v thu c S if L(u) +m(u,v) < L(v) then L(v) := L(u)+m(u,v) u := ñ nh thu c S có nhãn L(u) nh nh t {L(u): ñ dài ñư ng ñi ng n nh t t a ñ n u} S := S {u} endThí d 1: Tìm kho ng cách d(a,v) t a ñ n m i ñ nh v và tìm ñư ng ñi ng n nh t t añ n v cho trong ñ th G sau. b 4 c 6 d 1 1 2 2 2 2 3 4 3 a e g h 3 2 3 5 5 1 n m k 6 3 68http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p L(a) L(b) L(c) L(d) L(e) L(g) L(h) L(k) L(m) L(n) 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ − 1 ∞ ∞ 3 ∞ ∞ ∞ 3 2 − − 5 ...