intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Thêm vào BST
Báo xấu
89
lượt xem 15
download
 
  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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2431 lượt tải
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: 093 303 0098

Email: support@tailieu.vn

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

 

Đồng bộ tài khoản
4=>1