intTypePromotion=2 
Array
(
    [0] => Array
        (
            [banner_id] => 141
            [banner_name] => KM2 - Tặng đến 100%
            [banner_picture] => 986_1568345559.jpg
            [banner_picture2] => 823_1568345559.jpg
            [banner_picture3] => 278_1568345559.jpg
            [banner_picture4] => 449_1568779935.jpg
            [banner_picture5] => 
            [banner_type] => 7
            [banner_link] => https://tailieu.vn/nang-cap-tai-khoan-vip.html
            [banner_status] => 1
            [banner_priority] => 0
            [banner_lastmodify] => 2019-09-18 11:12:45
            [banner_startdate] => 2019-09-13 00:00:00
            [banner_enddate] => 2019-09-13 23:59:59
            [banner_isauto_active] => 0
            [banner_timeautoactive] => 
            [user_username] => minhduy
        )

)
 » 
 » 

Giáo trình tin học trong quản lý xây dựng - Chương 5

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

0
Thêm vào BST
Báo xấu
54
lượt xem 12
download

Giáo trình tin học trong quản lý xây dựng - Chương 5

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

Tài liệu tham khảo Giáo trình điện tử môn học tin học trong quản lý xây dựng ( GV. ThS. Nguyễn Thanh Phong - Khoa kỹ thuật và công nghệ ) - Chương 5 Quy hoạch mạng

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình tin học trong quản lý xây dựng - Chương 5

  1. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) CHƯƠNG 5 QUY HO CH M NG (NET-NETWORKS PROGRAMMING) * M C TIÊU H C T P Sau khi hoàn t t h c t p chương 5, sinh viên s có kh năng: 1. Mô t các thu t ng chính trong m ng. 2. Nh n bi t 3 d ng bài toán cơ b n trong quy ho ch m ng. 3. S d ng các công c tin h c đ gi i bài toán quy ho ch m ng. 1. GI I THI U M ng xu t hi n trong nhi u b i c nh và dư i nhi u d ng khác nhau: + Các m ng lư i đư ng giao thông v n t i, m ng lư i dây đi n và m ng thông tin liên l c… + S n xu t, phân ph i, l p k ho ch d án, qu n lý ngu n tài nguyên, b trí thi t b ... Bài toán quy ho ch m ng: là m t d ng đ c b i t c a các b ài toán quy ho ch tuy n tính. Ví d : Bài toán giao thông v n t i, bài toán phân công công vi c. Trong chương này, ba bài toán quan tr ng c a quy ho ch m ng s đ ư c trình bày: + Bài toán tìm đư ng đi ng n nh t (Shorest-Route Problem); + Bài toán đư ng dây m c loa (Minimal-Spanning Tree); + Bài toán c c đ i lưu lư ng (Maximal Flow Problem). Trong xây d ng, 3 mô hình c a quy ho ch m ng có th d ùng đ gi i quy t m t s bài toán trong quy ho ch và b trí bình đ công trư ng. T t c các ví d mô t các lo i bài toán quy ho ch m ng trong chương này tương đ i nh và đơn gi n hơn so v i các bài toán th c t GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 403
  2. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) nh m giúp b n đ c d hi u và áp d ng các thu t toán. Đ i v i nh ng quy ho ch m ng nh và đơn gi n, chúng ta có th tìm ra ngày l i gi i t i ưu b ng cách xem xét tr c quan và suy đoán. Đ i v i nh ng bài toán quy ho ch m ng l n và ph c t p có hàng trăm, hàng ngàn nút, chúng ta s g p khó khăn trong vi c tìm l i gi i b ng tr c giác. Vì v y, chúng ta ph i áp d ng các thu t toán đư c trình bày trong chương này đ gi i quy t v n đ dù gi i b ng tay hay trên máy tính. 2. CÁC THU T N G C A M NG M ng (Network): bao g m các đi m và các đư ng n i các đi m này l i v i nhau. + Các đi m này đư c g i là các Nút (Node). • Nút cung Nút c p: có đ c đi m là lư ng chuy n t i ra kh i nút đó l n hơn lư ng đi vào nút đó. • Nút c u: lư ng nh n vào l n hơn lư ng chuy n t i ra kh i nút. • Nút trung tính: lư ng đi vào và đi ra kh i nút b ng nhau. + Các đư ng n i các nút đư c g i là các cung/nhánh (Arc). • Cung có hư ng: Cho phép đi t 1 nút A đ n nút B và không cho phép đi theo hư ng ngư c l i (ký hi u AB). • Cung vô hư ng: cho phép di chuy n theo c hai hư ng. a) Cung có hư ng AB b) Cung vô hư ng AB Hình 5.1. Cung có hư ng và cung vô hư ng + M ng có hư ng: ch bao g m các cung có hư ng. + M ng vô hư ng: bao g m các cung vô hư ng. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 404
  3. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Tuy n: n i gi a hai nút và có th bao g m nhi u cung khác nhau. + Tuy n có hư ng t nút i đ n nút j là m t chu i các cung có hư ng t i sang j, do đó cho phép đi t i sang j. + Tuy n vô hư ng t nút i sang nút j là m t chu i các cung vô hư ng t i đi đ n j. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 405
  4. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) V í d : Tuy n OT, đư ng đi t O sang T có th đ i qua các cung OB - BD - DT (O → B → D → T) Hình 5.2. Ví d + Lưu ý r ng tuy n có hư ng th a mãn đi u ki n c a tuy n vô hư ng, nhưng đi u ngư c l i không đúng Liên thông: hai nút đư c g i là liên thông n u t n t i ít nh t m t tuy n vô hư ng gi a chúng. M ng liên thông: là m ng mà t t c các c p nút đ u liên thông. M ng nhánh cây: bao g m t t c các nút nhưng không đư c n i thành vòng. V í d : Xét 1 m ng lư i như trong Hình 8.3 như sau, trong đó: + xij = lư ng chuy n t i t nút i đ n nút j; + cij = chi phí chuy n t i đơn v t nút i đ n nút j GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 406
  5. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 8.3. Sơ đ m ng 3. BÀI TOÁN TÌM ĐƯ N G ĐI NG N N H T 3.1. Đ nh nghĩa Bài toán tìm đư ng đi ng n nh t (Shortest-Route/ Shortest- Path Problem) là bài toán tìm l trình di chuy n (c a ngư i, xe máy hay hàng hóa) t m t đ a đi m này đ n m t đ a đ i m khác trên h th ng nhi u đư ng giao thông có s n sao cho t ng chi u dài đư ng đi là ng n nh t. Nói cách khác, nó tìm đư ng đi ng n nh t xu t phát t 1 đi m ngu n ban đ u đ n m t chu i các đi m đích khác nhau. Ví d : + Tìm đư ng đi ng n nh t t nhà máy cung c p bê tông tươi đ n các công trư ng xây d ng. + Tìm đ ư ng đi ng n nh t đ v n chuy n công nhân, máy móc thi t b t công ty xây d ng đ n các công trư ng xây d ng. + Tìm đ ư ng đi ng n nh t t m t thành ph này đ n m t thành ph khác trên h th ng đư ng giao thông. + Tìm đư ng đi ng n nh t t nhà máy s n x u t đ n nhà kho ch a hàng. + Tìm đư ng đi ng n nh t (th i gian ít nh t) t nhà máy s n xu t đ n nơi tiêu th s n ph m. Th v c a 1 nút: là kho ng cách bé nh t t nút đ u (Nút 1) đ n nút đó: { } u j = min ui + dij i Trong đó: + uj = Kho ng cách ng n nh t t nút 1 đ n nút j v i u1 = 0; + ui = Kho ng cách ng n nh t t nút 1 đ n nút i + dij = Kho ng cách gi a nút j và nút i trư c nó GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 407
  6. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) 3.2. Các gi i thu t cho bài toán tìm đ ư ng đi ng n nh t G i i thu t t ng quát: + G i i thu t ti n; + G i i thu t D ijkstra; + G i i thu t Floyd. Gi i thu t đ quy: Gi i thu t ch dùng cho m ng có hư ng, không m ch vòng. Gi i theo bài toán QHTT nguyên. C hú ý: M t s ng d ng c a b ài toán tìm đư ng đi ng n nh t liên quan đ n tiêu chu n th i gian ho c chi phí thay vì kho ng cách. Do đó, ta có các d ng bài toán như sau: 1- C c ti u quãng đư ng đi. 2- C c ti u t ng chi phí c a m t chu i các thao tác. 3- C c ti u lư ng th i gian c a m t chu i các thao tác. B i vì bài toán tìm đư ng đi ng n nh t là bài toán c c ti u hóa nên chúng ta không th áp d ng các gi i thu t nêu trên n u b ài toán có giá tr các cung là âm. M c dù trong th c t , giá tr trên các cung có th là chi phí âm (t c l i nhu n dương). Chúng ta c n các gi i thu t nâng cao hơn đ gi i các bài toán d ng này. 3.3. Gi i thu t ti n cho bài toán Tìm đư ng đi ng n nh t - Bư c 1: + Tìm nút n m g n nút g c (nút xu t phát/ nút ngu n) nh t. + G hi giá tr (kho ng cách, th i gian, chi phí) t nút xu t phát đ n nút g n nh t đó (L p l i bư c này v i n=1,2,3…cho đ n khi nút th n n m g n nh t là nút đích.) - Bư c 2: Thành l p t p nút đã kh o sát (permanent set) g m nút g c và nút g n nút g c nh t đã xác đ nh bư c 1. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 408
  7. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) - Bư c 3: Xác đ nh t t c các nút chưa kh o sát n m g n t p nút đ ã kh o sát. T p nút đã kh o sát (permanent set) đư c n i tr c ti p đ n 1 ho c nhi u nút chưa kh o sát nào đó s cung c p m t ng viên cho nút g n nh t th n. - Bư c 4: Tìm nút n m g n t p nút đ ã kh o sát (permanent set) nh t, và ghi kho ng cách ng n nh t đ n nút này t nút g c (giá tr này g i là th v c a nút). Lưu ý : V i m i nút đã kh o sát và các ng viên c a nó, c ng kho ng cách gi a chúng và kho ng cách ng n nh t t nút g c đ n nút đã kh o sát đó. Nút nào có kho ng cách ng n nh t s là nút g n nh t th n và tuy n đư ng ng n nh t s là tuy n đư ng t o ra kho ng cách này. - Bư c 5: L p l i bư c 3 và 4: + Ti p t c l p l i q uá trình xác đ nh th v c a các nút trong m ng (b ng cách c ng th v c a nút g n nh t và kho ng cách gi a 2 nút) theo công th c: { } u j = min u i + d ij ) i + G iá tr th v ghi nút cu i cùng chính là kho ng cách ng n nh t t nút xu t phát đ n nút cu i cùng. 3.4. Gi i b ng QHTT Nguyên X ét m ng g m: + m nút; + n cung có hư ng; + cij: chi phí trên t ng cung (i, j). H ãy tìm chi phí nh nh t đ đi t nút 1 đ n nút m? Chi phí trên đư ng đi là t ng chi phí t ng đo n t o nên đư ng đi đó. Gi i: GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 409
  8. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) 0 neáu khoâng coù ñöôøng noái töø nuùt i ñeán nuùt j G i x ij =  1 neáu coù ñöôøng noái töø nuùt i ñeán nuùt j xij = 1 (n u ij đư c ch n là đư ng đi ng n nh t) Hàm m c tiêu: Min Z = ∑∑ cij * x ij i j Ràng bu c: 1 neáu i = 1  • ∑ x ij − ∑ x ki = 0 neáu i = 2,m − 1 −1 neáu i = m j k  • xij = 0 hay 1 cho m i i và j • cij nguyên Chú ý r ng bài toán đư ng đi ng n nh t là trư ng h p đ c bi t c a b ài toán c c ti u chi phí trên m ng lưu thông. T đó ta s xét toán ma tr n trư ng (ma tr n đ nh hư ng cung - nút) là t ng mô đun đ ng nh t và có th thay ràng bu c xij = 0 hay 1 b ng x ij ≥ 0 . Khi đó bài toán tr thành: ∑∑ cij * x ij Hàm m c tiêu: Min i j Ràng bu c: 1 neáu i = 1  • ∑ x ij − ∑ x ki = 0 neáu i = 2,m − 1 −1 neáu i = m j k  • x ij ≥ 0 3.5. Gi i thu t Đ Quy * Phương pháp đ quy: G i uj = kho ng cách ng n nh t t nút 1 đ n nút j v i u1 = 0. Các giá tr c a uj, j = 1,2..., n đư c tính toán đ q uy dùng công th c sau: { } u j = min u i + d ij i GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 410
  9. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Trong đó: + uj = Kho ng cách ng n nh t t nút 1 đ n nút j v i u1 = 0; + ui = Kho ng cách ng n nh t t nút 1 đ n nút i + dij = Kho ng cách gi a nút j và nút i trư c nó Lưu ý: uj ch đư c tính sau khi ui đã đư c tính. Nhãn c a nút j là [uj, n] v i n là nút j t o ra kho ng cách ng n nh t: { } u j = min ui + d ij = un + dnj. i Lưu ý: Gi i thu t này ch dùng cho các bài toán không có vòng (Acyclic). 3.6. Gi i thu t D ijkstra cho bài toán Tìm đ ư ng đi ng n nh t Gi i thi u 3.6.1. G i i thu t D ijkstra đư c s d ng đ tìm đư ng đi ng n nh t t nút ngu n và các nút khác trong m ng, dùng cho c bài toán có hay không có m ch vòng. Gi i thu t này có th áp d ng cho các bài toán m ng có vòng (Cyclic). Gi i thu t D ijkstra s d ng 1 quy trình g n nhãn đ c bi t, do đó nó còn có tên g i là gi i thu t g n nhãn. G i: + ui là kho ng cách ng n nh t t nút 1 đ n nút i; và + dij ≥ 0 là chi u dài cung (i, j); + i th hi n nút trư c trên con đư ng t nút 1 đ n nút j; ⇒ N hãn c a nút j đư c đ nh nghĩa là: [uj, i] = [ ui + dij, i] v i dij ≥ 0 N hãn dùng trong gi i thu t Dijkstra có 2 lo i: + N hãn t m th i (Temporary/Tentative Label): nhãn này có th b thay th b i m t nhãn khác n u t n t i 1 đư ng đi ng n hơn đ n nút đang kh o sát. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 411
  10. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Ký hi u nhãn t m th i: [uj, i] hay (uj, i) + N hãn c đ nh (Permanent Label): khi không tìm đư c 1 đư ng đi nào ng n hơn n a thì nhãn t m th i đư c chuy n thành nhãn c đ nh. Ký hi u nhãn c đ nh: [uj, i]* hay [uj, i] Gi i Thu t D ijkstra 3.6.2. G i s chúng ta có m t m ng g m n nút. Gi i thu t D ijkstra s tìm đ ư ng đi ng n nh t t nút ngu n 1 đ n các nút khác trong m ng như sau: - Bư c 1 : G n cho nút ngu n 1 nhãn c đ nh [0, -]* ho c [0, S]*. G án i = 1. Trong đó: + S 0 th hi n kho ng cách t nút 1 đ n chính nó. + D u – (hay ch S) th hi n nút 1 là nút ngu n (nút xu t phát – starting node). - Bư c 2: + N u i =1: Tính các nhãn t m th i (d1j, 1) c a các nút j mà t nút 1 có th đi đ n đư c, bi t r ng j là các nút chưa đư c g n nhãn c đ nh và nút 1 là nút ngu n, d1j là giá tr kho ng cách t nút 1 đ n nút j. + Nêu i > 1: Tính các nhãn t m th i (uj + dij, i) c a các nút j mà t nút i có th đi đ n đư c, bi t r ng j là các nút chưa đư c g n nhãn c đ nh và i là nút đã g n nhãn c đ nh. Nút j cho chúng ta giá tr kho ng cách uj + dij nh nh t s là nút đư c g n nhãn c đ nh [uj + dij, i]. + N u nút j đã đ ư c g n 1 nhãn t m th i (uj, k) đ n t 1 nút k nào đó, và n u kho ng cách đ n t nút i là ui + dij < uj (kho ng cách đ n t nút k), chúng ta thay th nhãn t m th i (uj, k) b ng (ui + dij, i). GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 412
  11. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) - Bư c 3: + N u t t c các nút đã đ ư c g n nhãn c đ nh. Ta d ng và đ c k t qu tìm đư ng đi ng n nh t t nút 1 đ n nút k b ng cách theo chi u ngư c dòng. + N gư c l i, ch n 1 nút r nào đó chưa đư c g n nhãn c đ nh [ur, s] có ur b é nh t trong các nút đư c g n nhãn t m th i. Gán i = r, l p l i bư c 2. C hú ý: - Chúng ta ph i tính (n-1) vòng l p đ tìm kho ng cách ng n nh t đ n t t c các nút. - N u chúng ta ch m u n tìm đư ng đi ng n nh t t nút ngu n 1 đ n m t nút k nào đó thì chúng ta có th d ng khi nút k đư c g n nhãn c đ nh . - N u chúng ta mu n tìm đ ư ng đi ng n nh t t m t nút k b t kỳ đ n các nút trong m ng thì chúng ta s b t đ u t nút này b ng cách gán nó nhãn c đ nh [0, -]* ho c [0, S]*. Sau đó, ti n hành các b ư c ti p theo c a gi i thu t Dijkstra. 3.7. Ví d minh h a: Công ty s n xu t n i th t Phương Nam H àng ngày công ty s n xu t n i th t Phương Nam ph i v n chuy n các s n ph m n i th t (bàn, gh , t …) t nhà máy s n xu t đ n nhà kho ch a hàng. Ông Nam, giám đ c công ty, mu n tìm đư ng đi ng n nh t t nhà máy s n xu t (nút 1) đ n nhà kho (nút 6). Cho bi t sơ đ m ng lư i đ ư ng giao thông đư c th hi n như trong hình 8.4 sau đây (v i chi u dài tuy n đư ng tính theo đơn v km). GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 413
  12. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 5.4. Sơ đ các tuy n đ ư ng giao thông t nhà máy đ n nhà kho Gi i bài toán b ng Gi i thu t ti n Cách 1: Gi i b ng hình v Q uan sát hình 8.4, chúng ta th y r ng nút n m g n nút g c (nút 1-nhà máy s n xu t) nh t là nút 2, v i kho ng cách là 100 km. Như v y, chúng ta có th n i nút 1 và nút 2 và ghi vào giá tr 100. Khi đó, nút 2 s là nút vào t p nút đã kh o sát. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 414
  13. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 5.5. Vòng l p th nh t Ti p theo, chúng ta ph i xác đ nh t t c các nút xu t phát t t p nút đã kh o sát (nút 1 và nút 2). Đó chính là nút 3, 4 và 5. Chúng ta s xác đ nh đư ng đi ng n nh t t t p nút đã kh o sát (nút 1 và nút 2) đ n nút 3, 4 và 5. Có 1 đư ng đi xu t phát t nút 1 là tuy n đ ư ng 1-3; và 3 đư ng đi xu t phát t nút 2 là tuy n đư ng 2-3, tuy n đư ng 2-4 và tuy n đư ng 2-5. Đư ng đi có kho ng cách ng n nh t là theo tuy n đư ng 1-2-3 (100+50 = 150 km). Vì v y, nút 3 s tr thành nút vào trong t p nút đã kh o sát. Và ta ghi giá tr 150 là th v c a nút 3. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 415
  14. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 5.6. Vòng l p th hai Tương t , chúng ta l p l i quá trình đ xác đ nh th v cho nút 4 và 5. T p nút đã kh o sát lúc này g m có nút 1, 2 và 3. Ti p theo, ta ph i xác đ nh nút ti p theo vào trong t p nút đã kh o sát. Lúc này, chúng ta có nút 4, 5 là các nút n m g n t p t p nút đã kh o sát (xu t phát t nút 2 và nút 3). Có 3 đư ng đi xu t p hát t t p nút đã kh o sát (nút 1, 2, và 3) đ n các nút 4 và 5 là các tuy n đư ng 2-4, 2-5 và 3-5. Kho ng cách ng n nh t là l trình 1-3- 5 (150 + 40 = 190 km). Vì v y, nút 5 s là nút ti p theo vào trong t p nút đã kh o sát. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 416
  15. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 5.7. Vòng l p th ba T p nút đ ã kh o sát lúc này g m có nút 1, 2 , 3 và 5. Ti p theo, ta ph i xác đ nh nút ti p theo vào trong t p nút đã kh o sát. Lúc này, chúng ta có nút 4 và nút 6 là các nút n m g n t p t p nút đã kh o sát (xu t phát t nút 5). Có 3 đư ng đi xu t phát t t p nút đã kh o sát (nút 1, 2 , 3 và 5) đ n các nút 4 và 6 là các tuy n đư ng 2-4 5-4 và 5- 6. Kho ng cách ng n nh t là l trình 1-3- 5-6 (190 + 100 = 290 km). Vì v y, nút 6 s là nút ti p theo vào trong t p nút đã kh o sát. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 417
  16. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 5.7. Vòng l p th tư (cu i cùng) - Như v y, đư ng đi có kho ng cách ng n nh t t nút 1 đ n nút 6 là 290 km theo tuy n đư ng 1-3-5-6. Cách 2: Gi i b ng cách l p b ng B ng 5.1. Gi i bài toán tìm đư n g đi ng n nh t b ng cách l p b ng T ng Tuy n T p nút Đo Nút Kho ng Nút kho ng cách đư ng đã kh o sát n gn cách chưa (Th v nút kh o n n i tr c ti p v i nút nh t ng n kh o chưa kh o sát nút chưa kh o sát ni th n nh t sát sát) {1} 1 1 2 1-2 100 100 Nút 2 1-2 1 3 1-3 200 {1, 2} 1 3 1-3 200 2 150 Nút 3 2-3 2 3 2-3 100+ 50=150 2 4 2-4 100+200=300 2 5 2-5 100+100=200 {1, 2,3} 300 2-4 4 2 3 200 2-5 5 2 3-5 3-5 Nút 5 5 190 3 150+40=190 {1, 2,3,5} 2 4 2-4 300 4 5 4 5-4 190+150=3401 5 6 5-6 90+100=290 290 Nút 6 5-6 Gi i b ng gi i Thu t Dijkstra 3.7.1. (100, 1) GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 418
  17. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) [0, -] (200, 1) Hình 5.8a. Vòng l p th nh t [100, 1] [0, -] (200, 1) Hình 5.8b. Vòng l p th nh t GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 419
  18. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) [100, 1] (300, 2) [0, -] (150, 2) (200, 2) Hình 5.9a. Vòng l p th hai GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 420
  19. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) (300, 2) [100, 1] [150, 2] (190, 3) Hình 5.9b. Vòng l p th hai (300, 2) [100, 1] (290, 5) [150, 2] [190, 3] Hình 5.10. Vòng l p th ba GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 421
  20. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) (300, 2) [100, 1] [290, 5] [150, 2] [190, 3] Hình 5.11. Vòng l p th tư [300, 2] [100, 1] [290, 5] [150, 2] [190, 3] Hình 5.12. Vòng l p th năm GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 422

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.13: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Điện - Điện Tử - Viễn Thông
111 tài liệu
1489 lượt tải
YOMEDIA
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline:0933030098

Email: support@vdoc.com.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

Đồng bộ tài khoản