Ý tưởng:

Với các bài toán tìm phương án tối ưu, nếu chúng ta xét hết tất cả các phương án thì mất rất nhiều thời gian, nhưng nếu sử dụng phương pháp tham ăn thì phương án tìm được chưa hẳn đã là phương án tối ưu. Nhánh cận là kỹ thuật xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh.             Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có, mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n. Kỹ thuật này gọi là phân nhánh.Ý tưởng chính của nó như sau :

Trong quá trình duyệt ta luôn giữ lại một phương án mẫu ( có thể xem là lời giải tối ưu cục bộ - chẳng hạn có giá nhỏ nhất tại thời điểm đó ). Đánh giá nhánh cận là phương pháp tính giá của phương án ngay trong quá trình xây dựng các thành phần của phương án theo hướng đang xây dựng có thể tốt hơn phương án mẫu hay không. Nếu không ta lựa chọn theo hướng khác.

Với mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị gần với giá của các phương án. Với bài toán tìm min ta sẽ xác định cận dưới còn với bài toán tìm max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án.

Mô hình chung

Giả sử bài toán tối ưu cho là :

Tìm Min{f(x) : x ? D};

Nghiệm của bài toán nếu có sẽ được biểu diễn dưới dạng :x = (x₁,...,x_n). Trong quá trình liệt kê theo phương pháp quay lui, ta xây dựng dần các thành phần của nghiệm.

Một bộ phận i thành phần (x₁, .., x_i) sẽ gọi là một lời giải (phương án) bộ phận cấp i. Ta gọi X_i là tập các lời giải bộ phận cấp i, mọi i= 1, n .

Đánh giá cận là tìm một hàm g xác định trên các Xi sao cho :

g ( x1,…, xi ) ≤ Min {f(a) : a = ( a1,.., an ) € X , xi = ai , mọi i= 1, n .

Thủ tục quay lui sửa lại thành thủ tục nhánh cận như sau :

Try (i)

for (j = 1 -> n)

if( Chấp nhận được )

{

Xác định xi theo j;

Ghi nhận trạng thái mới;

If ( i == n)

Cập nhật lời giải tối ưu ;

else

{

Xác định cận g (x₁,…,x_i)

If g (x₁,…,x_i) ≤ f^*

Try (i+1);

}

// Trả bài toán về trạng thái cũ