Sách hướng dẫn học tập Toán rời rạc - Nguyễn Duy Phương

x
+
+
+=+=
+=
+
+=
+∂=
⎭⎬
⎫
⎩⎨
⎧ ++=≥≤+∂≤
⎭⎬
⎫
⎩⎨
⎧ ++=∈≤+∂=
==∈
∑∑
∑∑
k
kk
k
n
kj
jkjj
n
kj
jjk
n
kj
jkjj
n
kj
jjk
jj
a
bc
nkkjxbxaxc
nkkjZxbxaxc
njuxDxxf
"
"
"
 85
Chương 4: Bài toán tối ưu 
(Theo mệnh đề giá trị số hạng thứ hai là 
1
1
+
+
k
kk
a
bc
) 
Vậy ta có thể tính cận trên cho phương án bộ phận (u1, u2,..., uk) theo công thức: 
 ""
1
1
21 ),,,(
+
++∂=
k
kk
kk a
bcuuug 
Chú ý: Khi tiếp tục xây dựng thành phần thứ k+1 của lời giải, các giá trị đề cử cho xk+1 sẽ là 
0, 1,..., [bk /ak+1]. Do có kết quả của mệnh đề, khi chọn giá trị cho xk+1 ta sẽ duyệt các giá trị đề cử 
theo thứ tự giảm dần. 
Ví dụ. Giải bài toán cái túi sau theo thuật toán nhánh cận trình bày trên. 
.4,3,2,1,
84235
max63510)(
4321
4321
=∈
≤+++
→+++=
+ jZx
xxxx
xxxxxf
j
Giải. Quá trình giải bài toán được mô tả trong cây tìm kiếm trong hình 4.1. Thông tin về 
một phương án bộ phận trên cây được ghi trong các ô trên hình vẽ tương ứng theo thứ tự sau: đầu 
tiên là các thành phấn của phương án, tiếp đến ∂ là giá trị của các đồ vật chất trong túi, w là trọng 
lượng còn lại của túi và g là cận trên. 
Kết thúc thuật toán, ta thu được phương án tối ưu là x* =(1, 1, 0, 1), giá trị tối ưu f*= 15. 
 86 
Chương 4: Bài toán tối ưu 
 x1=1 x1=0 
 x1=1 x2=0 
 Loại vì cận trên <kỷ lục 
 x3=0 
 x4=0 
Gốc +∞=f 
∂=10; 
w=3; g=15 
(0) ∂=0; 
w=8; g=40/3 
(1,1) ∂=15; 
w=0; g=15 
(1, 0) ∂=10; 
w=3; g=14.5 
(1,1,0) ∂=15; 
w=0; g=15 
;15
);0,0,1,1(
=
=
f
x
Hình 4.1. Giải bài toán cái túi theo thuật toán nhánh cận. 
Chương trình giải bài toán cái túi theo thuật toán nhánh cận được thể hiện như sau: 
#include 
#include 
#include 
#include 
#include 
#define TRUE 1 
#define FALSE 0 
#define MAX 100 
int x[MAX], xopt[MAX]; 
float fopt, cost, weight; 
 87
Chương 4: Bài toán tối ưu 
void Init(float *C, float *A, int *n, float *w){ 
 int i;FILE *fp; 
 fopt=0; weight=0; 
 fp=fopen("caitui.in","r"); 
 if(fp==NULL){ 
 printf("\n Khong co file input"); 
 delay(2000); return; 
 } 
 fscanf(fp,"%d %f", n,w); 
 for(i=1; i<=*n;i++) xopt[i]=0; 
 printf("\n So luong do vat %d:", *n); 
 printf("\n Gioi han tui %8.2f:", *w); 
 printf("\n Vecto gia tri:"); 
 for(i=1; i<=*n; i++) { 
 fscanf(fp,"%f", &C[i]); 
 printf("%8.2f", C[i]); 
 } 
 printf("\n Vector trong luong:"); 
 for(i=1; i<=*n; i++){ 
 fscanf(fp,"%f", &A[i]); 
 printf("%8.2f", A[i]); 
 } 
 fclose(fp); 
} 
void swap(int n){ 
 int i; 
 for(i=1; i<=n; i++) 
 xopt[i]=x[i]; 
} 
void Update_Kyluc(int n){ 
 if(cost>fopt){ 
 swap(n); 
 88 
Chương 4: Bài toán tối ưu 
 fopt=cost; 
 } 
} 
void Try(float *A, float *C, int n, float w, int i){ 
 int j, t=(w-weight)/A[i]; 
 for(j=t; j>=0;j--){ 
 x[i]=j; 
 cost = cost + C[i]*x[i]; 
 weight = weight + x[i]*A[i]; 
 if(i==n) Update_Kyluc(n); 
 else if(cost + C[i+1]*(w-weight)/A[i+1]> fopt){ 
 Try(A, C, n, w, i+1); 
 } 
 weight = weight-A[i]*x[i]; 
 cost = cost-C[i]*x[i]; 
 } 
} 
void Result(int n){ 
 int i; 
 printf("\n Gia tri do vat %8.2f:", fopt); 
 printf("\n Phuong an toi uu:"); 
 for(i=1; i<=n; i++) 
 printf("%3d", xopt[i]); 
} 
void main(void){ 
 int n; 
 float A[MAX], C[MAX], w; 
 clrscr();Init(C, A, &n, &w); 
 Try(C, A, n, w,1);Result(n); 
 getch(); 
} 
 89
Chương 4: Bài toán tối ưu 
Ví dụ 2. Bài toán Người du lịch. Một người du lịch muốn đi thăm quan n thành phố T1, T2, , 
Tn. Xuất phát từ mộ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ố đi qua đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là chi phí đi từ 
thành phố Ti đến thành phố Tj (i = 1, 2,.., n), hãy tìm hành trình với tổng chi phí là nhỏ nhất (một 
hành trình là một cách đi thoả mãn điều kiện). 
Giải. Cố định thành phố xuất phát là T1. Bài toán Người du lịch được đưa về bài toán: Tìm 
cực tiểu của phiếm hàm: 
min],[],[],[],1[),,,( 1132221 →++++= − xxcxxcxxcxcxxxf nnnn "" 
với điều kiện 
 { jinjijicc }≠== ;,,2,1,],,[minmin " là chi phí đi lại giữa các thành phố. 
Giả sử ta đang có phương án bộ phận (u1, u2,..., uk). Phương án tương ứng với hành trình bộ 
phận qua k thành phố: 
 )()()( 121 kk uTuTuTT →→→→ −"
Vì vậy, chi phí phải trả theo hành trình bộ phận này sẽ là tổng các chi phí theo từng node 
của hành trình bộ phận. 
∂ =c[1,u2] + c[u2,u3] +... + c[uk-1, uk]. 
Để phát triển hành trình bộ phận này thành hành trình đầy đủ, ta còn phải đi qua n-k thành 
phố còn lại rồi quay trở về thành phố T1, tức là còn phải đi qua n-k+1 đoạn đường nữa. Do chi phí 
phải trả cho việc đi qua mỗi trong n-k+1 đoạn đường còn lại đều không nhiều hơn cmin, nên cận 
dưới cho phương án bộ phận (u1, u2,..., uk) có thể được tính theo công thức 
g(u1, u2,..., uk) = ∂ +(n - k +1) cmin. 
Chẳng hạn ta giải bài toán người du lịch với ma trận chi phí như sau 
0511159
120726
4160917
2022403
15181430
=C 
Ta có cmin = 2. Quá trình thực hiện thuật toán được mô tả bởi cây tìm kiếm lời giải được thể 
hiện trong hình 4.2. 
Thông tin về một phương án bộ phận trên cây được ghi trong các ô trên hình vẽ tương ứng 
theo thứ tự sau: 
ƒ Đầu tiên là các thành phần của phương án 
ƒ Tiếp đến ∂ là chi phí theo hành trình bộ phận 
 90 
Chương 4: Bài toán tối ưu 
ƒ g là cận dưới 
Kết thúc thuật toán, ta thu được phương án tối ưu ( 1, 2, 3, 5, 4, 1) tương ứng với phương án 
tối ưu với hành trình: 
 và chi phí nhỏ nhất là 22 145321 TTTTTT →→→→→
Các nhánh này bị loại vì có cận 
dưới g> 22=f 
+∞=f
(2) ∂=3; g=15 (3) ∂=14; g=26 (4) ∂=18; g=30 (5) ∂=15; g=27 
(2,3) ∂=7; g=16 (2,4) ∂=25; g=34 (2,5) ∂=23; g=32 
(2,3,4) ∂=23; 
g=29 
(2,3,5) ∂=11; 
g=17 
(2,3,4,5) ∂=41; 
g=44 
(2,3,5,4) ∂=16; 
g=19 
Hành trình ( 1, 2, 3,4, 5,1) 
chi phí 53. Đặt 53=f 
Hành trình ( 1, 2, 3, 5,4, 1) 
chi phí 25(Kỷ lục mới). Đặt 
22=f 
Hình 4.2. Cây tìm kiếm lời giải bài toán người du lịch. 
Chương trình giải bài toán theo thuật toán nhánh cận được thể hiện như sau: 
#include 
#include 
#include 
 91
Chương 4: Bài toán tối ưu 
#include 
#define MAX 20 
int n, P[MAX], B[MAX], C[20][20], count=0; 
int A[MAX], XOPT[MAX]; 
int can, cmin, fopt; 
void Read_Data(void){ 
 int i, j;FILE *fp; 
 fp = fopen("dulich.in","r"); 
 fscanf(fp,"%d", &n); 
 printf("\n So thanh pho: %d", n); 
 printf("\n Ma tran chi phi:"); 
 for (i=1; i<=n; i++){ 
 printf("\n"); 
 for(j=1; j<=n; j++){ 
 fscanf(fp,"%d",&C[i][j]); 
 printf("%5d", C[i][j]); 
 } 
 } 
} 
int Min_Matrix(void){ 
 int min=1000, i, j; 
 for(i=1; i<=n; i++){ 
 for(j=1; j<=n; j++){ 
 if (i!=j && min>C[i][j]) 
 min=C[i][j]; 
 } 
 } 
 return(min); 
} 
void Init(void){ 
 int i; 
 cmin=Min_Matrix(); 
 92 
Chương 4: Bài toán tối ưu 
 fopt=32000;can=0; A[1]=1; 
 for (i=1;i<=n; i++) 
 B[i]=1; 
} 
void Result(void){ 
 int i; 
 printf("\n Hanh trinh toi uu %d:", fopt); 
 printf("\n Hanh trinh:"); 
 for(i=1; i<=n; i++) 
 printf("%3d->", XOPT[i]); 
 printf("%d",1); 
} 
void Swap(void){ 
 int i; 
 for(i=1; i<=n;i++) 
 XOPT[i]=A[i]; 
} 
void Update_Kyluc(void){ 
 int sum; 
 sum=can+C[A[n]][A[1]]; 
 if(sum<fopt) { 
 Swap(); 
 fopt=sum; 
 } 
} 
void Try(int i){ 
 int j; 
 for(j=2; j<=n;j++){ 
 if(B[j]){ 
 A[i]=j; B[j]=0; 
 can=can+C[A[i-1]][A[i]]; 
 if (i==n) Update_Kyluc(); 
 93
Chương 4: Bài toán tối ưu 
 else if( can + (n-i+1)*cmin< fopt){ 
 count++; 
 Try(i+1); 
 } 
 B[j]=1;can=can-C[A[i-1]][A[i]]; 
 } 
 } 
} 
void main(void){ 
 clrscr();Read_Data();Init(); 
 Try(2);Result(); getch(); 
} 
4.4. KỸ THUẬT RÚT GỌN GIẢI QUYẾT BÀI TOÁN NGƯỜI DU LỊCH 
Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Tư tưởng 
cơ bản của thuật toán là trong quá trình tìm kiếm lời giải, ta sẽ phân hoạch tập các phương án của 
bài toán thành hai hay nhiều tập con biểu diễn như một node của cây tìm kiếm và cố gắng bằng 
phép đánh giá cận các node, tìm cách loại bỏ những nhánh cây (những tập con các phương án của 
bài toán) mà ta biết chắc chắn không phương án tối ưu. Mặc dù trong trường hợp tồi nhất thuật 
toán sẽ trở thành duyệt toàn bộ, nhưng trong những trường hợp cụ thể nó có thể rút ngắn đáng kể 
thời gian tìm kiếm. Mục này sẽ thể hiện khác những tư tưởng của thuật toán nhánh cận vào việc 
giải quyết bài toán người du lịch. 
Xét bài toán người du lịch như đã được phát biểu. Gọi C = { cij: i, j = 1, 2,...n} là ma trận 
chi phí. Mỗi hành trình của người du lịch: 
Tπ(1)→Tπ(2)→...→Tπ(n)→Tπ(1) có thể viết lại dưới dạng: 
(π(1), π(2), π(2), π(3),..., π(n-1), π(n), π(n), π(1), trong đó mỗi thành phần: 
π(j-1), π(j) sẽ được gọi là một cạnh của hành trình. 
Khi tiến hành tìm kiếm lời giải bài toán người du lịch chúng ta phân tập các hành trình 
thành 2 tập con: Tập những hành trình chứa một cặp cạnh (i, j) nào đó còn tập kia gồm những 
hành trình không chứa cạnh này. Ta gọi việc làm đó là sự phân nhánh, mỗi tập con như vậy được 
gọi là một nhánh hay một node của cây tìm kiếm. Quá trình phân nhánh được minh hoạ bởi cây 
tìm kiếm như trong hình 4.3. 
 94 
Chương 4: Bài toán tối ưu 
(Hình 4.3) 
Tập tất cả các hành trình 
Hành trình chứa 
(i,j) 
Hành trình 
không chứa (i,j) 
Việc phân nhánh sẽ được thực hiện dựa trên một qui tắc heuristic nào đó cho phép ta rút ngắn 
quá trình tìm kiếm phương án tối ưu. Sau khi phân nhánh và tính cận dưới giá trị hàm mục tiêu trên 
mỗi tập con. Việc tìm kiếm sẽ tiếp tục trên tập con có giá trị cận dưới nhỏ hơn. Thủ tục này được 
tiếp tục cho đến khi ta nhận được một hành trình đầy đủ tức là một phương án cuả bài toán. Khi đó 
ta chỉ cần xét những tập con các phương án nào có cận dưới nhỏ hơn giá trị của hàm mục tiêu tại 
phương án đã tìm được. Quá trình phân nhánh và tính cận trên tập các phương án của bài toán thông 
thường cho phép rút ngắn một cách đáng kể quá trình tìm kiếm do ta loại được rất nhiều tập con 
chắc chắn không chứa phương án tối ưu. Sau đây, là m