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

Cấu trúc dữ liệu và giải thuật (phần 21)

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

Thêm vào BST
Báo xấu
92
lượt xem 33
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bạn cũng đã từng nghe tới thuật toán tham lam khi bắt đầu bước vào thế giới công nghệ thông tin, và trong tài liệu này các bạn sẽ được làm quen với thuật toán này, khá thú vị và hiểu quả trong một số bài toán

Chủ đề:

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

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật (phần 21)

  1. Please purchase a personal license. personal
  2. CÁC THU T TOÁN TO THAM LAM (GREEDY) THAM
  3. Gi i thu t tham lam Gi thu tham Khái ni m: M i bài toán ta có t p h p nh ng l a ch n gi i quy t bài toán. Gi i thu t tham lam x u t vi c l a ch n kh năng t t nh t cho bài toán ó. Ví d : Bài toán cây khung t i thi u Bài toán ư ng i ng n nh t
  4. Traveling Salesperson Problem Traveling Bài toán: Bài toán tìm ư ng i c a ngư i giao hàng (TSP) - Ngư i giao hàng c n i giao hàng t i n thành ph . Xu t phát t m t thành ph nào ó, i qua các thành ph khác giao hàng và tr v thành ph ban u. - M i thành ph ch n 1 l n. Kho ng cách gi a các thành ph là xác nh - Hãy tìm m t chu trình sao cho t ng dài ư ng i là nh nh t
  5. Traveling Salesperson Problem Traveling Gi i quy t bài toán v i phương pháp vét c n: - Xét t t c các chu trình, và ch n chu trình dài nh nh t Ph i xét t t c (n-1)!/2 chu trình??? - Ch n 1 nh b t kì, t i nh này có n-1 c nh t i n- 1 nh khác, nên có n-1 các ch n c nh u tiên. - Sau khi ch n ư c c nh u tiên, còn n-2 cách ch n c nh th 2. - Ti p t c như v y ta có (n-1)! cách ch n chu trình - Do ch quan tâm n dài, không quan tâm n hư ng (n-1)!/2 phương án
  6. Traveling Salesperson Problem Traveling Gi i quy t bài toán v i gi i thu t tham lam: 1. Xét các c nh có dài t nh nl n ưa vào chu trình ( có n(n-1)/2 c nh) 2. M i c nh s ư c ưa vào chu trình n u: 1. Không t o thành m t chu trình thi u (t o thành chu trình trư c khi i h t t t c n nh) 2. Không t o thành m t nh có c p >=3 ( không có nhi u hơn 2 c nh xu t phát t m t nh, do yêu c u c a bài toán m i thành ph ch n 1 l n: 1 n, 1 i) 3. L p l i bư c 2 cho n khi xây d ng ư c 1 chu trình
  7. Traveling Salesperson Problem Traveling Ví d : Cho dài ư ng i gi a các thành ph ư c bi u di n b ng ma tr n k sau. Tìm chu trình ng n nh t gi a các thành ph 1234567 • (3,5) = 1 (5,6) = 2 (4,7) = 4 1 16 12 13 6 7 11 2 21 18 8 19 5 (2,7) = 5 (1,6) = 7 (1,4) = 13 3 20 1 3 15 (2,3) =21 4 14 10 4 T ng ư ng i: (1,4,7,2,3,5,6,1)=53 5 2 17 6 9 ây ch là phương án t t Phương án t i ưu: (1,4,7,2,5,3,6,1) =41
  8. Traveling Salesperson Problem Traveling Gi i thu t: void TSP (Graph &g) { E – t p h p các c nh; S p x p các c nh trong E theo th t tăng d n; cycle = NULL; length_cycle = 0; while (E !=F) { if ( c nh e th a mãn i u ki n ) { cycle = cycle + e; length_cycle = length_cycle + length(e); } E = E – e; } }
  9. Traveling Salesperson Problem Traveling Gi i pháp khác c a thu t toán tham lam: 1. Xu t phát t 1 nh b t kỳ, ch n 1 c nh có dài nh nh t t nh ó n nh k ti p. 2. T nh k ti p, ch n c nh có dài nh nh t i ra t nh này th a m n 2 i u ki n ( không t o chu trình trư c khi qua n nh, 1 nh không l n hơn 2 ư ng i) 3. L p l i bư c 2 cho n khi i n n nh thì quay l i nh xu t phát
  10. Traveling Salesperson Problem Traveling Bài t p: Tìm ư ng i ng n nh t c a ngư i giao hàng v i dài gi a các thành ph cho b i ma tr n sau: ư ng i ã tìm ra t i ưu chưa?
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

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
2=>2