tailieunhanh - Chapter 5 - CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT

Ý tưởng phương pháp tham lam Các giải thuật tối ưu hóa thường đi qua một số bước với một tập các khả năng lựa chọn tại mỗi bước. Một giải thuật tham lam thường chọn một khả năng mà xem như tốt nhất tại lúc đó. | CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT CHƯƠNG 5 Nội dung Qui hoạch động Giải thuật tham lam Giải thuật quay lui (backtracking) Giải thuật nhánh và cận Giải thuật tham lam (Greedy Algorithm) Ý tưởng phương pháp Lược đồ giải thuật Các ví dụ Ý tưởng phương pháp tham lam Các giải thuật tối ưu hóa thường đi qua một số bước với một tập các khả năng lựa chọn tại mỗi bước. Một giải thuật tham lam thường chọn một khả năng mà xem như tốt nhất tại lúc đó. Tức là, giải thuật chọn một khả năng tối ưu cục bộ với hy vọng sẽ dẫn đến một lời giải tối ưu toàn cục. Vài thí dụ của giải thuật tham lam: - Giải thuật Prim để tính cây bao trùm tối thiểu - Giải thuật Dijkstra để giải bài tóan những lối đi ngắn nhất từ một đỉnh nguồn (single-source shortest paths problem). Ý tưởng phương pháp tham lam Lưu ý Phương pháp tham lam thường được áp dụng rộng rãi trong các bài toán tối ưu Trong một số trường hợp, không tìm được nghiệm đúng bài toán mà chỉ là nghiệm “tốt”. Việc giải bài toán theo . | CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT CHƯƠNG 5 Nội dung Qui hoạch động Giải thuật tham lam Giải thuật quay lui (backtracking) Giải thuật nhánh và cận Giải thuật tham lam (Greedy Algorithm) Ý tưởng phương pháp Lược đồ giải thuật Các ví dụ Ý tưởng phương pháp tham lam Các giải thuật tối ưu hóa thường đi qua một số bước với một tập các khả năng lựa chọn tại mỗi bước. Một giải thuật tham lam thường chọn một khả năng mà xem như tốt nhất tại lúc đó. Tức là, giải thuật chọn một khả năng tối ưu cục bộ với hy vọng sẽ dẫn đến một lời giải tối ưu toàn cục. Vài thí dụ của giải thuật tham lam: - Giải thuật Prim để tính cây bao trùm tối thiểu - Giải thuật Dijkstra để giải bài tóan những lối đi ngắn nhất từ một đỉnh nguồn (single-source shortest paths problem). Ý tưởng phương pháp tham lam Lưu ý Phương pháp tham lam thường được áp dụng rộng rãi trong các bài toán tối ưu Trong một số trường hợp, không tìm được nghiệm đúng bài toán mà chỉ là nghiệm “tốt”. Việc giải bài toán theo phương pháp tham lam tránh được bùng nổ tổ hợp và khá hiệu quả Sơ đồ chung của giải thuật tham lam Dạng các bài toán giải bằng giải thuật Tham Lam Giả sử ta phải chọn một tập con R của các phần tử của một tập S = (s1, s2,.,sn ) sao cho : Tập R thỏa mãn một điều kiện ràng buộc W(R) nào đó; Một hàm mục tiêu Z(R) đạt giá trị tối ưu (cực đại hoặc cực tiểu). Sơ đồ Bước 1: Chọn một phần tử s có lợi nhất cho lời giải trong bước đó sao cho phần tử này cùng với lời giải tối ưu của bài toán với tập con S {s} với ràng buộc W(R {s }) và hàm mục tiêu Z(R {s}) là lời giải tối ưu của bài toán. Bước 2: Tiếp tục tìm phần tử tiếp theo có lợi nhất với tập con S = S {s} với ràng buộc W=W(R {s}) và hàm mục tiêu Z = Z(R {s}). Cho đến khi không thể tìm được phần tử như vậy hoặc tập S = . Lược đồ giải thuật –bỏ Greedy(A, S) // A is the candidate set, S is the solution begin S: = ∅; while A ≠∅do begin x: = select(A); A: = A-{x}; if S U {x} accepted then S: = S U {x}; end; end; Các ví dụ:Bài toán lựa chọn .