+ cấu trúc dữ liệu :

1-định nghĩa :

 Phương pháp nhánh cận là một phương pháp được áp dụng để tìm nghiệm của bài toán tối ưu.

 Phương pháp nhánh cận là một dạng cải tiến của phương pháp quay lui. Trường hợp xấu nhất của phương pháp là trở về phương pháp quay lui.

 Phương pháp nhánh cận khác phương pháp quay lui là ta xây dựng một hàm để đánh giá nghiệm. Tại một phương án bộ phận: nếu giá nghiệm có thể phát triển tại đó mà lớn hơn nghiệm tốt nhất đã có ->cắt bỏ các nhánh đi từ nó và quay lên trên thử lại nghiệm khác.

2-biểu diễn dữ liệu :

3-các phép toán :

PHƯƠNG PHÁP NHÁNH CẬN

 Giả sử cần xây dựng ngiệm bài toán (x1, x2, ..., xn) với xi được chọn từ một tập Ai.

 Để xây dựng nghiệm của bài toán ta xây dựng dần từng nghiệm thành phần là từ x1, x2, ..., xk.

 Với mỗi 1 nghiệm thành phần sẽ gắn với 1 hàm đánh giá:

cost(x1, ....., xk) ->Phải tìm nghiệm có giá nhỏ nhất.

 Khi xây dựng nghiệm: giả sử có nghiệm (x1, x2, ...., x(k-1)) cần mở rộng nghiệm (x1, x2,.....,xk).

 Nếu nghiệm mở rộng (x1, x2, ..., xk) mà có giá lớn hơn nghiệm tốt nhất trước đó thì cắt tất cả các nhánh đi xuống từ xk và quay lui phát triển các nhánh khác (x1, x2, ....., x(k-2)).

- tư tưởng :

- thủ tục :

void Try(Nghiệm thứ k)

{

for(int i=0; i<n; i++)

< khởI tạo giá trị ban đầu>

if(chấp nhận )

{

<Ghi nhớ trạng thái nghiệm>

if(k=n) <Cập nhật kỉ lục>

else

if (cost(x1, x2, ...., xk)<=lowcost)

Try(k+1);

<Xoá ghi nhớ>;

}

}