Bài giảng Thuật toán: Chương 4 - GV. Nguyễn Thanh Cẩm

Chương 4 Thuật toán tham lam thuộc bài giảng thuật toán, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: thuật toán tham lam, một số thí dụ minh họa.
Nội dung trích xuất từ tài liệu:
Bài giảng Thuật toán: Chương 4 - GV. Nguyễn Thanh CẩmTRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm Nội Dung C1 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP C2 CHIA ĐỂ TRỊ C3 QUY HOẠCH ĐỘNG C4 THUẬT TOÁN THAM LAM C5 THUẬT TOÁN QUAY LUINguyễn Thanh Cẩm THUẬT TOÁN THAM LAM 4.1 Thuật toán tham lam 4.2 Một số bài toán minh họaNguyễn Thanh Cẩm THUẬT TOÁN THAM LAM 4.1 Thuật toán tham lam 4.1.1 Đặc điểm chung của thuật toán tham lam 4.1.2 Thuật toán tham lam Sự khác nhau giữa thuật toán tham lam và 4.1.3 thuật toán quy hoạch độngNguyễn Thanh Cẩm 4.1.1 Đặc điểm chung của thuật toán tham lam  Một bài toán thực hiện cấu trúc con tối ưu (optimal substructure) nếu cách giải quyết tối ưu của bài toán chứa đựng cách giải quyết tối ưu những bài toán con của nó.  Đối với nhiều bài toán, thuật toán tham lam hầu như không cho ra lời giải tối ưu toàn cục, vì chúng thường không chạy trên tất cả các trường hợp. Tuy nhiên, các thuật toán này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối ưu.  Nếu một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như quy hoạch động …Nguyễn Thanh Cẩm 4.1.2 Thuật toán tham lam Thuật tham lam có 05 thành phần:  Một tập hợp các ứng viên C (candidate), để từ đó tạo ra lời giải.  Một hàm lựa chọn Select(C), để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào lời giải.  Một hàm khả thi Feasible(S  x), dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải.  Một hàm mục tiêu Solution(S), ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh.  Một hàm đánh giá, chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.Nguyễn Thanh Cẩm 4.1.2 Thuật toán tham lam Thuật tham lam: void Greedy; //Giả sử C là tập các ứng cử viên { S = ; // S là lời giải xây dựng theo thuật toán While ( (C  0) and not Solution(S)) { x  Select(C); C = Cx; If (Feasible(S  x)) S=S x } If (Solution(S) ) Return S }Nguyễn Thanh Cẩm 4.1.2 Thuật toán tham lam  Chúng minh tính đúng đắn:  Để chỉ ra thuật toán không cho lời giải đúng chỉ cần đư-a ra một phản ví dụ  Việc chứng minh thuật toán đúng khó hơn nhiều và ta sẽ nghiên cứu cụ thể trong phần sau đây :  Lập luận biến đổi (Exchange Argument)  Giả sử cần chứng minh thuật toán A cho lời giải đúng. A(I) là lời giải tìm được bởi thuật toán A đối với bộ dữ liệu I. Còn O là lời giải tối ưu của bài toán với bộ dữ liệu này.  Ta cần tìm cách xây dựng phép biến đổi  để biến đổi O thành O’ sao cho:  O’ cũng tốt không kém gì O (Nghĩa là O’ vẫn tối ưu).  O’ giống với A(I) nhiều hơn O.  Giả sử đã xây dựng được phép biến đổi vừa nêu. Để chứng minh tính đúng đắn dựa vào hai sơ đồ chứng minh sau  1) Chứng minh bằng phản chứng: Giả sử A không đúng đắn, hãy tìm bộ dữ liệu I sao cho A(I) khác với lời giải tối ưu của bài toán. Gọi O là lời giải tối ưu giống với A(I) nhất => A(I) khác O. Dùng phép biến đổi  chúng ta có thể biến đổi O  O’ sao cho O’ vẫn tối ưu và O’ giống với A(I) hơn => mâu thuẫn giả thiết O là lời giải tối ưu giống với A(I) nhất.  2) Chứng minh trực tiếp: O là lời giải tối ưu. Biến đổi O  O’ giống với A(I) hơn là O. Nếu O’ = A(I) thì A(I) chính là phương án tối ưu ngược lại biến đổi O’  O’’ giống với A(I) hơn. Cứ thế ta thu được dãy O’, O’’ ,O’’’ …..ngày càng giống hơn, và chỉ có một số hữu hạn điều kiện để so sánh nên chỉ sau một số hữu hạn lần phép biến đổi sẽ kết thúc và đó là tại A(I).Nguyễn Thanh Cẩm 4.1.3 Sự khác nhau giữa thuật toán tham lam và thuật toán quy hoạch động  Toàn bộ phương pháp tối ưu có thể đạt được, từ việc chọn tối ưu trong từng bước chọn. Về khía cạnh này, thuật toán tham lam khác với thuật toán quy hoạch động ở chỗ:  Trong quy hoạch động chúng ta thực hiện chọn cho từng bước, nhưng việc lựa chọn này phụ thuộc vào cách giải quyết các bài toán con.  Với thuật toán tham lam, tại mỗi bước chúng ta chọn bất cứ cái gì là tốt nhất vào thời điểm hiện tại, và sau đó giải quyết các vấn đề phát sinh t ...