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

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:77

Thêm vào BST

Báo xấu

152
lượt xem 27
download

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

Ý 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 đó.

Chủ đề:

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

Lưu

Nội dung Text: Chapter 5 - CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT

1 CHƯƠNG 5 CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT
Nội dung 2 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 b e g in S: =∅; while A ≠ do∅ be g in x: =select(A); A: =A-{ ; x} if S U { accepted the n S : =S U { ; x} x} e nd ; e nd ;
Các ví dụ:Bài toán lựa chọn công việc Bài toán:  Giả sử rằng ta có một tập S = { 1,2,...n} của n công việc sử dụng  cùng một tài nguyên, ví dụ như một phòng họp, tại một thời điểm chỉ có một công việc được tiến hành. Các công việc i được bắt đầu tại thời điểm si và kết thúc tại thời điểm fi với si ≤ fi . Nếu được chọn, công việc i sẽ chiếm khoảng thời gian là [si, fi) Hãy lựa chọn các công việc không mâu thuẫn nhau (nghĩa là hoạt  động i và j là tương thích nếu khoảng thời gian [si,fi] và [sj, fj] không phủ lấp lên nhau(tức là i và j là tương thích nếu si >= fj hay sj >= fi) sao cho số các công việc được chọn là nhiều nhất. INPUT: Thời gian khởi đầu s[1..n]; Thời gian kết thúc f[1..n] 
Tính chất lời giải Giả sử dãy công việc sắp xếp tăng dần theo thời điểm kết thúc : f1 ≤ f 2 ≤ ... ≤ fn Luôn tồn tại một lời giải tối ưu chứa công việc thứ nhất 1. Nếu A ⊂ S là lời giải tối của bài toán có chứa việc 1 thì 2. A – {1} là lời giải tối ưu của bài toán với tập S’ gồm các công việc bắt đầu từ thời điểm f1 trở đi.
Bài toán xếp lịch hoạt động Thời gian bắt đầu và kết thúc của mội công việc  • Các hoạt động tương thích tối đa mà có thể hoàn thành là: • {a3, a9, a11} chứa các hoạt động tương thích với nhau nhưng chưa phải là tập con tối đa. • {a1, a4, a8’ a11} là tập con tối đa nhưng không phải duy nhất
0 12 3 4 5 6 78 9 10 11 12 13 14 15
0 12 3 4 5 6 78 9 10 11 12 13 14 15
0 12 3 4 5 6 78 9 10 11 12 13 14 15
0 12 3 4 5 6 78 9 10 11 12 13 14 15
Các bước của thuật giải tham lam Xác định cấu trúc tối ưu của bài toán 1. Xây dựng lời giải đệ qui 2. Chứng minh với bất kỳ lời gọi đệ qui, một lựa chọn 3. tối ưu là một lựa chọn tham lam. Vì vậy nó luôn đảm bảo để tạo một lựa chọn tham lam. Chỉ ra rằng duy nhất một bài toán con sau khi ch ọn 4. tham lam là khác rỗng. Phát triển lời giải đệ qui để thực hiện giải thuật 5. tham lam.
Bước 1: Xây dựng cấu trúc tối ưu Tìm Optimal structure để xây dựng 1 lời giải tối ưu cho  bài toán từ những lời giải tối ưu của các bài toán con. Gọi Sij là tập con của các hoạt động trong S có thể  bắt đầu sau khi hoạt động ai kết thúc và trước khi hoạt động aj bắt đầu Sij chứa các hoạt động tương thích với ai và aj và  cũng tương thích với tất cả các hoạt động kết thúc không muộn hơn và bắt đầu không sớm hơn bắt đầu của aj.
Bước 1: Xây dựng cấu trúc tối ưu Giả sử các hoạt động được sắp xếp theo thứ tự tăng  thời gian kết thúc của các hoạt động Để tìm cấu trúc con cho bài toán xếp lịch, khảo sát  các bài toán con Sij khác rỗng và giả thuyết lời giải Sij chứa một số hoạt động ak sao cho fi
Bước 2: Lời Giải Đệ Qui Tìm các tập con kích cỡ tối đa Aik và Akj chứa các  hoạt động tương thích nhau cho mỗi bài toán con. Tạo tập kích cỡ tối đa Aij chứa các hoạt động tương  thích Aij = Aik U {ak} U Akj Đặt c[i,j] là số hoạt động của 1 tập con kích cỡ tối đa  chứa các hoạt động tương thích trong Sij: • Ta có công thức đệ qui để tìm c[i, j]
Bước 2: Lời Giải Đệ Qui Chọn hoạt động am trong Sij có thời gian hoàn thành  sớm nhất, rồi tìm lời giải cho bài toán con Smj. Hoạt động được chọn theo cách tham lam nghĩa là nó làm tối đa thời gian còn lại chưa được xếp lịch để được xếp lịch cho nhiều hoạt động khác. Loại bỏ những hoạt động chưa được xếp lịch (bị trùng  lắp). Lặp lại quá trình trên 