Phát biểu bài toán

• Giả sử ta có tập
• Xét một phần tử và một hàm
• Bài toán tối ưu yêu cầu tìm giá trị nhỏ nhất/lớn nhất của với
• Việc này có thể đạt được bằng phương pháp duyệt toàn bộ sử dụng thuật toán quay lui, tuy nhiên để duyệt toàn bộ sẽ cần một khoảng thời gian và tài nguyên lớn.

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

• Thuật toán nhánh cận giúp giảm bớt độ phức tạp của thuật toán quay lui, bằng cách cắt bỏ các nhánh nếu không đủ điều kiện
• Xét bài toán tìm giá trị nhỏ nhất của hàm .
• Đầu tiên, ta xây dựng hàm thỏa mãn tính chất: với mỗi k, bất đẳng thức sau được thỏa mãn
• Hàm này được gọi là hàm cận dưới của .
• Giả sử phương án tốt nhất hiện tại là và . Nếu , khi đó chắc chắn , nên sẽ không thể là phương án tốt hơn . Khi đó ta sẽ dừng việc duyệt tiếp đến phương án bộ phận , chuyển sang ứng cử viên khác cho , và nếu không còn ứng cử viên phù hợp, ta trở về ,…
• Đối với bài toán tìm giá trị lớn nhất, ta xét hàm cận trên, tức là
• Và kiểm tra nếu thì sẽ kết thúc
• Như vậy có thể thấy, có hai yếu tố quan trọng đối với thuật toán nhánh cận:
  • Hàm cận trên/dưới
  • Tập ứng cử viên và cách duyệt

Mã giả

• Dựa trên mã giả của thuật toán quay lui, ta bổ sung phần kiểm tra hàm cận dưới

Try(k):
	Xây dựng S_k;
	Với mỗi x_k trong S_k:
		Chọn x_k;
		Nếu k == n:
			Nếu f(x) < f_best:
				Cập nhật kỉ lục;
		Nếu k < n:
			Nếu g(x) <= f_best:
				Try(k+1);
		Bỏ chọn x_k;

• Đầu tiên ta khởi tạo f_best = inf hoặc một giá trị nào đó ta biết chắc lớn hơn tất cả các . Sau khi chạy Try(1), ta sẽ có cấu hình tối ưu cần thiết.

Một số bài toán cụ thể

Bài toán cái túi (Knapsack Problem)

Phát biểu bài toán

• Giả sử ta có một cái túi có khối lượng tối đa có thể chứa được là .
• Ta có món đồ, món đồ thứ có khối lượng và giá trị .
• Giả sử số lượng mỗi món đồ là không hạn chế
• Bài toán: cần lấy những món đồ gì, số lượng bao nhiêu để giá trị thu được là lớn nhất?

Biểu diễn bài toán

• Ta có thể biểu diễn lại bài toán thành bài toán: tìm nghiệm của bất phương trình sao cho là lớn nhất?
• Ta sẽ sắp xếp các đồ vật theo thứ tự giảm dần về tỉ lệ giá trị/ khối lượng, tức là
• Hàm

Tìm hàm cận trên

• Để có thể giải bài toán trên sử dụng thuật toán nhánh cận, ta cần xác định hàm cận trên phù hợp
• Giả sử ta đã có phương án bộ phận thứ là . Khối lượng còn lại cái túi có thể nhận là

• Giá trị hiện tại ta đang có

• Ta cần xây dựng hàm sao cho
• Ta có

• Theo cách sắp xếp, ta luôn có

• Vậy ta có thể lấy

• Trong quá trình duyệt, ta sẽ lấy giảm dần từ về 0

Bài toán người du lịch (Travelling Salesman Problem)

Phát biểu bài toán

• Một người du lịch muốn đi tham quan thành phố .
• Xuất phát từ thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, quay trở lại điểm xuất phát
• Chi phí di chuyển giữa các thành phố được biểu diễn trong ma trận , với biểu thị chi phí đi từ đến
• Ta cần tìm đường đi thỏa mãn yêu cầu, sao cho chi phí là thấp nhất

Biểu diễn bài toán

• Xét một hoán vị của n số tự nhiên đầu tiên
• Chi phí di chuyển là

• Ta cần tìm

Tìm hàm cận dưới

• Gọi là chi phí nhỏ nhất giữa hai thành phố bất kì
• Giả sử tại phương án bộ phận cấp , ta có đường đi , với chi phí hiện tại là
• Ta còn cần phải đi đoạn đường nữa, nên ta có

• Ta có thể duyệt theo cách tương tự việc duyệt toán bộ để sinh hoán vị