Chọn tham lam và chứng minh lựa chọn an toàn

Lan cần xếp bốn buổi sinh hoạt vào một phòng. Các buổi lần lượt diễn ra từ 1 đến 4, 2 đến 3, 3 đến 5 và 5 đến 7 giờ. Hai buổi được phép chạm nhau ở đầu mút. Chọn buổi đầu tiên theo giờ bắt đầu chỉ để lại chỗ cho hai buổi. Lan muốn tìm cách chọn được nhiều buổi hơn và giải thích vì sao không thể làm tốt hơn.

Một lựa chọn trước mắt cần giữ được cơ hội tối ưu

Thuật toán tham lam (greedy algorithm) xây dựng lời giải qua nhiều bước. Ở mỗi bước, nó chọn theo một quy tắc cục bộ và không quay lại sửa lựa chọn đó. Một quy tắc chỉ đáng tin khi có lý do chứng minh rằng vẫn tồn tại lời giải tối ưu chứa lựa chọn vừa thực hiện.

Với lịch của Lan, chọn buổi bắt đầu sớm nhất là một quy tắc cục bộ. Buổi 1–4 bắt đầu trước các buổi khác, nhưng chiếm phòng lúc 2–3. Nếu chọn buổi 2–3 rồi 3–5, Lan đã xếp được hai buổi trước giờ 5. Buổi 5–7 còn nối tiếp được.

Đoạn mã sau đếm số buổi theo quy tắc bắt đầu sớm nhất. Mỗi cặp là thời điểm bắt đầu và kết thúc:

activities = [(1, 4), (2, 3), (3, 5), (5, 7)]
last = None
chosen = []
for start, end in sorted(activities):
    if last is None or start >= last:
        chosen.append((start, end))
        last = end
print(chosen)
print(len(chosen))

[(1, 4), (5, 7)]
2

Kết quả là hai buổi: 1–4 và 5–7. Danh sách 2–3, 3–5, 5–7 có ba buổi hợp lệ, nên quy tắc đầu tiên thất bại. Đây là phản ví dụ (counterexample): một đầu vào hợp lệ đủ bác bỏ phát biểu rằng quy tắc đúng với mọi đầu vào.

Sơ đồ sau mô tả hai đường đi. Việc xét một đầu vào không chứng minh được thuật toán đúng với mọi đầu vào:

Một thuật toán có thể đúng cho hàng nghìn bộ thử nhưng sai ở bộ tiếp theo. Bằng chứng cần dựa vào cấu trúc của mọi lời giải, không dựa vào số lượng bộ thử đã qua. Khi tìm thấy phản ví dụ, hãy kiểm tra lại quy tắc hoặc điều kiện đề bài trước khi tối ưu mã.

Chọn buổi kết thúc sớm nhất để dành thời gian cho phần còn lại

Mỗi hoạt động có khoảng thời gian nửa mở [start, end), với start < end. Hai hoạt động liên tiếp được dùng chung phòng khi buổi sau có start >= end của buổi trước. Vì vậy thời điểm 3 có thể là điểm kết thúc của một buổi và bắt đầu của buổi kế tiếp.

Sắp các hoạt động theo end tăng dần. Chọn hoạt động đầu tiên, sau đó duyệt theo thứ tự ấy. Mỗi lần gặp hoạt động bắt đầu không sớm hơn thời điểm kết thúc đã chọn gần nhất, ta nhận nó.

Hình sau cho thấy quá trình xét lịch của Lan. A, B, C, D lần lượt là 1–4, 2–3, 3–5 và 5–7:

Sau khi chọn B, buổi A bị bỏ vì bắt đầu lúc 1, trước khi B kết thúc lúc 3. Buổi C bắt đầu đúng lúc 3 nên được chọn. Buổi D bắt đầu lúc 5, đúng lúc C kết thúc, nên cũng được chọn.

Chương trình dưới đây đọc dữ liệu thay vì giả định thời điểm đều dương. last = None biểu thị chưa chọn buổi nào:

4
1 4
2 3
3 5
5 7

n = int(input())
activities = []
for _ in range(n):
    start, end = map(int, input().split())
    activities.append((start, end))
activities.sort(key=lambda activity: activity[1])
last = None
chosen = []
for start, end in activities:
    if last is None or start >= last:
        chosen.append((start, end))
        last = end
print(len(chosen))
print(chosen)

3
[(2, 3), (3, 5), (5, 7)]

Giá trị None tránh sai khi mọi thời điểm đều âm. Nếu hai buổi cùng kết thúc, chọn buổi nào trước cũng để cùng một thời điểm bắt đầu cho phần còn lại. Các buổi có thời lượng dương cùng kết thúc không thể cùng được chọn.

Vì sao phép đổi chỗ giữ số buổi tối ưu?

Gọi G là buổi có giờ kết thúc sớm nhất. Xét một lịch tối ưu bất kỳ và gọi buổi đầu tiên của lịch ấy là O. Nếu G chưa nằm đầu lịch, thay O bằng G. Theo cách chọn, G kết thúc không muộn hơn O.

Mọi buổi phía sau O đều bắt đầu từ lúc O kết thúc trở đi. Chúng cũng bắt đầu sau khi G kết thúc, nên lịch sau khi thay vẫn hợp lệ. Số buổi không đổi, vì ta thay đúng một buổi. Vậy có ít nhất một lịch tối ưu bắt đầu bằng G.

Sau khi chọn G, bài toán còn lại gồm các buổi bắt đầu từ lúc G kết thúc trở đi. Lập luận tương tự áp dụng tiếp trên tập còn lại. Cuối cùng lịch của thuật toán có số buổi bằng lịch tối ưu. Đây là lập luận đổi chỗ (exchange argument): biến một nghiệm tối ưu thành nghiệm chứa lựa chọn của ta mà không làm nghiệm kém đi.

Với lịch của Lan, một lịch tối ưu có thể bắt đầu bằng 2–3. Giả sử lịch tối ưu khác bắt đầu bằng 1–4, đổi buổi đầu sang 2–3 vẫn giữ được mọi buổi sau 4. Thực tế lịch ba buổi không bắt đầu bằng 1–4, nhưng phép đổi chứng minh an toàn kể cả trước khi biết lịch tối ưu cụ thể.

Sắp xếp mất O(n log n), duyệt mất O(n), và lưu danh sách mất O(n) bộ nhớ. Với n = 10 000, cỡ n log₂ n khoảng 133 000, thay vì xét tới 2^10000 tập con. Con số này là ước lượng tăng trưởng, không phải thời gian chạy chính xác.

Mua giá thấp trước khi mục tiêu là số lượng

Một thư viện có ngân sách 11 và giá các cuốn sách là 8, 3, 2, 5. Mỗi cuốn mua tối đa một lần và mọi cuốn đều đóng góp một đơn vị vào số lượng. Chọn giá thấp nhất trước giữ lại nhiều tiền nhất cho các cuốn còn lại.

prices = [8, 3, 2, 5]
budget = 11
total = 0
chosen = []
for price in sorted(prices):
    if total + price > budget:
        break
    total += price
    chosen.append(price)
print(chosen, total)

[2, 3, 5] 10

Chương trình mua ba cuốn giá 2, 3 và 5, tổng là 10. Cuốn còn lại có giá 8 nên không thể mua cả bốn. Với mọi số lượng k, tổng của k giá nhỏ nhất không lớn hơn tổng của bất kỳ k giá nào khác. Vì vậy, nếu k cuốn rẻ nhất vượt ngân sách thì không có cách mua k cuốn.

Lập luận này phụ thuộc mục tiêu chỉ là số cuốn và giá không âm. Nếu mỗi cuốn có giá trị sử dụng khác nhau và mục tiêu là tổng giá trị, thay một cuốn đắt bằng cuốn rẻ có thể làm giảm giá trị. Không được áp dụng nguyên quy tắc khi đề thay đổi mục tiêu.

Nếu ngân sách vừa bằng tổng, dấu > cho phép mua tiếp; dùng >= sẽ bỏ nhầm món vừa đủ tiền. Giá bằng 0 vẫn hợp lệ và mỗi món vẫn chỉ được chọn một lần. sort mất O(n log n); sau đó mỗi giá được xét tối đa một lần.

Ghép nhu cầu nhỏ nhất với tài nguyên nhỏ nhất có thể dùng

Một câu lạc bộ có ba bạn cần bánh kích thước ít nhất 2, 4, 5. Bốn bánh có kích thước 1, 3, 4, 7. Mỗi bánh chỉ dành cho một bạn; mỗi bạn nhận nhiều nhất một bánh. Mục tiêu là số bạn hài lòng lớn nhất.

Sắp nhu cầu và kích thước theo thứ tự tăng. Xét bạn còn lại có nhu cầu nhỏ nhất và chiếc bánh nhỏ nhất chưa xét. Nếu bánh quá nhỏ, nó cũng không đủ cho bất kỳ bạn nào còn lại. Nếu bánh đủ, ghép hai đối tượng rồi chuyển cả hai con trỏ.

Đoạn mã sau in các cặp (nhu cầu, bánh) và số bạn được phục vụ:

needs = sorted([2, 4, 5])
sizes = sorted([1, 3, 4, 7])
i = j = 0
pairs = []
while i < len(needs) and j < len(sizes):
    if sizes[j] >= needs[i]:
        pairs.append((needs[i], sizes[j]))
        i += 1
    j += 1
print(pairs)
print(len(pairs))

[(2, 3), (4, 4), (5, 7)]
3

Ta ghép 2 với 3, 4 với 4 và 5 với 7. Bánh bằng đúng nhu cầu được chấp nhận, nên dùng >=. Nếu bánh nhỏ nhất không đủ cho bạn có nhu cầu thấp nhất, không bạn còn lại nào dùng được bánh ấy. Bỏ nó không làm giảm số cặp tối ưu.

Nếu bánh nhỏ nhất đủ, xét một cách ghép tối ưu. Khi cả bạn và bánh đó đều đang được ghép với đối tượng khác, đổi hai cặp để họ ghép với nhau. Bánh trước đó của bạn này đủ lớn cho bạn còn lại vì nó không nhỏ hơn bánh nhỏ nhất. Các trường hợp một trong hai chưa được ghép cũng cho phép thay một cặp mà không giảm số cặp. Do đó có nghiệm tối ưu chứa cặp vừa chọn.

Mỗi con trỏ chỉ tăng và không vượt độ dài danh sách. Sau sắp xếp, vòng ghép mất O(n + m) với n bạn và m bánh. Tổng thời gian là O(n log n + m log m), bộ nhớ lưu dữ liệu là O(n + m).

Giữ các công việc ngắn khi thời gian vượt hạn

Giả sử một người phải làm việc liên tục từ thời điểm 0, không làm hai việc cùng lúc. Mỗi việc có thời lượng dương t và hạn hoàn thành d. Ta muốn chọn số việc lớn nhất sao cho từng việc được chọn hoàn thành không muộn hơn hạn của nó.

Đầu tiên, xét việc theo hạn tăng dần. Đưa thời lượng của việc đang xét vào tập chọn và cộng vào tổng. Nếu tổng vượt hạn hiện tại, bỏ việc có thời lượng lớn nhất trong tập. Việc bị bỏ có thể là việc vừa xét hoặc một việc được chọn trước đó.

Ví dụ có ba việc (thời lượng, hạn) là (4, 4), (2, 5) và (2, 6). Giữ việc đầu và thêm việc thứ hai tạo tổng 6, vượt hạn 5. Bỏ việc dài nhất là 4, sau đó thêm việc cuối. Hai việc dài 2 có thể hoàn thành ở thời điểm 2 và 4.

import heapq

jobs = [(4, 4), (2, 5), (2, 6)]
chosen = []
total = 0
for duration, deadline in sorted(jobs, key=lambda job: job[1]):
    total += duration
    heapq.heappush(chosen, -duration)
    if total > deadline:
        total += heapq.heappop(chosen)
    print(deadline, total, sorted(-x for x in chosen))
print(len(chosen))

4 4 [4]
5 2 [2]
6 4 [2, 2]
2

heapq lấy số nhỏ nhất, nên lưu -duration để lấy thời lượng lớn nhất. Khi bỏ, giá trị lấy ra là số âm: cộng số đó vào total tương đương trừ thời lượng. Không được cộng lại thời lượng dương, vì tổng sẽ tăng thay vì giảm.

Tại mỗi hạn, tập đang giữ là một tập khả thi có số việc lớn nhất trong các việc đã xét. Trong các tập khả thi đạt số đó, tập được giữ có tổng thời lượng nhỏ nhất. Khi thêm một việc làm vượt hạn, mọi lịch giữ toàn bộ tập mới đều không hợp lệ. Phải bỏ ít nhất một việc; bỏ việc dài nhất cho tổng còn lại nhỏ nhất.

Tập cũ đã khả thi, nên sau khi bỏ việc dài nhất, tổng không lớn hơn tổng cũ. Các hạn trước vẫn được tôn trọng: nếu bỏ việc mới, lịch cũ không đổi; nếu bỏ việc cũ, các việc cũ còn lại chỉ kết thúc sớm hơn. Việc mới đứng cuối trong thứ tự hạn, và tổng mới không vượt hạn của nó. Lập luận này tiếp tục sau từng việc và bảo đảm đáp án cuối cùng tối ưu.

Sắp xếp và mỗi thao tác đẩy hoặc lấy khỏi heap đều cần tối đa O(log n) cho mỗi việc. Tổng thời gian là O(n log n), bộ nhớ O(n). Với 10 000 việc, khoảng n log₂ n là 133 000; máy vẫn cần thêm thời gian đọc dữ liệu và thực hiện các thao tác Python.

Đoạn sau kiểm tra ranh giới: việc dài hơn hạn của chính nó sẽ bị bỏ, còn việc hoàn thành đúng hạn được giữ:

import heapq

jobs = [(5, 3), (3, 3)]
heap = []
total = 0
for duration, deadline in sorted(jobs, key=lambda job: job[1]):
    total += duration
    heapq.heappush(heap, -duration)
    if total > deadline:
        total += heapq.heappop(heap)
print(len(heap), total)

1 3

Sau việc đầu, tổng 5 vượt 3 nên việc ấy bị bỏ. Việc thứ hai có tổng 3, bằng hạn 3, nên được giữ. Hai hạn bằng nhau không đòi hỏi một thứ tự phụ riêng cho số lượng tối đa.

Duyệt mọi phương án nhỏ để tìm phản ví dụ

Bài 3 đã giới thiệu duyệt tập con. Ở đây, dùng nó làm thước so sánh cho bài chọn hoạt động: với từng tập con, sắp theo giờ kết thúc và kiểm tra các buổi liên tiếp. Lấy kích thước lớn nhất trong các tập hợp lệ.

Mã dưới đây duyệt mọi lịch con của đúng bốn buổi trong tình huống mở đầu. Nó in kết quả đúng và kết quả của quy tắc bắt đầu sớm nhất:

from itertools import combinations

items = [(1, 4), (2, 3), (3, 5), (5, 7)]
best = 0
for size in range(len(items) + 1):
    for subset in combinations(items, size):
        ordered = sorted(subset, key=lambda item: item[1])
        valid = all(ordered[i - 1][1] <= ordered[i][0]
                    for i in range(1, len(ordered)))
        if valid:
            best = max(best, size)
last = None
early = 0
for start, end in sorted(items):
    if last is None or start >= last:
        early += 1
        last = end
print(best, early)

3 2

Thước đo tìm được ba buổi, trong khi quy tắc kia chỉ tìm được hai. Một bộ kiểm nhỏ khác nên gồm lịch rỗng, một buổi, các buổi trùng hoàn toàn, đầu mút chạm nhau và thời điểm âm. Với đầu vào đã cố định, kiểm tra tất cả tập con xác nhận kết quả của riêng đầu vào ấy.

Ta có thể tạo nhiều lịch nhỏ rồi so thuật toán đúng dự kiến với thước đo. Đoạn sau thử mọi tập ba buổi lấy từ năm khoảng đã chọn. assert dừng chương trình nếu hai cách không đồng ý:

from itertools import combinations

pool = [(0, 1), (0, 3), (1, 2), (1, 4), (2, 4)]
checked = 0
for items in combinations(pool, 3):
    ordered = sorted(items, key=lambda x: x[1])
    last = None
    greedy = 0
    for start, end in ordered:
        if last is None or start >= last:
            greedy += 1
            last = end
    best = 0
    for size in range(4):
        for subset in combinations(items, size):
            seq = sorted(subset, key=lambda x: x[1])
            if all(seq[i - 1][1] <= seq[i][0]
                   for i in range(1, len(seq))):
                best = max(best, size)
    assert greedy == best
    checked += 1
print(checked)

10

Có 10 tập ba phần tử được kiểm tra. Thước đo xét 2^n tập con nên chỉ phù hợp khi n nhỏ; với 20 buổi đã có hơn một triệu tập. Việc so sánh giúp tìm lỗi mã hoặc phản ví dụ, nhưng lập luận đổi chỗ mới bảo đảm kết quả cho mọi kích thước hợp lệ.

Đổi tiền cho thấy một quy tắc hợp lý vẫn có thể sai

Một máy có vô hạn đồng mệnh giá 1, 3 và 4. Đổi số tiền 6 bằng ít đồng nhất. Quy tắc lấy đồng lớn nhất không vượt số tiền còn lại sẽ chọn 4, rồi 1, rồi 1. Hai đồng 3 cộng lại cũng bằng 6 và ít đồng hơn.

Chương trình sau thực hiện quy tắc lấy đồng lớn nhất, rồi đếm cách dùng hai đồng 3:

remaining = 6
coins = []
for value in [4, 3, 1]:
    while remaining >= value:
        remaining -= value
        coins.append(value)
print(coins, len(coins))
print([3, 3], len([3, 3]))

[4, 1, 1] 3
[3, 3] 2

Không thể đổi 6 bằng một đồng vì không có mệnh giá 6. Hai đồng 3 do đó là tối ưu cho riêng ví dụ này. Phản ví dụ không khẳng định quy tắc lấy đồng lớn nhất sai với mọi hệ tiền; nó chỉ bác bỏ việc dùng quy tắc ấy cho mọi hệ tiền tùy ý.

Khi không chứng minh được lựa chọn cục bộ an toàn, hãy cân nhắc một phương pháp lưu và so sánh nhiều trạng thái. Đừng kết luận rằng bài toán cần một kỹ thuật khác chỉ vì một quy tắc tham lam cụ thể thất bại: có thể còn quy tắc khác đúng.

Lỗi thường gặp

Tóm tắt

• Tham lam cần quy tắc lựa chọn và lập luận giữ được nghiệm tối ưu.
• Chọn hoạt động kết thúc sớm nhất để phần còn lại có nhiều thời gian nhất.
• Giá thấp trước và ghép nhu cầu thấp trước chỉ đúng trong các điều kiện đã nêu.
• Với công việc theo hạn, bỏ thời lượng lớn nhất khi tổng vượt hạn.
• Duyệt toàn bộ trên dữ liệu nhỏ giúp tìm phản ví dụ, không thay thế chứng minh.

Kiểm tra nhanh

Đọc thêm

• Python: hướng dẫn sắp xếp với key.
• Python: hàng đợi ưu tiên với heapq.
• MIT OpenCourseWare 6.046J: Design and Analysis of Algorithms, có bài giảng về thuật toán tham lam.