Các dạng bài sử dụng thuật toán tham lam – Greedy Algorithm Problems

2284

Thuật toán tham lam là gì

Thuật toán tham lam hay chính xác hơn là một kĩ thuật (technique) tương tự quy hoạch động hay chia để trị cũng là những kĩ thuật luôn chọn quyết định tốt nhất ở thời điểm hiện tại hay lựa chọn tối ưu cục bộ và hy vọng rằng quyết định đó sẽ dẫn tới giải pháp tối ưu toàn cục của bài toán. Do đó nó khác với quy hoạch động luôn duyệt hết và đảm bảo tìm thấy lời giải, với quy hoạch động mọi quyết định đều phải dựa vào quyết định của bài toán con đã được giải ở bước trước đó và có thể xét lại đường đi của bước trước hướng tới lời giải. Giải thuật tham lam quyết định sớm và thay đổi đường đi thuật toán theo quyết định đó, và không bao giờ xét lại các quyết định cũ. Chính vì vậy trong nhiều bài toán tham lam có thể không cho kết quả chính xác nhất.
Tham lam không dựa vào quyết định của bài toán trước đó để đưa ra quyết định mà tại mỗi bước nó tự ra quyết định tối ưu cục bộ và quyết định này sẽ quyết định đường đi của mọi bước tiếp theo, quyết định này cũng không thể quay lại hay phục hồi.

https://vi.wikipedia.org/wiki/Giải_thuật_tham_lam

Ưu điểm của tham lam

  • Thuật toán tham lam dễ dàng tiếp cận với các bài toán đặc biệt là các bài toán đồ thị và NP-đầy đủ mặc dù không đảm bảo tìm ra được lời giải tối ưu tuy nhiên nó vẫn trở nên rất hữu ích bởi việc dễ dàng thiết kế để cho ra lời giải ước lượng (tương đối chính xác).
  • Độ phức tạp của tham lam là khá rõ ràng từ đó bạn có thể xem xét độ phù hợp của tham lam đối với thời gian chạy của bài toán cần giải quyết.
  • Nếu có thể chứng minh rằng 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ẽ trở thành phương pháp đượ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.

Nhược điểm

  • Rất khó để hiểu hay chứng minh 1 lời giải tham lam là kết quả tối ưu ngay kể cả khi nó đưa ra lời giải tối ưu
  • Đa số các thuật toán tham lam là không chính xác.

Các bài toán tham lam

Bài toán trồng cây

Problem: Một nông dân đang muốn trồng hoa vào khu vườn của mình. Để cho khu vườn trở nên thật màu sắc ông quyết định trồng nhiều loài hoa khác nhau vào khu vườn. Mỗi loài hoa có 1 cách trồng khác nhau do đó ông sẽ trồng từng loài hoa vào các ngày liên tiếp nhau. Cháu của ông rất mong chờ được thấy tất cả loài hoa trong khu vườn đều nở hoa trông sẽ tuyệt vời như thế nào. Tuy nhiên mỗi loài hoa lại có thời gian phát triển từ lúc trồng tới lúc nở hoa khác nhau. Nhiệm vụ của bạn là giúp ông nông dân tìm ra ngày sớm nhất mà tất cả loài hoa đều nở hoa.
Trong kho của ông nông dân hiện tại có một số loài hoa

Loài hoa Thời gian hoa sẽ nở
1 Hoa hồng 3
2 Hoa lan 4
3 Hoa cúc 2
4 Hoa mười giờ 1

 

Idea: Mỗi cách trồng là 1 hoán vị của N (N là số loài hoa) với mỗi cách trồng sẽ cần một thời gian chờ để tất cả loài hoa đều nở. Ví dụ
Với hoán vị 1234:

  • Trồng hoa hồng (1) vào ngày thứ 1 => sau 1 + 3 = 4 ngày hoa sẽ nở
  • Trồng hoa lan (2) vào ngày thứ 2 => sau 2 + 4 = 6 ngày hoa sẽ nở
  • Trồng hoa cúc (3) vào ngày thứ 3 => sau 3 + 2 = 5 ngày hoa sẽ nở
  • Trồng hoa mười giờ (1) vào ngày thứ 4 => sau 4 + 1 = 5 ngày hoa sẽ nở

Thời gian sớm nhất tất cả loài hoa đều nở là ngày thứ 7
Với hoán vị 2134:
Thời gian sớm nhất tất cả loài hoa đều nở là ngày thứ 6
Dễ thấy với các loài hoa có thời gian phát triển lâu cần được trồng trước các loài hoa phát triển nhanh (tham lam) => Sort theo thứ tự giảm dần thời gian phát triển của hoa để sinh ra hoán vị tốt nhất.

Implementation

 

Ngoài ra, còn có 1 số bài toán tham lam tương tự dạng này nữa:
https://www.hackerrank.com/challenges/angry-children/problem
https://www.hackerrank.com/challenges/greedy-florist/problem

Bài toán sắp xếp công việc

Problem: Ngày CN, Minh có rất nhiều dự định muốn hoàn thành chẳng hạn như làm bài tập lớn môn A, viết bài viblo, ôn tập môn B, nghe nhạc, chạy bộ, … Mỗi công việc đều có thời gian lý tưởng để bắt đầu và kết thúc của nó. Tuy nhiên có một số công việc không thể cùng hoàn thành bởi công việc trước chưa kết thúc công việc sau đã bắt đầu. Chẳng hạn

Task start end
làm btl môn A 8 (h) 10 (h)
viết bài viblo 9 11
ôn tập môn B 10 12
nghe nhạc 14 15
chạy bộ 17 18

Chúng ta không thể hoàn thành cả 2 task là viết bài viblo và làm btl môn A hay ôn tập môn B. Nếu chọn thực hiện viết bài viblo bạn chỉ có thể hoàn thành 3/5 task trong khi nếu không chọn viết bài viblo bạn có thể hoàn thành 4/5 task.
Chúng ta cần giúp Minh tìm ra được số task có thể hoàn thành nhiều nhất mỗi khi ngày CN tới.

Idea: Dễ thấy để chọn được ra nhiều task nhất ta sẽ chọn ra task có thời gian kết thúc sớm nhất và đảm bảo thời gian bắt đầu của nó muộn hơn thời gian kết thúc của các task được chọn trước đó. Riêng với task đầu tiên ta chỉ cần chọn ra task kết thúc sớm nhất.
Ý tưởng tham lam này cũng đã được chứng minh là đúng trong mọi TH tuy nhiên mình nhớ được link để trích dẫn.

Implementation:

 

 

Ngoài ra, còn có 1 số bài toán tham lam tương tự dạng này kết hợp với disjoin set nữa:
https://www.geeksforgeeks.org/job-sequencing-problem-set-1-greedy-algorithm/

Bài toán ATM withdrawal

Đây là link gốc của bài toán: http://codeforces.com/problemset/gymProblem/100541/C
Đây là lời dịch tiếng viết và solution

Vinh làm việc cho 1 nhà máy sản xuất cây ATM. Chức năng cơ bản của cây ATM đó là rút tiền. Khi người dùng yêu cầu rút W VND, cây ATM sẽ trả ra N tờ tiền có tổng đúng bằng W. Ở thế hệ tiếp theo của cây ATM, Vinh phải làm việc với thuật toán để tối ưu số tờ tiền trả ra cho mỗi giao dịch là nhỏ nhất.

Nhiệm vụ của bạn là giúp Vinh thực hiện công việc của anh ý với các tờ tiền được đưa vào có giá trị 1000,  2000,  3000,  5000, 1000 * 101,  2000 * 101,  3000 * 101,  5000 * 101, …,  1000 * 10c,  2000 * 10c,  3000 * 10c,  5000 * 10c. Với c là số nguyên dương.

Với dữ liệu đầu vào là 2 số W ( W <= 1018) và c (c <= 15).
Và đầu ra là 2 số N và S trong đó S là số cách để trả ra số tờ tiền ít nhất N sao cho tổng bằng W. Nếu không thể trả ra W thì chương trình trả về 0.

Idea: Dễ thấy đơn vị nhỏ nhất để thanh toán là 1000. Do đó nếu W không chia hết cho 1000 thì cây ATM không thể thanh toán => Bài toán trở thành dùng các tờ 1,  2,  3,  5, 1 * 101, 2 * 101, 3 * 101, 5 * 101, …, 1 * 10c, 2 * 10c, 3 * 10c, 5 * 10c để trả ra W2 = W/1000. Ý tưởng tham lam đầu tiên đó nếu W lớn ta ưu tiên sử dụng các tờ mệnh giá lớn trước tức đầu tiên nếu W > 1 * 10c ta sẽ dùng các tờ 1 * 10c, 2 * 10c, 3 * 10c, 5 * 10c trước, sau đó tới các tờ 1 * 10c-1, 2 * 10c-1, 3 * 10c-1, 5 * 10c-1 và tới c-2, … 0.
Ví dụ
Với số tiền W = xyzt000 => W2= xyzt và c = 2 ta sẽ làm như sau

  • Dùng các tờ 100, 200, 300, 500 để trả ra xy00 đồng => dùng các tờ 1, 2, 3, 5 trả ra xy đồng (1)
  • Dùng các tờ 10, 20, 30, 50 trả ra z0 đồng => dùng các tờ 1, 2, 3 , 5 trả ra z đồng ( z ∈ [0, 9]) (2)
  • dùng các tờ 1, 2, 3 , 5 trả ra t đồng ( t ∈ [0, 9]) (3)

Giả sử mỗi trường hợp (TH) (1), (2), (3) ta cần lấy số tờ ít nhất là u và số cách là v thì
Số tờ ít nhất cần lấy ra để có tổng bằng W là  ci = 0(u)
Số cách ứng với cách lấy trên là  ci = 0(v)

Với TH (2) và (3) ( z,t ∈ [0, 9]) ta có thể lập bảng để tra cứu như sau

Số tờ Số cách
0 0 1
1 1 1
2 1 1
3 1 1
4 2 2 (dùng tờ số 3 và 1 hoặc 2 tờ số 2)
5 1 1
6 2 2 (dùng tờ số 5 và 1 hoặc 2 tờ số 3)
7 2 1
8 2 1
9 3 3 (dùng tờ số 5, 3 và 1 hoặc 5 và 2 tờ số 2 hoặc 3 tờ số 3)

 

Với TH (1) ta tiếp tục tham lam bằng cách sử dụng tờ mệnh giá cao nhất tờ số 5 để lấy ra xy/5 đồng phần dư còn lại xy%5 ta tiếp tục tra bảng trên.
Ví dụ xy = 29
Ta sử dụng 5 tờ 5 đồng để lấy được 25 đồng ( chỉ có 1 cách) sau đó còn 4 đồng ta dùng 2 tờ ( có 2 cách) Tuy nhiên ta còn 1 cách lấy nữa đó là chỉ lấy 4 tờ 5 đồng để được 20 đồng và dùng 3 tờ 3 đồng => với TH này ta cần 7 tờ và có tới tận 3 cách lấy

Tổng quát lại ta có các TH sau

  1. xy%5 = 0 => cần xy/5 tờ 5 đồng và có 1 cách lấy
  2. xy%5 = 1 => có 2 TH con
    1. xy != 1 => có thêm cách là lấy xy/5 -1 tờ 5 đồng và lấy 6 đồng nữa => cần xy/5 + 1 tờ và có 2 cách lấy
    1. xy đúng bằng 1 => cần 1 tờ 1 đồng và có 1 cách lấy
  1. xy%5 = 2 => có 2 TH con tuy nhiên với TH lấy 7 đồng cũng chỉ có 1 cách => cần xy/5 + 1 và có 1 cách
  2. xy%5 = 3 => có 2 TH con tuy nhiên với TH lấy 8 đồng cũng chỉ có 1 cách => cần xy/5 + 1 và có 1 cách
  3. xy%5 = 4 => có 2 TH con
    1. xy != 4 => có thêm cách là lấy xy/5 -1 tờ 5 đồng và lấy 6 đồng nữa => cần xy/5 + 1 tờ và có 3 cách lấy
    1. xy == 4 => cần 4 đồng => cần 2 tờ và có 2 cách lấy

Implementation

 

Bài toán cái túi

Problem: Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.
Thực chất đây là 1 bài toán tối ưu hóa tổ hợp. Bài toán cơ bản nhất là bài toán cái túi dạng 0-1 tức kẻ trộm sẽ chọn (chọn 1 đồ vật) và không chọn.

Bài toán cái túi có cách tiếp cận tối ưu là quy hoạch động. Tuy nhiên không phải bài toán NP-hard nào cũng có thể giải bằng quy hoạch động được và ban đầu bài toán cái túi cũng được tiếp cận qua tham lam.
Link tham khảo:  https://en.wikipedia.org/wiki/Continuous_knapsack_problem
Idea: Ý tưởng tham lam của bài toán đó là tính tỷ lệ giá trị/khối lượng của từng vật pi/wi (price/weight). Sau đó sort theo tỷ lệ này với thứ tự giảm dần. Chúng ta sẽ chọn những vật có pi/wi cao nhất đồng thời sức chứa của túi có thể chứa được vật đó (remain > wi) mỗi khi cho thêm vật vào túi ta cũng giảm sức chứa của túi đi.
Implementation:

 

Các bài toán liên quan tới đồ thị

Đa số các bài toán tham lam đều trong đồ thị dưới đây là một số ví dụ điển hình

Bài toán cây khung nhỏ nhất

Problem: Cho 1 đồ thị vô hướng và liên thông có trọng số G = (V, E) cây khung của đồ thị G là một cây bao trùm lên đồ thị G, cây khung nhỏ nhất của một đồ thị liên thông có trọng số là cây khung có tổng trọng số các cạnh là nhỏ nhất.
Idea: Một trong những thuật toán tìm cây khung nhỏ nhất là Kruskal (đây là 1 thuật toán tham lam). Ý tưởng của nó như sau
Thuật toán Kruskal dựa trên mô hình xây dựng cây khung nhỏ nhất bằng thuật toán hợp nhất.

  • Thuật toán không xét các cạnh với thứ tự tuỳ ý.
  • Thuật toán xét các cạnh theo thứ tự đã sắp xếp theo trọng số.

Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất – tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau:

  • Ưu tiên các cạnh có trọng số nhỏ hơn.
  • Kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó.
  • Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n – 1 cạnh sẽ là cây khung nhỏ nhất.

Như vậy thuật toán tham lam bằng cách luôn chọn những cạnh có trọng số nhỏ nhất và không tạo thành chu trình để kết nạp. Để xác định cạnh được kết nạp có tạo chu trình hay không ta có thể sử dụng cấu trúc dữ liệu disjoin set

Implementation

 

Bài toán tìm đường đi ngắn nhất

Problem: Cho đồ thị G có trọng số không âm, tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất.

Idea: Một trong những thuật toán tìm cây khung nhỏ nhất là Dijsktra (đây là 1 thuật toán tham lam). Ý tưởng của nó như sau:

  • Đặt tất cả các khoảng cách đỉnh = vô cùng ngoại trừ đỉnh xuất phát = 0.
  • Đẩy đỉnh xuất phát trong hàng đợi ưu tiên.
  • Pop đỉnh với khoảng cách từ đỉnh đó tới đỉnh xuất phát là nhỏ nhất (nếu xây dựng hàng đợi ưu tiên sử dụng min-heap thì đó chính là đỉnh đầu tiên).
  • Sử dụng đỉnh được lấy ra cập nhật khoảng cách của các đỉnh kề với nó tới đỉnh xuất phát trong trường hợp “khoảng cách đỉnh hiện tại + trọng lượng cạnh < khoảng cách đỉnh kề với nó tới đỉnh xuất phát”, sau đó đẩy các đỉnh kề vào hàng đợi.
  • Lặp lại cho đến khi hàng đợi ưu tiên trống.

Implementation

 

TopDev via Viblo