Thuật toán nhánh cận

Mô hình thuật toán nhánh cận

Dựa trên mô hình thuật toán quay lui, ta xây dựng mô hình sau:

Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả  năng đánh giá theo từng bước, nếu tại bước thứ i, giá trị thử gán cho x[i]  không có hi vọng tìm thấy cấu hình tốt hơn BESTCONFIG thì thử giá trị khác ngay mà không cần gọi đệ quy tìm tiếp hay ghi nhận kết quả làm gì. Nghiệm của bài toán sẽ được làm tốt dần, bởi khi tìm ra một cấu hình mới (tốt hơn BESTCONFIG) ta không in kết quả ngay mà cập nhật BESTCONFIG bằng cấu hình mới vừa tìm được.

 

 

Share
Share