Embedded Files
Nguồn tham khảo:
Competitive Programming 4, Book 1, Steven Halim (CP4)
GeeksforGeeks (G4G)
Giới thiệu
Giới thiệu
Trong nhiều trường hợp, giải thuật vét cạn không đủ thời gian thực hiện khi số phần tử hoặc số trường hợp cần xem xét quá lớn, dù được cải tiến bằng phương pháp nhánh cận, số trường hợp còn lại cần xét cũng rất nhiều thì người ta đề xuất một giải pháp khác là tham lam (greedy). Một thuật toán được gọi là tham lam nếu nó lựa chọn một phương án tối ưu cục bộ tại mỗi bước với hi vọng sẽ đạt được kết quả tối ưu toàn cục (CP4). Trong nhiều trường hợp, giải thuật tham lam cho ra kết quả chính xác và thực hiện trong thời gian rất nhanh, nhiều trường hợp nó sẽ cho kết quả sai (không phải kết quả tối ưu toàn cục).
Dù cho đến nay chưa có công thức chắc chắn nào để nhận biết được một bài toán có thể giải bằng tham lam được hay không, nhiều tài liệu cũng đưa ra được hai dấu hiệu có thể tạm dùng để nhận biết những bài toán như vậy:
Nó có cấu trúc con tối ưu.
Nghĩa là giải pháp tối ưu của bài toán lớn chứa đựng giải pháp tối ưu của các bài toán con.
Nó có tính chất tham lam.
Nghĩa là, nếu ta thực hiện một lựa chọn có vẻ như tốt nhất tại thời điểm hiện tại rồi tiếp tục làm vậy với các bài toán con, chúng ta sẽ đạt tới giải pháp tối ưu. Chúng ta sẽ không cần phải xem xét lại những lựa chọn trước đó nữa.
Để dễ hiểu chúng ta cùng xem xét một vài ví dụ sau đây.
Một số ví dụ
Một số ví dụ
Ví dụ 1 - Coin Change
Ví dụ 1 - Coin Change
Tóm tắt: Cho N đồng xu với các mệnh giá khác nhau (đơn vị cent). Hãy tìm số lượng đồng xu nhỏ nhất để đáp ứng vừa đủ V cents. Giả định rằng chúng ta có thể lấy một số lượng không giới hạn một loại mệnh giá. Ví dụ, với n = 4, cho coinValue = {25, 10, 5, 1} cents, chúng ta muốn đáp ứng một lượng V = 42 cents. Kết quả bài toán là 5 đồng xu: 25 + 10 + 5 + 1 + 1
Giải thuật tham lam để giải bài toán trên như sau:
Chọn đồng xu có mệnh giá lớn nhất mà không vượt qua giá trị V. lấy V' = V - đồng lớn nhất vừa chọn, cứ tiếp tục như vậy chon đến khi V' = 0.
Sở dĩ bài toán trên có thể giải được bằng tham lam cho ra kết quả tối ưu vì nó đáp ứng được 2 yêu cầu chúng ta nói đến ở trên.
Có cấu trúc con tối ưu:
Ta thấy rằng để đáp ứng 42 cents, ta dùng 5 đồng: 25 + 10 + 5 + 1 + 1.
Bài toán con là cần đáp ứng 17 cents (khi đã trừ đồng lớn nhất hiện tại): 10 + 5 + 1 + 1 (cấu hình này chứa đựng trong bài toán lớn)
Bài toán con cấp thấp hơn là 7 cents: 5 + 1 + 1 (cũng được chứa đựng trong bài toán lớn ban đầu)
Có tính chất tham lam:
Khi ta chọn đồng lớn nhất tại thời điểm hiện tại là 25 cents, coi như một lựa chọn tối ưu cục bộ. Dùng đúng cách này để giải quyết cho bài toán con nhỏ hơn, tức chọn đồng 10 cents cho V' = 17, .... Thực hiện đúng chiến thuật này đưa ra đến giải pháp tối ưu cho bài toán, ít nhất là cho bộ input này.
Tuy nhiên, giải thuật tham lam không thể giải được tối ưu cho mọi input của bài toán trên. Ví dụ, với n = 3, coinValue = {4, 3, 1}, ta cần đáp ứng V = 6 cents. Giải thuật tham lam cho ra kết quả 3 đồng xu: 4 + 1 + 1. Tuy nhiên, kết quả tối ưu cho input này là 2: 3 + 3. Chúng ta sẽ bàn kỹ lại giải pháp này ở phần tiếp theo (Quy hoạch động).
Tóm tắt: Cho một số máy li tâm trên trạm không gian quốc tế, mỗi máy li tâm chứa 1 ≤ C ≤ 5 khoang có thể chứa 0, 1 hoặc 2 mẫu vật. Cho 1 ≤ S ≤ 2C mẫu vật và một list M khối lượng của S mẫu vật đó. Hãy xác định khoang nào nên chứa những mẫu vật nào sao cho tối thiểu hóa sự "mất cân bằng".
Trong đó, sự mất cân bằng được định nghĩa như sau:
Đặt A = Sum(Mj)/C, i từ 1 đến S, nghĩa là A là khối lượng trung bình của mỗi khoan.
Độ mất cân bằng = Sum(|Xi -A|), trong đó Xi là tổng khối lượng các mẫu vật được chứa trong khoang Ci.
Nguồn ảnh: CP4
Ảnh mô tả về độ mất cân bằng (IMBALANCE) với C = 3, S = 4, M = {5, 1, 2, 7}
Để thực hiện được giải thuật tham lam cho bài toán này, chúng ta quan sát qua về bộ input mẫu:
Nếu có một khoan trống, tức nhiên ta nên di chuyển mẫu vật từ một khoan đang chứa 2 mẫu vào nó, điều đó sẽ giảm bớt độ mất cân bằng.
Nếu S > C, ta phải rải S - C mẫu vật vào các khoan đang chứa sẵn 1 mẫu vật. Quan sát ảnh dưới đây:
Nguồn ảnh: CP4
Như vậy, nếu S < C, ta phải rãi mỗi vật vào một khoan, chấp nhận có khoan trống. Nếu C < S < 2C, ta sẽ them 2C - S mẫu vật giả với khối lượng 0, sắp xếp các mẫu vật theo khối lượng tăng dần. Lân lược bắt cặp mẫu vật đầu với cuối, mẫu thứ 2 với kế cuối, .... bỏ vào các khoan C1, C2, ...
Theo ví dụ trên, C = 3, S = 4, M = {5, 1, 2, 7}. Ta thêm 6 -4 = 2 mẫu vật với khối lượng 0 vào M --> {5, 1, 2, 7, 0, 0} --> Sắp xếp tăng dần --> {0, 0, 1, 2, 5, 7}.
Bắt cặp 0 + 7 đưa vào khoan 1, 0 + 5 đưa vào khoan 2, 1 + 2 đưa vào khoan 3.
A = (7+5+3)/3 = 5
Imbalance = (7-5)+(5-5) +(5-3) = 4.
Nguồn ảnh: CP4
Tóm tắt: Đặt n béc tưới xoay theo hàng ngang vào một bãi cỏ có chiều dài L và chiều rộng W. Các bec tưới đều được đặt ở trung tâm theo chiều dọc của bãi cỏ. Mỗi bec được cho một khoảng cách với mép trái bãi cỏ và có bán kính phủ R. Hỏi cần bật tối thiểu bao nhiêu bec để có thể tưới hết bãi có trên. N <=10^4.
Ví dụ với test case sau:
Nguồn ảnh: CP4
Kết quả của testcase này là 6, gồm các bec {A, B, D, E, F, H}, bỏ qua hai bec {C, G}.
Chúng ta có thể dùng backtracking để sinh tất cả các cấu hình của n bec tưới, kết hợp kỹ thuật nhánh cận để chọn cấu hình có ít bec nhất. Tuy nhiên với n lên đến 10^4 thì số trường hợp cần sinh quá lớn, khó có thể thử hết trong thời gian cho phép.
Để thực hiện được giải thuật tham lam, chúng ta nhìn qua hình bên phải của hình trên. Ta sẽ thấy một bec thứ i đang ở tọa độ ngang x thì sẽ có độ phủ ngang từ x - dx đến x+dx, trong đó dx = sqrt(R^2 - (W/2)^2). Khi bec này bật, bec tiếp theo cần bật phải có độ phủ gối vào độ phủ này. Nếu không thể gối được thì không thể phủ vùng cỏ tiếp giáp.
Quan sát tiếp theo nữa là một bec có vùng phủ nằm hoàn toàn trong vùng phủ của một bec khác thì ta bỏ qua nó và chọn bec có vùng phủ lớn hơn.
Như vậy, sau khi đã tính được vùng phủ các bec, tức mỗi bec được lưu hai chỉ số firstpoint và endpoint, ta sắp xếp tăng dần theo first và giảm dần theo end nếu trùng first.
Đi từ trái qua, chọn bec có first nhỏ nhất, sau đó chọn tiếp bec có vùng phủ gối trong vùng phủ của nó và ưu tiên chọn bec có end xa hơn. Nếu trong quá trình tìm có một vị trí mà không tìm được bec nào thỏa việc gối lên vùng phủ trước thì ta kết luận không thể phủ hết được, ngược lại ta cứ tiếp tục đi theo chiến thuật ban đầu. Mỗi lần chọn được một bec thì đếm số lượng lên 1 và lưu nhãn bec đó vào thùng chứa, đồng thời cập nhật lại bec đang xét để xét các bec tiếp theo. Kỹ thuật này còn gọi là kỹ thuật đường quét (Sweep line) mà ta sẽ thảo luận sâu hơn trong chuyên đề sau.
Bài tập
Bài tập
Nhiệm vụ 1 - UVa 10020 - Minimal Coverage
Nhiệm vụ 2 - UVa 1193 - Rada Installation
Nhiệm vụ 3 - UVa 11292 - Dragon of LooWater
Nhiệm vụ 4 - UVa 12390 - Distributing Ballot Boxes
Nhiệm vụ 5 - UVa 12321 - Gas Stations
Nhiệm vụ 6 - Sức mạnh phi thường (Codeforce)
Nhiệm vụ 7 - UVa 1153 - Keep the Customer Satisfied
Thực hiện contest ngắn: Practices Greedy
Page updated
Google Sites
Report abuse