Tổng quan
Nhánh cận duyệt cây quyết định của một bài toán tổ hợp, nhưng có cắt tỉa: tại mỗi nút nó tính một cận trên lạc quan về những gì nhánh đó có thể đạt, và bỏ nhánh nếu cận đó không thể vượt lời giải tốt nhất tìm được đến lúc này. Bài toán ba lô 0/1 là ví dụ kinh điển.
Mỗi món đồ là một quyết định lấy/không lấy (nhánh), nên cây tìm kiếm có tới 2^n lá; cận (nới lỏng theo ba lô phân số) là thứ giúp tránh phải duyệt vét cạn nó trong thực tế.
Nhánh cận hoạt động thế nào?
- Rẽ nhánh theo món đồ kế tiếp: tạo hai nút con — một lấy nó, một bỏ qua nó.
- Tại mỗi nút, tính một cận trên lạc quan về giá trị tốt nhất có thể đạt bên dưới.
- Cắt tỉa nút nếu cận của nó không vượt quá lời giải hoàn chỉnh tốt nhất tìm được đến nay.
- Nếu không, đi xuống, cập nhật lời giải tốt nhất mỗi khi một lá khả thi cải thiện nó.
Khi nào nên dùng?
- Các bài toán tối ưu NP-khó cần đáp án chính xác: ba lô, người bán hàng, gán việc.
- Các trường hợp mà cận chặt cắt tỉa phần lớn cây, khiến việc tìm kiếm khả thi.
- Ưu tiên quy hoạch động hoặc heuristic khi trọng lượng là số nguyên bị chặn, hoặc khi đáp án gần đúng là đủ.
Phân tích độ phức tạp
Ở trường hợp xấu nhất không nhánh nào bị cắt và nhánh cận suy biến thành tìm kiếm vét cạn — O(2^n) với n quyết định nhị phân. Trong thực tế, một cận tốt cắt tỉa những mảng lớn của cây, nên nó nhanh hơn nhiều so với vét cạn trên các trường hợp điển hình, dù không cho đảm bảo tiệm cận tốt hơn.
Câu hỏi thường gặp
Nhánh cận khác backtracking thuần thế nào?
Backtracking chỉ cắt các nhánh vi phạm ràng buộc (bất khả thi). Nhánh cận còn cắt cả các nhánh khả thi mà cận lạc quan không thể vượt lời giải hiện tốt nhất, nên nó loại bỏ nhiều phần cây hơn hẳn trong bài toán tối ưu.
Điều gì tạo nên một hàm cận tốt?
Nó phải lạc quan (không bao giờ đánh giá thấp giá trị tốt nhất của nhánh) nhưng vẫn chặt (gần với tối ưu thực). Với ba lô, nới lỏng sang phiên bản phân số cho đúng một cận như vậy.