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

Bài giảng Phân tích và thiết kế thuật giải: Bài 5 - TS. Ngô Quốc Việt

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:55

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

Bài giảng Phân tích và thiết kế thuật giải - Bài 4 giới thiệu về thuật giải tham lam. Các nội dung chính trong chương này gồm có: Các thuật giải tham lam, một số thuật giải Greedy, 0-1 vs. Fractional Knapsack, Greedy Fractional Knapsack Algorithm,... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Phân tích và thiết kế thuật giải: Bài 5 - TS. Ngô Quốc Việt

  1. PHÂN TÍCH THIẾT KẾ THUẬT GIẢI THUẬT GIẢI THAM LAM TS. NGÔ QUỐC VIỆT- 2015
  2. Nội dung 1. Giới thiệu 2. Các thuật giải tham lam 3. Bài tập 4. Hỏi đáp. 2
  3. Giới thiệu  Thuật giải tham lam (greedy algorithm)  Là một phương pháp tìm kiếm lời giải “tối ưu”.  Thuật giải tham lam tiếp cận theo cách: ở mỗi bước chọn lời giải tốt nhất  Được gọi là tối ưu cục bộ. Phần lớn tìm được lời giải tối ưu.  Tuy nhiên có thể vì lựa chọn này dẫn đến lời giải sau cùng không tối ưu toàn cục. 3
  4. Một số thuật giải Greedy  Fractional knapsack algorithm  Huffman codes  Kruskal's MST algorithm  Prim's MST algorithm  Dijkstra's SSSP algorithm 4
  5. Thuật giải tham lam- Minh hoạ 1  Bài toán đổi tiền lẻ: cho một tập các đồng xu có mệnh giá khác nhau. Cần đổi N đồng lấy các đồng xu sao cho số đồng xu ít nhất.  Ví dụ: 24 = 10+ 10 + 1 + 1 + 1 + 1. Tuy nhiên nếu có đồng 8 xu thì cách chọn trên không tối ưu.  Tiếp cận theo thuật giải tham: chọn đồng xu mệnh giá lớn nhất có thể tại mỗi bước. 5
  6. Thuật giải tham lam- Minh hoạ 1  Sắp xếp tập đồng xu giảm dần 6
  7. Thuật giải tham lam- Minh hoạ 2  Bài toán lịch làm việc:  Việc j bắt đầu tại sj và kết thúc tại fj.  Mỗi thời điểm làm một việc.  Hai công việc không được làm chồng chéo.  Yêu cầu: làm nhiều việc nhất có thể (tình theo thời gian, chứ không phải số đầu việc) 7
  8. Thuật giải tham lam- Minh hoạ 2  Tiếp cận tham lam cho bài toán này. Xét các thứ tự có thể.  Bắt đầu sớm nhất: xếp tăng dần theo si.  Kết thúc sớm nhất: xếp tăng dần theo fi.  Khoảng ngắn nhất: xếp tăng dần theo (fi-si)  Ít chồng chéo nhất: với việc j, đếm số lượng (gọi là cj) việc có chồng chéo với việc j. Xếp tăng dần theo cj. 8
  9. Thuật giải tham lam- Minh hoạ 2  Giả sử chọn: sắp xếp tăng dần theo fi. Việc j có thể thêm vào nếu không chồng chéo với việc cuối cùng vừa thêm vào A. 9
  10. Thuật giải tham lam- Minh hoạ 3  Bài toán xếp lịch giảng dạy n môn học vào m phòng học.  Môn j bắt đầu tại sj và kết thúc tại fj.  Mục tiêu: tìm số phòng tối thiểu để có thể dạy tất cả các môn sao cho một môn không dạy ở hai phòng cùng lúc trong ngày.  Ví dụ có 4 phòng học, và 10 môn. 10
  11. Thuật giải tham lam- Minh hoạ 3  Cách sắp xếp khác 11
  12. Thuật giải tham lam- Minh hoạ 3  Xếp môn học tăng dần theo si.Xếp vô phòng học 1 trước, khi phòng học này đầy, xét đến phòng học kế tiếp … 12
  13. Thuật giải tham lam- Minh hoạ 4  Bài toán xếp lịch nhằm giảm tối đa việc trễ giao hàng. Mô tả:  Việc j cần tj thời gian và phải giao tại thời điểm dj.  Nếu j bắt đầu lúc sj, thì sẽ kết thúc tại fj = sj+tj.  Độ trễ lj=max(0, fj-dj).  Mục tiêu: sắp xếp các việc sao cho giảm tối đa L=max(lj). 13
  14. Thuật giải tham lam- Minh hoạ 4 Ví dụ: sắp lịch cho 6 việc có thời gian làm và thời hạn giao hàng như sau Một cách sắp xếp 14
  15. Thuật giải tham lam- Minh hoạ 4  Sắp xếp các việc theo tiêu chuẩn nào đó (tăng dần theo thời gian xử lý, theo thời hạn giao hàng, …)  Thực hiện xếp vô hàng đợi các việc thoả mãn ràng buộc (không chồng chéo) theo thứ tự đã chọn. Ví dụ thuật giải tham cho các việc xếp tăng dần theo deadline như sau 15
  16. Thuật giải tham lam- Minh hoạ 4 16
  17. Thuật giải tham lam- Minh hoạ 4  Cải tiến xếp lịch sao cho không có thời gian rảnh. Ví dụ:  Thực hiện bằng cách bổ sung thêm bước hoán vị ‘nghịch thế’ sau khi đã xếp lịch bằng thuật giải tham. Chú ý hoán vị các nghịch thế kề nhau (giống Buble sort) nếu cần. 17
  18. 0-1 vs. Fractional Knapsack  0-1 Knapsack Problem:  Các vật không thể chia nhỏ  Hoặc là chọn vật hoặc không chọn cho vào ba lô  Giải bằng DP hoặc Greedy  Fractional Knapsack Problem:  Vật có thể được chia nhỏ (có thể lấy một phần cho vào ba lô)  Giải thông qua greedy algorithm… 18
  19. Greedy Fractional Knapsack Algorithm  Sắp xếp các items theo giá trị trên mỗi đơn vị giảm dần  While ba lô còn trống do  Xét next item trong danh sách đã xếp giảm dần  Lấy càng nhiều càng tốt  O(n log n) running time ? 19
  20. Greedy Fractional Knapsack Algorithm Algorithm fractionalKnapsack(S, W) Input: set S of items w/ benefit bi and weight wi; max. weight W Output: amount xi of each item i to maximize benefit w/ weight at most W for each item i in S xi  0 vi  bi / wi {value} w0 {total weight} while w < W remove item i w/ highest vi xi  min{wi , W - w} w  w + min{wi , W - w} 20
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