Đang tải trang
Trong bài này
Minh cần chọn các kiện hàng nặng 6, 4, 3 và 2 kg cho một xe chở tối đa 10 kg. Có 16 cách chọn, nhưng xe đầy ngay khi chọn hai kiện đầu. Minh muốn biết những cách còn lại có cần kiểm tra hết không.
Một nhánh chỉ cần giữ lại khi còn cơ hội cải thiện nghiệm
Nhánh và cận (branch and bound) tìm nghiệm tối ưu bằng cách chia các lựa chọn thành nhánh và loại những nhánh không thể cải thiện kết quả. Nghiệm tốt nhất hiện có (incumbent) phải là một nghiệm hợp lệ đã biết, không phải một dự đoán. Ta lưu giá trị của nó trong best.
Cận trên (upper bound) của nhánh tối đa hóa không nhỏ hơn giá trị tốt nhất thật sự có thể đạt trong nhánh. Nếu cận trên không vượt best, mọi nghiệm ở đó đều không tốt hơn nghiệm đang có. Vì vậy có thể bỏ nhánh khi chỉ cần giá trị tối ưu.
Ngược lại, cận dưới (lower bound) của nhánh tối thiểu hóa không lớn hơn chi phí tốt nhất có thể đạt trong nhánh. Nếu cận dưới lớn hơn hoặc bằng best, nhánh không tạo ra chi phí nhỏ hơn. Hai hướng bất đẳng thức này dựa trên chứng minh, không dựa vào việc một nhánh trông có vẻ xấu.
Kiểm traBỏ trạng thái đã vi phạm ràng buộcƯớc lượngTính cận lạc quan của các lựa chọn còn lạiSo sánhBỏ nhánh không thể cải thiện nghiệm hợp lệPhân nhánhThử lựa chọn và hoàn tác trước lựa chọn tiếp theo
Khi cần liệt kê mọi nghiệm tối ưu, dấu bằng có ý nghĩa khác. Một nhánh có cận bằng best vẫn có thể chứa một nghiệm khác cùng giá trị. Khi ấy chỉ cắt nếu cận kém hẳn best, và cần lưu các nghiệm bằng nhau.
Python
best = 10
for upper in [8, 10, 12]:
print(upper, upper <= best)Kết quả
8 True 10 True 12 False
Tổng hậu tố cho một cận trên an toàn khi chọn kiện hàng
Giả sử a chỉ chứa số không âm và tập rỗng được phép chọn. Ở trạng thái i, các kiện trước i đã được quyết định; total là tổng đã chọn. Đặt suffix[i] là tổng các kiện từ i đến cuối.
Mọi cách hoàn thành nhánh chỉ lấy được một phần các kiện còn lại. Vì chúng không âm, tổng cuối không thể lớn hơn total + suffix[i]. Giới hạn xe cũng cho một cận trên là S. Do đó min(S, total + suffix[i]) là cận trên an toàn, dù chưa chắc đạt được.
| Bước | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Kiện | 6 | 4 | 3i | 2 |
Ở hình này, total = 4 và suffix[2] = 3 + 2 = 5. Nếu đã biết best = 10, nhánh chỉ đạt tối đa 9 nên có thể cắt. Hình gạch kiện 6 vì nhánh này đã quyết định bỏ kiện đó.
Python
a = [6, 4, 3, 2]
suffix = [0] * (len(a) + 1)
for i in range(len(a) - 1, -1, -1):
suffix[i] = suffix[i + 1] + a[i]
print(suffix)Kết quả
[15, 9, 5, 2, 0]
Ta cũng bỏ trạng thái total > S: các kiện còn lại không âm nên thêm hay bỏ chúng đều không thể đưa tổng trở lại mức cho phép. Điều này không đúng nếu các kiện có thể mang giá trị âm.
Python
def best_subset_sum(a, limit):
a = sorted(a, reverse=True)
n = len(a)
suffix = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix[i] = suffix[i + 1] + a[i]
best = 0
def visit(i, total):
nonlocal best
if total > limit:
return
best = max(best, total)
if i == n or min(limit, total + suffix[i]) <= best:
return
visit(i + 1, total + a[i])
visit(i + 1, total)
visit(0, 0)
return best
print(best_subset_sum([6, 4, 3, 2], 10))
print(best_subset_sum([8, 9], 3))Kết quả
10 0
Mỗi trạng thái hợp lệ tự biểu diễn một tập con: bỏ hết kiện chưa xét sẽ tạo cùng tổng. Vì vậy cập nhật best ngay tại trạng thái này là an toàn. Khởi tạo best = 0 cũng hợp lệ vì tập rỗng có tổng 0 và S không âm.
Chương trình thử lấy kiện lớn trước để có thể tìm nghiệm tốt sớm. Sắp xếp không làm mất tập con vì chỉ đổi thứ tự duyệt. Nếu cần in chỉ số ban đầu, hãy lưu chỉ số đi kèm từng kiện.
Tại mỗi nút còn xét, hai nhánh lấy và bỏ bao phủ mọi cách chọn. Những nhánh bị cắt do quá tải không hợp lệ; những nhánh bị cắt bởi cận không cải thiện best. Do đó kết quả cuối là tối ưu.
Trong trường hợp xấu, có không quá 2^(n+1) - 1 nút của cây nhị phân đầy đủ. Tiền xử lý mất O(n log n) do sắp xếp và O(n) để tính hậu tố. Mỗi nút tính cận trong O(1); ngăn đệ quy và hậu tố dùng O(n) bộ nhớ.
Với n = 20, cây đầy đủ có thể có hơn hai triệu nút. Cận thường giảm con số thực tế, nhưng không bảo đảm giảm đủ trong mọi dữ liệu. Nếu n lớn, cần xét giới hạn đề và các thuật toán khác như quy hoạch động khi sức chứa nhỏ.
Đếm số nút giúp thấy tác dụng mà không bảo đảm tốc độ
Ví dụ sau chạy hai lần trên cùng dữ liệu. Cả hai đều bỏ trạng thái quá tải; chỉ lượt thứ hai dùng thêm cận hậu tố. Một nút được tính khi hàm được gọi, kể cả nút bị cắt ngay sau đó.
Python
def search(a, limit, use_bound):
suffix = [0] * (len(a) + 1)
for i in range(len(a) - 1, -1, -1):
suffix[i] = suffix[i + 1] + a[i]
best, visits = 0, 0
def dfs(i, total):
nonlocal best, visits
visits += 1
if total > limit:
return
best = max(best, total)
if i == len(a):
return
if use_bound and min(limit, total + suffix[i]) <= best:
return
dfs(i + 1, total + a[i])
dfs(i + 1, total)
dfs(0, 0)
return best, visits
items = [6, 4, 3, 2]
print(search(items, 10, False))
print(search(items, 10, True))Kết quả
(10, 29) (10, 5)
Hai kết quả tối ưu phải giống nhau. Số lần gọi đo trên ví dụ này không chứng minh một tỉ lệ tăng tốc cho dữ liệu khác. Cận lỏng hoặc nghiệm tốt xuất hiện muộn có thể khiến thuật toán vẫn gần vét cạn.
Python
best = 8
actual_max = 9
for upper in [9, 15, 8]:
print(upper, upper >= actual_max, upper <= best)Kết quả
9 True False 15 True False 8 False True
Ở đây 9 và 15 đều là cận trên an toàn cho nhánh có giá trị tốt nhất là 9. Giá trị 8 không an toàn: nó có thể khiến ta bỏ nhánh chứa kết quả tốt hơn best.
Phân công dùng tổng chi phí nhỏ nhất cho từng người làm cận dưới
Giả sử có ba người, ba việc và bảng chi phí dưới đây. Mỗi người làm một việc, mỗi việc giao đúng một lần. Ta xử lý lần lượt từng người và đánh dấu việc đã giao.
3 dòng
| Người | Việc 1 | Việc 2 | Việc 3 |
|---|---|---|---|
| 1 | 9 | 2 | 7 |
| 2 | 6 | 4 | 3 |
| 3 | 5 | 8 | 1 |
Với một trạng thái, hãy cho mỗi người còn lại chọn việc rẻ nhất trong những việc chưa giao. Các lựa chọn giả định này có thể trùng việc. Chúng không nhất thiết tạo thành phân công hợp lệ, nhưng mỗi chi phí riêng không lớn hơn chi phí người ấy phải trả trong bất kỳ cách hoàn thành hợp lệ nào.
Cộng các giá trị nhỏ nhất ấy với chi phí hiện tại cho một cận dưới an toàn. Cho phép trùng việc làm bài toán dễ hơn nên có thể khiến cận quá lạc quan, không làm nó quá cao. Nếu cận đã không nhỏ hơn best, nhánh không cải thiện được đáp án.
Python
cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
used = [True, False, False]
current = 9
bound = current + sum(min(cost[i][j] for j in range(3) if not used[j])
for i in range(1, 3))
print(bound)Kết quả
13
Hai người còn lại có thể cùng được ước lượng bằng việc thứ ba. Đây là phép nới lỏng để tính cận, không phải lời giải phân công. Khi xây dựng nghiệm thật, used vẫn ngăn việc được giao hai lần.
Python
def assign(cost):
n = len(cost)
used = [False] * n
best = float('inf')
def visit(person, current):
nonlocal best
if person == n:
best = min(best, current)
return
remaining = [j for j in range(n) if not used[j]]
lower = current + sum(min(cost[i][j] for j in remaining)
for i in range(person, n))
if lower >= best:
return
for j in sorted(remaining, key=lambda j: cost[person][j]):
used[j] = True
visit(person + 1, current + cost[person][j])
used[j] = False
visit(0, 0)
return best
print(assign([[9, 2, 7], [6, 4, 3], [5, 8, 1]]))Kết quả
9
Mỗi việc chưa dùng được thử cho người hiện tại, nên các nhánh không bị cắt bao phủ các phân công hợp lệ. Dấu used[j] = False khôi phục trạng thái trước khi thử việc khác. best chỉ cập nhật tại lá, khi mọi người đã có việc.
Tại một nút, tính cận tốn tối đa O(n²). Có không quá n! lá và ít hơn e · n! nút trong cây hoán vị. Với n = 8, có 40 320 lá trước khi cắt; chi phí thực tế tùy dữ liệu, không chỉ phụ thuộc số lá.
Cận dưới vẫn đúng khi chi phí âm nếu được tính bằng tổng nhỏ nhất như trên. Tuy nhiên cắt chỉ vì current >= best sẽ sai với chi phí âm: những khoản âm sau đó có thể hạ tổng. Muốn dùng phép cắt đơn giản ấy phải chứng minh chi phí còn lại không âm.
Python
current, best = 10, 7
remaining_cost = -5
print(current >= best)
print(current + remaining_cost < best)Kết quả
True True
Chọn thứ tự tìm kiếm tốt mà vẫn giữ mọi lựa chọn
Thử việc rẻ trước hoặc kiện lớn trước có thể giúp tìm best tốt sớm. Đây là cách sắp thứ tự, không phải bằng chứng rằng lựa chọn đầu tiên thuộc nghiệm tối ưu. Các nhánh khác vẫn được xem xét trừ khi cận an toàn cho phép cắt.
Python
cost = [[1, 2], [1, 100]]
greedy = cost[0][0] + cost[1][1]
alternative = cost[0][1] + cost[1][0]
print(greedy, alternative)Kết quả
101 3
Nếu chỉ cần giá trị tối ưu, best không cần lưu thứ tự lựa chọn. Nếu cần khôi phục nghiệm, hãy sao chép đường đi khi cải thiện best. Với bài đếm mọi nghiệm tối ưu, phải giữ các nhánh có thể bằng best và đếm từng nghiệm hợp lệ.
Lỗi thường gặp
| Lỗi | Vì sao sai | Cách sửa |
|---|---|---|
| Dùng cận trên quá thấp cho bài tối đa | Có thể bỏ nhánh chứa nghiệm tốt hơn | Chứng minh mọi kết quả trong nhánh không vượt cận |
| Nhầm chiều so sánh ở bài tối thiểu | Cận dưới nhỏ vẫn có thể dẫn đến chi phí tốt | Cắt khi cận dưới lớn hơn hoặc bằng best |
Khởi tạo best bằng một giá trị không có nghiệm | Một nhánh tốt có thể bị loại theo đáp án giả | Dùng nghiệm hợp lệ hoặc vô cực phù hợp |
| Bỏ nhánh quá tải khi còn số âm | Số âm sau đó có thể đưa tổng về hợp lệ | Chứng minh các số còn lại không âm |
Quên hoàn tác used | Lựa chọn của nhánh trước rò sang nhánh sau | Khôi phục ngay sau lời gọi đệ quy |
Cắt khi bằng best để liệt kê mọi nghiệm | Có thể mất nghiệm khác có cùng giá trị | Chỉ cắt khi cận kém hẳn nghiệm đã biết |
Tóm tắt
bestlà giá trị của nghiệm hợp lệ tốt nhất đã biết; cận là giới hạn lạc quan cho cả một nhánh.- Bài tối đa hóa cắt khi cận trên không vượt
best; bài tối thiểu hóa cắt khi cận dưới không nhỏ hơnbest, nếu chỉ cần giá trị. - Tổng hậu tố không âm và tổng chi phí nhỏ nhất theo từng người là hai cách tính cận an toàn.
- Thứ tự thử có thể giảm số nút, nhưng trường hợp xấu vẫn tăng theo hàm mũ hoặc giai thừa.