I. Tổng quan
1. Giới thiệu phương pháp
Trong lập trình cũng như trong thực tế, chắc hẳn các bạn đều đã gặp những bài toán với yêu cầu tìm kết quả tốt nhất thỏa mãn một hoặc một số điều kiện nào đó. Sự thật là chúng ta gặp các bài toán này khá thường xuyên, thậm chí vô cùng thực tiễn, chẳng hạn như:
- Tìm cách trả số tiền TT với nn tờ tiền có mệnh giá cho trước, sao cho số tờ tiền cần sử dụng là nhỏ nhất?
- Trong các nhà máy sản xuất vỏ lon đồ uống, các nhà thiết kế luôn luôn tìm cách thiết kế sao cho diện tích toàn phần của vỏ lon là nhỏ nhất nhằm giảm thiểu chi phí nguyên liệu. Bài toán đặt ra là với thể tích cần thiết là V,V, làm sao để tạo ra vỏ lon hình trụ có diện tích toàn phần nhỏ nhất?
……
Có rất nhiều bài toán như vậy trong Tin học, và chúng được gọi là các bài toán tối ưu. Thông thường, người ta sẽ hay nghĩ đến phương pháp Quy hoạch động khi giải các bài toán tối ưu, tuy nhiên, phương pháp này chỉ có thể áp dụng nếu như bài toán đang xét có bản chất đệ quy mà thôi. Thực tế có nhiều bài toán tối ưu không có thuật toán nào thực sự hữu hiệu để giải quyết, mà vẫn phải sử dụng mô hình xem xét tất cả các phương án rồi đánh giá chúng để chọn ra phương án tốt nhất.
Phương pháp Nhánh và Cận (Branch and Bound) chính là một phương pháp cải tiến từ phương pháp Quay lui, được sử dụng để tìm nghiệm của bài toán tối ưu.
2. Ý tưởng
Bước đầu tiên của phương pháp vẫn giống với ý tưởng của quay lui: Tìm cách biểu diễn nghiệm của bài toán dưới dạng một vector (x1,x2,…,xn),(x_1, x_2,dots, x_n), mỗi thành phần xix_i được chọn ra từ tập các ứng cử viên SiS_i.
Bước tiếp theo sẽ hơi khác một chút: Nếu như ở phương pháp Quay lui, chỉ cần tuần tự chọn các ứng cử viên cho từng thành phần của vector nghiệm, thì ở phương pháp Nhánh và cận, mỗi nghiệm X=(x1,x2,…,xn)X = (x_1, x_2, dots, x_n) của bài toán sẽ được đánh giá độ tốt bằng một hàm f(X)f(X). Vì đây là bài toán tối ưu, nên mục tiêu của chúng ta là đi tìm nghiệm có hàm f(X)f(X) tốt nhất, thường là lớn nhất hoặc nhỏ nhất.
Bước thứ 33 là xây dựng nghiệm của bài toán. Giả sử, các bạn đã xây dựng được ii thành phần của nghiệm là (x1,x2,…,xi)(x_1, x_2,dots, x_i) và chuẩn bị mở rộng nghiệm thành (x1,x2,…,xi,xi+1)(x_1, x_2,dots, x_i, x_{i + 1}). Nếu như bằng một cách nào đó, các bạn đánh giá được độ tốt của toàn bộ các nghiệm mở rộng của nhánh này là (x1,x2,…,xi,xi+1,… )(x_1, x_2,dots, x_{i}, x_{i + 1},dots) và biết rằng không có nghiệm nào trong nhánh này “tốt hơn” nghiệm tốt nhất tại thời điểm đó, thì việc mở rộng tiếp từ (x1,x2,…,xi)(x_1, x_2,dots, x_i) sẽ là không cần thiết nữa, mà thay vào đó ta sẽ chuyển qua chọn ứng cử viên tiếp theo cho thành phần xix_i luôn.
Bằng phương pháp trên, ta sẽ loại bỏ được những nhánh không cần thiết để không duyệt vào các phương án đó, từ đó việc tìm ra nghiệm tối ưu sẽ nhanh hơn. Tuy nhiên, việc đánh giá được “độ tốt” của các nghiệm mở rộng không phải việc đơn giản, nhưng nếu làm được như vậy thì giải thuật sẽ thực thi nhanh hơn nhiều so với quay lui.
3. Lược đồ giải thuật
Để thực hiện giải thuật Nhánh và Cận, các bạn có thể sử dụng một hàm đệ quy giống như giải thuật Quay lui, nhưng thêm phần đánh giá nghiệm trước khi xây dựng thành phần thứ ii. Ngoài ra, ta cần sử dụng thêm một biến text{best_solution} để ghi nhận nghiệm tốt nhất hiện tại.
Dưới đây là mô hình cài đặt bằng C++:
voidbranch_and_bound(i){// Đánh giá các nghiệm mở rộngif({Các_nghiệm_mở_rộng_đều_không_tốt_hơn_best_solution})return;for(value in S[i]){
x[i]= value;// Ghi nhận thành phần thứ i.if({Tìm_thấy_nghiệm})
best_solution = X;// Cập nhật lại best_solution bằng nghiệm vừa tìm được.elsebranch_and_bound(i +1);// Chưa tìm thấy nghiệm thì xây dựng tiếp.{Loại_bỏ_thành_phần_thứ_i}}}Bây giờ, hãy cùng đến với một số bài toán minh họa để hiểu rõ hơn về phương pháp!
II. Một số bài toán minh họa
1. Rút tiền ATM
Đề bài
Một máy ATM hiện có nn tờ tiền có giá trị lần lượt là t1,t2,…,tnt_1, t_2,dots, t_n. Hãy tìm ra cách trả số tiền SS sao cho số tờ tiền phải sử dụng là ít nhất?
Input:
- Dòng đầu tiên chứa hai số nguyên dương nn và S (1≤n≤20;1≤S≤1000)S (1 le n le 20; 1 le S le 1000).
- Dòng thứ hai chứa nn số nguyên dương t1,t2,…,tnt_1, t_2,dots, t_n phân tách nhau bởi dấu cách (1≤ti≤1000;∀i:1≤i≤n)(1 le t_i le 1000; forall i: 1 le i le n).
Output:
- Nếu như có thể trả số tiền SS thì in ra số tờ tiền ít nhất cần sử dụng và các tờ tiền được chọn, ngược lại in ra −1-1.
Sample Input:
10 390
200 10 20 20 50 50 50 50 100 100
Sample Output:
5
20 20 50 100 200
Phân tích ý tưởng
Nghiệm của bài toán có thể biểu diễn dưới dạng một vector gồm toàn các bit nhị phân 0−10 – 1 là x1,x2,…,xnx_1, x_2,dots, x_n với ý nghĩa: xi=0x_i = 0 là tờ tiền thứ ii không được chọn, xi=1x_i = 1 là tờ tiền thứ ii được chọn.
Mục tiêu chúng ta đang cần tìm một bộ nghiệm sao cho:
{t1×x1+t2×x2+⋯+tn×xn=S.(x1+x2+⋯+xn) MIN.begin{cases}t_1 times x_1 + t_2 times x_2 + cdots + t_n times x_n = S.\ (x_1 + x_2 + cdots + x_n) text{ MIN}. end{cases}
Giả sử các bạn đã xây dựng được ii thành phần của nghiệm là (x1,x2,…,xi),(x_1, x_2, dots, x_i), tổng số tờ tiền đã sử dụng là cntcnt và số tiền đã trả được là sum,sum, thì ta nhận xét thấy:
- Số tiền còn lại cần trả là S−sumS – sum.
- Nếu gọi tmax[i+1]t_{max}[i + 1] là giá trị của tờ tiền lớn nhất trong các tờ tiền còn lại (tmax[i+1]=max(ti+1,ti+2,…,tn)),(t_{max}[i + 1] = text{max}big(t_{i + 1}, t_{i + 2}, dots, t_n)big), thì ít nhất ta cần sử dụng thêm S−sumtmax[i+1]frac{S – sum}{t_{max}[i + 1]} tờ tiền nữa, tức là tổng số tờ tiền tối thiểu cần dùng của nhánh phương án này là cnt+S−sumtmax[i+1]cnt + frac{S – sum}{t_{max}[i + 1]}.
Gọi số tờ tiền của cách trả tốt nhất hiện tại là text{cnt_best}, thì nếu như cnt + frac{S – sum}{t_{max}[i]} ge text{best_cnt}, ta sẽ không cần phải mở rộng các nghiệm từ (x1,x2,…,xi)(x_1, x_2,dots, x_i) nữa.
Để kiểm soát các tờ tiền được chọn, mình sử dụng thêm hai mảng là marktext{mark} để đánh dấu các tờ tiền được chọn trong một phương án, và text{mark_best} để đánh dấu các tờ tiền được chọn trong phương án tốt nhất.
Cài đặt
#include<bits/stdc++.h>usingnamespace std;constint maxn =21;int n, S, cnt, cnt_best, sum, a[maxn], mark[maxn], mark_best[maxn], maxmoney[maxn];voidenter(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> S;for(int i =1; i <= n;++i)
cin >> t[i];}voidcreate_data(){// cnt_best là số tờ tiền sử dụng trong phương án tốt nhất.// Ban đầu chưa có phương án nào, gán cnt_best = n + 1.
best_cnt = n +1;// t_max[i] lưu giá trị của tờ tiền lớn nhất từ i tới n.
t_max[n]= t[n];for(int i = n -1; i >=0;--i)
t_max[i]=max(t_max[i +1], t[i]);}// Nếu tìm được một phương án tốt hơn thì cập nhật lại kết quả.voidupdate_best_solution(){if(sum == S && cnt < cnt_best){
cnt_best = cnt;for(int i =1; i <= n;++i)
mark_best[i]= mark[i];}}// In kết quả.voidprintf_result(){// Không tìm được cách trả tiền, in ra -1.if(cnt_best == n +1)
cout <<-1;else// Tìm được thì in ra cách trả đó.{
cout << cnt_best << endl;for(int i =1; i <= n;++i)if(mark_best[i])
cout << t[i]<<' ';}}voidbranch_and_bound(int i){// Nếu nghiệm mở rộng của nhánh này không tốt hơn thì return.if(cnt +(S - sum)/ t_max[i +1]>= cnt_best)return;for(int j =0; j <=1;++j){// Ghi nhận thành phần thứ i.
sum = sum + a[i]* j;
mark[i]= j;
cnt += j;if(i == n)update_best_solution();elseif(sum <= S)branch_and_bound(i +1);// Loại bỏ thành phần thứ i.
sum -= t[i]* j;
cnt -= j;}}intmain(){enter();create_data();branch_and_bound(1);printf_result();return0;}2. Bài toán Người du lịch
Đề bài
Có nn thành phố đánh số từ 11 tới nn. Giữa các cặp thành phố có thể có hoặc không có đường nối hai chiều, mạng lưới đường này được mô tả bằng một ma trận Cu,v,C_{u, v}, với ý nghĩa Cu,v=Cv,uC_{u, v} = C_{v, u} là chi phí để di chuyển giữa hai thành phố uu và vv.
Một người du lịch xuất phát từ thành phố 1,1, người này muốn đi thăm tất cả các thành phố khác, mỗi thành phố đúng một lần rồi quay trở lại thành phố 11.
Yêu cầu: Hãy tìm một hành trình cho người đó sao cho chi phí di chuyển là ít nhất?
Input:
- Dòng đầu tiên chứa số nguyên dương n (1≤n≤20)n (1 le n le 20).
- nn dòng tiếp theo, mỗi dòng chứa nn số nguyên dương không vượt quá 100100 biểu thị ma trận CC.
Output:
- Dòng đầu tiên ghi chi phí nhỏ nhất.
- Dòng thứ hai ghi một hành trình tìm được.
Sample Input:
4
0 20 35 42
20 0 34 30
35 34 0 12
42 30 12 0
Sample Output:
97
1 2 4 3 1
Hình minh họa:
Phân tích ý tưởng
Vector nghiệm của bài toán là một dãy (x1=1,x2,x3,…,xn,xn+1=1);(x_1 = 1, x_2, x_3,dots, x_n, x_{n + 1} = 1); với điều kiện giữa hai thành phố xix_i và xi+1x_{i + 1} phải có đường đi trực tiếp. Ngoài ra, chỉ có thành phố 11 được phép lặp lại 22 lần. Vì thế, có thể thấy dãy (x1,x2,…,xn)(x_1, x_2,dots, x_n) là một hoán vị của (1,2,…,n)(1, 2, dots, n).
Ý tưởng duyệt quay lui như sau: Khi đã xây dựng được (x1,x2,…,xi),(x_1, x_2,…, x_i), thì xi+1x_{i + 1} có thể chọn một trong các thành phố mà có đường nối trực tiếp với nó, đồng thời chưa được chọn. Tuy nhiên, ta có thể áp dụng Nhánh và Cận để giảm độ phức tạp như sau:
- Gọi chi phí tốt nhất hiện tại là text{best_cost}.
- Với mỗi bước thử chọn xi,x_i, kiểm tra xem chi phí đường đi tính tới lúc đó có lớn hơn hoặc bằng chi phí tốt nhất hiện tại hay không. Nếu đã lớn hơn thì chọn ngay giá trị khác cho xi,x_i, bởi vì có đi tiếp theo nhánh này cũng sẽ chỉ tạo ra chi phí lớn hơn mà thôi.
- Tới khi chọn được một giá trị xnx_n thì cần kiểm tra xem chi phí tới xnx_n cộng thêm chi phí từ xnx_n về 11 có tốt hơn chi phí tốt nhất hiện tại không? Nếu có thì cập nhật lại cách đi tốt nhất.
Cài đặt
Trong cài đặt dưới đây, giả thiết rằng giữa mọi cặp thành phố đều tồn tại đường đi, và chi phí cu,vc_{u, v} luôn bằng 00 nếu như u=vu = v.
Mảng visitedtext{visited} dùng để đánh dấu một thành phố đã được thăm hay chưa trong một cấu hình XX. Mảng xx sử dụng để lưu cấu hình hiện tại, còn mảng text{x_best} sử dụng để lưu cấu hình tốt nhất với text{best_cost} là chi phí tốt nhất tìm được.
#include<bits/stdc++.h>#defineintlonglong#definetask"tsp."#defineinf1e9+7usingnamespace std;constint maxn =21;int n, current_cost, best_cost;int visited[maxn], x_best[maxn], x[maxn], c[maxn][maxn];voidenter(){
cin >> n;for(int i =1; i <= n;++i)for(int j =1; j <= n;++j)
cin >> c[i][j];// Khởi tạo trước thành phố đầu tiên là 1, đồng thời đánh dấu nó đã thăm.
x[1]=1;
visited[1]=1;// Khởi tạo chi phí tối ưu bằng +oo, giả sử phương án hiện tại đang rất tệ.
best_cost = inf;}// Cập nhật kết quả tốt nhất.voidupdate_best_solution(int current_cost){if(current_cost + c[x[n]][1]< best_cost){
best_cost = current_cost + c[x[n]][1];for(int i =1; i <= n;++i)
x_best[i]= x[i];}}// In ra phương án tốt nhất tìm được.voidprint_best_solution(){
cout << best_cost << endl;for(int i =1; i <= n;++i)
cout << x_best[i]<<"->";
cout <<1;}// Giải thuật nhánh và cận.voidbranch_and_bound(int i){if(current_cost >= best_cost)return;for(int j =2; j <= n;++j)if(!visited[j]){
visited[j]=1;
x[i]= j;
current_cost += c[x[i -1]][j];// Đã sinh xong một cấu hình, cập nhật chi phí tốt nhất.if(i == n)update_best_solution(current_cost);// Chưa sinh xong, tiếp tục sinh thành phần tiếp theo với chi phí tăng thêm.elsebranch_and_bound(i +1);
visited[j]=0;
current_cost -= c[x[i -1]][j];}}main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);enter();branch_and_bound(2);print_best_solution();return0;}III. Tài liệu tham khảo
Nguồn: viblo.asia