Phương pháp nhánh cận

Phương pháp (hay giải thuật) nhánh cận là một trong những phương pháp giải các bài toán liệt kê cấu hình có điều kiện tối ưu.

1. Bài toán tối ưu
- Bài toán yêu cầu tìm ra một phương án tốt nhất thỏa mãn một số yêu cầu ràng buộc nào đó – nghiệm của bài toán đạt giá trị max/min trong không gian nghiệm.

- Thuộc lĩnh vực Tối ưu toán học hoặc Quy hoạch toán học. Lời giải toán có thể khó => Sự vào cuộc của Tin học

- Hai hướng tiếp cận tìm lời giải tối ưu cho bài toán:

+ Tìm từng lời giải, khi hoàn tất một lời giải thì so sánh của nó với chi phí tốt nhất hiện có. Nếu tốt hơn thì cập nhật chi phí tốt nhất mới.

+ Với mỗi lời giải, khi xây dựng các thành phần nghiệm luôn kiểm tra điều kiện nếu đi tiếp theo hướng này thì có khả năng nhận được lời giải tốt hơn lời giải hiện có không? Nếu không thì thôi không đi theo hướng này nữa. => Nguyên lí nhánh cận 

2. Ý tưởng
- Nhánh cận (Branch and Bound): Thuật toán tìm lời giải cho các bài toán tối ưu dạng liệt kê cấu hình dựa trên nguyên lí đánh giá nhánh cận.

- Nguyên lí đánh giá nhánh cận: Sử dụng các thông tin đã tìm được trong lời giải của bài toán để loại bỏ sớm phương án không dẫn tới lời giải tối ưu

- Bản chất:

+ Sử dụng phương pháp quay lui nhưng tại mỗi bước đưa thêm thao tác đánh giá giá trị phương án hiện có.

+ Nếu đó là phương án tối ưu hoặc có hy vọng trở thành phương án tối ưu (tức là tốt hơn phương án hiện có) thì cập nhật lại phương án tối ưu hoặc đi tiếp theo hướng đó.

+ Trong trường hợp ngược lại thì bỏ qua hướng đang xét.