Duyệt mọi phương án để tìm lời giải

Lan cần chọn ba hộp quà trong tám hộp. Mỗi hộp có một khối lượng, và tổng cần gần 20 nhất. Lan chưa biết cách bỏ qua hộp nào mà vẫn chắc chắn tìm được đáp án. Bạn có thể thử từng bộ ba và giữ bộ tốt nhất.

Liệt kê có hệ thống giúp không bỏ sót đáp án

Duyệt toàn bộ (complete search) sinh từng phương án có thể, kiểm tra điều kiện rồi cập nhật kết quả. Để chứng minh cách làm đúng, bạn cần trả lời hai câu hỏi. Mỗi đáp án hợp lệ có được sinh ra không? Phương án nào có bị tính hai lần không?

Trước hết, hãy đếm số cách chọn hai vị trí khác nhau trong bốn vị trí. Thứ tự hai vị trí không quan trọng:

n = 4
count = 0
for i in range(n):
    for j in range(i + 1, n):
        print(i, j)
        count += 1
print('Số cặp:', count)

0 1
0 2
0 3
1 2
1 3
2 3
Số cặp: 6

Mọi cặp khác nhau đều có đúng một chỉ số nhỏ hơn. Vòng ngoài chọn chỉ số đó, còn vòng trong chọn chỉ số lớn hơn. Vì vậy mỗi cặp xuất hiện đúng một lần. Nếu dùng cả hai vòng từ 0, cặp đảo ngược bị đếm thêm và vị trí có thể ghép với chính nó.

Số cặp là n * (n - 1) // 2. Với n = 100, con số này là 4 950. Với n = 100000, nó gần năm tỉ, quá lớn để coi là một phép thử nhẹ. Thời gian là O(n^2) nếu mỗi lần kiểm tra mất O(1).

Đoạn sau đếm số cặp có tổng đúng bằng 7. Hai vị trí mang cùng giá trị vẫn là hai lựa chọn khác nhau:

a = [2, 5, 2, -1, 8]
target = 7
count = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] + a[j] == target:
            count += 1
print(count)

3

Giá trị 2 xuất hiện hai lần nên tạo hai cặp với 5. Cặp -1 và 8 cũng thỏa. Ta đếm theo vị trí, không gom các giá trị bằng nhau thành một.

Chỉ số tăng dần tạo mỗi bộ ba đúng một lần

Một bộ ba không xét thứ tự có ba chỉ số duy nhất theo thứ tự i < j < k. Ta chọn j sau i, rồi chọn k sau j. Mỗi bộ ba đều được sinh và không bộ nào được sinh lại.

Đoạn dưới nhận một dãy và tìm tổng ba phần tử gần mục tiêu nhất. Khi hai tổng cách đều mục tiêu, đề chọn tổng nhỏ hơn:

5 20
4 9 13 2 7

n, target = map(int, input().split())
a = list(map(int, input().split()))
best = None
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            total = a[i] + a[j] + a[k]
            candidate = (abs(total - target), total)
            if best is None or candidate < best:
                best = candidate
print(best[1])

20

Python so sánh hai tuple từ trái sang phải. Phần tử đầu quyết định khoảng cách; nếu khoảng cách bằng nhau, phần tử sau chọn tổng nhỏ hơn. Khởi tạo best bằng None tránh giả định đáp án luôn dương.

Với n = 80, số bộ ba là 80 * 79 * 78 // 6, tức 82 160. Kiểm tra một bộ mất thời gian hằng số, nên tổng là O(n^3). Nếu n = 2000, số bộ ba vượt một tỉ. Khi đó cần một hướng khác thay vì chỉ tăng tốc đọc dữ liệu.

Mỗi bit biểu diễn một quyết định chọn hoặc bỏ

Khi một phương án là một nhóm bất kỳ, mỗi phần tử có hai khả năng: chọn hoặc không chọn. Một tập con (subset) là nhóm thu được từ các quyết định đó. Không chọn phần tử nào tạo tập rỗng; chọn tất cả tạo tập đầy đủ.

Với ba vật A, B, C, mỗi dòng sau biểu diễn một lựa chọn. Bit ở cột A là bit thấp nhất:

Một mặt nạ bit (bitmask) là số nguyên mà mỗi bit biểu diễn một quyết định. 1 << i tạo số có bit thứ i bật. mask & (1 << i) khác 0 đúng khi bit thứ i của mask bật.

Chương trình sau liệt kê tổng của mọi tập con trong dãy ba số:

a = [3, -2, 5]
n = len(a)
for mask in range(1 << n):
    total = 0
    for i in range(n):
        if mask & (1 << i):
            total += a[i]
    print(mask, total)

0 0
1 3
2 -2
3 1
4 5
5 8
6 3
7 6

Mỗi dãy quyết định có đúng một biểu diễn bit. Vì các số từ 0 đến 2^n - 1 chứa mọi mẫu bit dài n, mọi tập con được xét đúng một lần. Mặt nạ 0 cần được xét nếu đề cho phép nhóm rỗng.

Nếu cần nhóm không rỗng có tổng bằng target, bạn chỉ cần bắt đầu từ mặt nạ 1. Đoạn sau đếm cả các nhóm khác vị trí nhưng có cùng tổng:

a = [1, -1, 0]
target = 0
count = 0
for mask in range(1, 1 << len(a)):
    total = 0
    for i, value in enumerate(a):
        if mask & (1 << i):
            total += value
    if total == target:
        count += 1
print(count)

3

Có 2^n mặt nạ và mỗi mặt nạ xét n bit. Thời gian là O(n * 2^n), bộ nhớ phụ là O(1) nếu không kể dãy vào. Với n = 20, có 1 048 576 mặt nạ và tối đa 20 971 520 lần kiểm tra bit. Phải đo trên máy chấm: số bước này không đảm bảo kịp ở mọi giới hạn thời gian.

Bạn có thể giảm thao tác lặp bằng cách xây tổng từ các tập con trước đó. Tập mới gồm một tập cũ và một phần tử mới:

a = [3, -2, 5]
sums = [0]
for value in a:
    sums += [old + value for old in sums]
print(sums)

[0, 3, -2, 1, 5, 8, 3, 6]

Trước khi xử lý một vật, danh sách chứa đúng tổng của mọi tập con các vật đã xét. Bản sao mới cộng vật đó vào từng tổng. Hai nửa lần lượt tương ứng với bỏ và chọn vật, nên không thiếu phương án. Cách này dùng O(2^n) thời gian và bộ nhớ; nó giữ cả tổng trùng vì các nhóm có thể khác vị trí.

Hoán vị cần xét thứ tự, không chỉ thành viên

Hoán vị (permutation) là một cách sắp thứ tự các phần tử. Khi xếp ba bạn A, B, C vào ba ghế, ABC và BAC là hai cách khác nhau. Có n! cách xếp n phần tử phân biệt.

itertools.permutations sinh từng thứ tự mà không cần viết các vòng lặp theo số phần tử. Đoạn sau tìm thứ tự có tổng chênh lệch giữa hai số kề nhau nhỏ nhất:

from itertools import permutations

a = [1, 4, 7]
best = None
for order in permutations(a):
    cost = sum(abs(order[i] - order[i + 1])
               for i in range(len(order) - 1))
    if best is None or cost < best:
        best = cost
print(best)

6

Mỗi hoán vị đều được kiểm tra, vì thế giá trị nhỏ nhất đã lưu là đáp án. Tính chi phí từ đầu mất O(n) cho mỗi hoán vị. Tổng thời gian là O(n * n!), ngoài bộ nhớ của dữ liệu đang xét.

Với n = 8, có 40 320 thứ tự. Với n = 10, đã có 3 628 800 thứ tự. Các con số này chưa tính chi phí kiểm tra từng thứ tự. Thứ tự tăng trưởng nhanh khiến việc đo thời gian trên dữ liệu lớn nhất đặc biệt cần thiết.

Nếu danh sách có giá trị trùng, permutations vẫn phân biệt vị trí đầu vào. Hai kết quả có cùng giá trị có thể xuất hiện nhiều lần. Muốn đếm thứ tự giá trị phân biệt, cần xử lý trùng theo yêu cầu cụ thể của đề.

Nhánh lựa chọn chỉ được bỏ khi chắc chắn vô ích

Quay lui (backtracking) xây một phương án từng bước. Với mỗi lựa chọn, chương trình đi sâu rồi hoàn tác để thử lựa chọn tiếp theo. Hình sau cho thấy hai lựa chọn đầu tiên của ba vật:

Để minh họa quản lý trạng thái, chương trình liệt kê các nhóm hai vị trí từ ba vật:

items = ['A', 'B', 'C']
chosen = []

def visit(start):
    if len(chosen) == 2:
        print(''.join(chosen))
        return
    for i in range(start, len(items)):
        chosen.append(items[i])
        visit(i + 1)
        chosen.pop()

visit(0)

AB
AC
BC

start tăng sau mỗi lần chọn, nên chỉ số đã chọn luôn tăng. Bất kỳ cặp nào cũng có đúng một thứ tự chỉ số tăng. pop() đưa danh sách về trạng thái trước nhánh, để nhánh sau không mang lựa chọn cũ.

Một nhánh có thể được cắt tỉa (pruning) khi ta chứng minh mọi phần mở rộng đều không hợp lệ hoặc không tốt hơn đáp án hiện tại. Ví dụ, nếu mọi khối lượng đều không âm, một tổng đã vượt giới hạn không thể giảm khi chọn thêm. Nếu có số âm, kết luận đó không còn đúng.

values = [8, -5]
limit = 5
print('Sau vật đầu:', values[0])
print('Sau cả hai vật:', sum(values))
print('Nhóm hợp lệ:', sum(values) <= limit)

Sau vật đầu: 8
Sau cả hai vật: 3
Nhóm hợp lệ: True

Với dữ liệu này, cắt nhánh ngay sau 8 sẽ bỏ mất nhóm có tổng 3. Cắt tỉa có thể giảm số nhánh thực tế, nhưng trong trường hợp xấu nhất vẫn phải tính theo toàn bộ không gian tìm kiếm.

Ước lượng chi phí trước khi chọn cách duyệt

Số vòng lặp không tự cho biết chương trình nhanh hay chậm. Bạn cần nhân số phương án với chi phí xử lý mỗi phương án. Sau đó hãy xét thêm số bộ dữ liệu và giới hạn thời gian thực tế.

Chương trình sau tự tính số phương án của ba kiểu duyệt với vài kích thước. Mỗi dòng gồm kích thước, số cặp, số tập con và số hoán vị:

from math import factorial

for n in [4, 8, 10, 20]:
    pairs = n * (n - 1) // 2
    subsets = 1 << n
    orders = factorial(n)
    print(n, pairs, subsets, orders)

4 6 16 24
8 28 256 40320
10 45 1024 3628800
20 190 1048576 2432902008176640000

Cùng tăng n, số hoán vị tăng nhanh hơn rất nhiều so với số cặp. Bảng này chỉ đếm phương án, không đo thời gian chạy. Với mỗi thứ tự, nếu bạn tính lại tổng qua n phần tử, chi phí còn phải nhân thêm khoảng n.

Giả sử một bài yêu cầu đếm nhóm có tổng đúng, với n = 20. Duyệt mọi mặt nạ là 1 048 576 lượt. Nếu mỗi lượt quét cả 20 vị trí, tối đa có hơn 20 triệu lần xét bit. Một chương trình khác giữ danh sách tổng cần thêm bộ nhớ cho hơn một triệu số. Hai cách đúng nhưng có thể khác nhiều về thời gian và bộ nhớ.

Giới hạn đề gồm nhiều bộ dữ liệu cũng ảnh hưởng tổng chi phí. Nếu mỗi bộ có 20 phần tử, hai mươi bộ không còn cùng chi phí với một bộ. Hãy đọc ràng buộc tổng, số bộ và bộ nhớ trước khi kết luận. Sau đó đo trên dữ liệu lớn nhất hợp lệ trong môi trường tương tự máy chấm.

Để đếm số vòng lặp thực tế, bạn có thể thêm một biến đếm trong bản thử cục bộ. Đoạn sau so sánh số lượt duyệt ba chỉ số tự do với số bộ ba tăng dần:

n = 8
all_visits = 0
ordered_visits = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            all_visits += 1
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            ordered_visits += 1
print('Mọi bộ chỉ số:', all_visits)
print('Bộ ba tăng dần:', ordered_visits)

Mọi bộ chỉ số: 512
Bộ ba tăng dần: 56

Cách thứ nhất còn xét các bộ lặp chỉ số và các thứ tự đảo. Nếu chỉ cần chọn ba vị trí không xét thứ tự, các lượt đó không đại diện cho ba lựa chọn mới. Cách thứ hai tạo đúng 56 bộ, phù hợp với 8 * 7 * 6 // 6.

Định nghĩa đáp án trước khi xử lý trường hợp biên

Trước khi viết vòng lặp, hãy làm rõ đề đếm theo giá trị hay theo vị trí. Với hai thẻ cùng ghi 5, chọn thẻ thứ nhất và chọn thẻ thứ hai tạo hai nhóm vị trí khác nhau. Nếu đề chỉ hỏi những tổng khác nhau, cả hai nhóm lại cùng đóng góp một giá trị tổng.

Chương trình dưới đây hiển thị cả hai cách đếm cho cùng một dữ liệu. Bạn có thể đối chiếu để chọn đúng cách theo đề:

from itertools import combinations

a = [5, 5, 2]
pair_sums = [sum(pair) for pair in combinations(a, 2)]
print('Số cặp vị trí:', len(pair_sums))
print('Số tổng khác nhau:', len(set(pair_sums)))

Số cặp vị trí: 3
Số tổng khác nhau: 2

Có ba cặp vị trí, nhưng chỉ hai giá trị tổng. Đưa các tổng vào set là hợp lý khi cần số tổng khác nhau. Cách đó sai nếu cần số nhóm, vì nó gộp hai nhóm có cùng tổng.

Các bài tối ưu cũng cần quy định khi có nhiều phương án tốt như nhau. Bài chọn ba hộp quà ở trên ưu tiên tổng nhỏ hơn khi khoảng cách bằng nhau. Một đề khác có thể yêu cầu in chỉ số nhỏ nhất hoặc bất kỳ đáp án nào. Quy tắc cập nhật phải làm đúng yêu cầu đó, kể cả khi thứ tự sinh phương án thay đổi.

Cuối cùng, hãy thử trường hợp nhỏ nhất trước. Với bài chọn ba vị trí, n = 3 chỉ có một bộ. Với tập con, n = 1 giúp kiểm tra việc cho phép hoặc loại tập rỗng. Các số bằng nhau, toàn số âm và trường hợp không có đáp án cũng thường làm lộ lỗi khởi tạo.

So sánh với lời giải chậm giúp tìm phản ví dụ

Một chương trình duyệt toàn bộ dễ viết có thể làm đáp án tham chiếu cho dữ liệu nhỏ. Bạn sinh nhiều dữ liệu, chạy cả lời giải tham chiếu và lời giải cần kiểm tra, rồi so sánh kết quả. Phải chắc rằng hai chương trình giải cùng một đề và xử lý cùng trường hợp biên.

Ví dụ này so sánh cách duyệt cặp với cách lấy hai số lớn nhất. Dữ liệu thử có ít nhất hai số:

from random import Random

def slow(a):
    return max(a[i] + a[j] for i in range(len(a))
               for j in range(i + 1, len(a)))

def fast(a):
    ordered = sorted(a)
    return ordered[-1] + ordered[-2]

rng = Random(42)
for _ in range(200):
    a = [rng.randint(-9, 9) for _ in range(rng.randint(2, 8))]
    if slow(a) != fast(a):
        print('Khác nhau:', a, slow(a), fast(a))
        break
else:
    print('200 phép thử khớp')

200 phép thử khớp

Hạt giống cố định giúp lặp lại cùng chuỗi dữ liệu khi sửa lỗi. Nếu thấy kết quả khác, lưu dãy gây lỗi rồi rút ngắn nó để hiểu nguyên nhân. Các phép thử ngẫu nhiên có thể tìm lỗi, nhưng không chứng minh lời giải đúng với mọi đầu vào.

Lỗi thường gặp

Tóm tắt

• Xác định rõ phương án, điều kiện hợp lệ và cách cập nhật đáp án.
• Chỉ số tăng dần sinh cặp hoặc bộ ba không xét thứ tự đúng một lần.
• Duyệt mặt nạ xét mọi tập con; chú ý tập rỗng và các vị trí có giá trị trùng.
• Hoán vị xét thứ tự; ước lượng cả số thứ tự lẫn chi phí kiểm tra.
• Đối chiếu với lời giải chậm trên dữ liệu nhỏ giúp phát hiện sai sót.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về itertools giải thích cách sinh hoán vị và tổ hợp.
• Tài liệu Python về phép toán bit mô tả dịch bit và phép AND.