›
›

Bài giảng Thuật toán ứng dụng - Chương 3: Đệ quy quay lui - Phạm Quang Dũng

Download
THUẬT TOÁN ỨNG DỤNG  
ĐỆ QUY QUAY LUI  
Phạm Quang Dũng  
Bộ mô n KHMT  
[email protected].vn  
1
NộI dung  
Đệ quy quay lui  
Tổng quan đệ quy quay lui  
Bài toá n liệt kê xâ u nhị phâ n  
Bài toá n liệt kê nghiệm nguyên dương phương trì nh tuyến tí nh  
Bài toá n liệt kê TSP  
Bài toá n liệt kê hành trì nh taxi  
Bài toá n liệt kê CBUS  
Bài toá n liệt kê BCA  
Bài toá n liệt kê CVRP  
Thuật toá n nhá nh và cận  
Tổng quan nhá nh và cận  
Bài toá n tối ưu TSP  
Bài toá n tối ưu hành trì nh taxi  
Bài toá n tối ưu CBUS  
Bài toá n tối ưu BCA  
Bài toá n tối ưu CVRP  
2
Đệ quy quay lui  
Phương phá p dùng để liệt kê cá c cấu hì nh tổ hợp cũng  
như giải bài toá n tối ưu tổ hợp  
Liệt kê: liệt kê tất cả cá c bộ x = (x1,x2,…, xN) trong đó xi  
Ai - tập rời rạc, đồng thời (x1,x2,..., xN) thỏa mã n cá c ràng  
buộc C cho trước  
Tối ưu tổ hợp: trong số cá c bộ (phương á n) x = (x1,x2,…,  
xN) trong đó xi Ai - tập rời rạc, đồng thời (x1,x2,..., xN)  
thỏa mã n cá c ràng buộc C cho trước, cần tì m phương á n  
có f(x) → min(max)  
Thử lần lượt từng giá trị cho mỗi biến  
Chiến lược chọn biến, ví dụ x1, x2, x3,…, xN  
Chiến lược chọn giá trị cho biến, ví dụ từ nhỏ đến lớn  
hoặc ngược lại  
3
Đệ quy quay lui  
()  
x1 = vk  
x1 = v1  
x1 = v2  
. . . .  
(v1)  
x2 = uq  
x2 = u1  
. . . .  
. . . .  
(v1,uq)  
x3 = wh  
. . . .  
. . . .  
x3 = w1  
(v1,uq, wh)  
4
Đệ quy quay lui  
Tại mỗi thời điểm, ta có phương án bộ phận (x1 = v1, x2 = v2,  
…, xk-1 = vk-1) → cần thử duyệt tiếp các khả năng cho xk ?  
try(k){// thử giá trị cho xk  
forall v Ak do{  
if(check(v,k)) then{// kiểm tra ràng buộc C của bài toán  
xk = v;  
[cập nhật các cấu trúc dữ liệu liên quan]  
if(k = N) then solution();  
else try(k+1);  
[khôi phục trạng thái các cấu trúc dữ liệu khi quay lui]  
}
}
}
5
Liệt kê xâ u nhị phâ n độ dài N  
#include <iostream>  
using namespace std;  
#define MAX 100  
int N;  
int x[MAX];// bieu dien loi phuong an cua bai toan  
bool check(int v, int k){  
return true;  
}
void solution(){  
for(int i = 1; i <= N; i++) cout << x[i] << " "; cout << endl;  
}
6
Liệt kê xâ u nhị phâ n độ dài N  
void TRY(int k){  
for(int v = 0; v <= 1; v++){  
if(check(v,k)){  
x[k] = v;  
if(k == N) solution();  
else TRY(k+1);  
}
}
}
int main(){  
N = 3;  
TRY(1);// bat dau thu gia tri cho x[1]  
}
7
Liệt kê nghiệm nguyên dương của  
phương trì nh tuyến tí nh  
X1 + X2 + . . . + Xn = M  
Phương á n bộ phận (X1, …, Xk-1) có tổng bộ phận là T  
Khởi tạo  
Phương á n bộ phận rỗng: (), T = 0  
Thử giá trị cho Xk  
X1 + X2 + … + Xk-1 + Xk + Xk+ 1 + . . . + Xn = M  
Xk = M – T – (Xk+1 + Xk+2 + … + Xn)  
1 ≤ Xk ≤ M – T – (n - k)  
8
Liệt kê nghiệm nguyên dương của  
phương trì nh tuyến tí nh  
X1 + X2 + . . . + Xn = M  
#include <stdio.h>  
#define MAX 100  
int n,M;  
int X[MAX];  
int T;// accumulated sum  
int check(int v, int k){  
if(k < n) return 1;  
return T + v == M;  
}
void solution(){  
for(int i = 1; i <= n; i++) printf("%d ",X[i]); printf("\n");  
}
9
Liệt kê nghiệm nguyên dương của  
phương trì nh tuyến tí nh  
void TRY(int k){  
for(int v = 1; v <= M-T - n+k; v++){  
if(check(v,k)){  
X[k] = v;  
T = T + X[k];// update incrementally  
if(k == n) solution();  
else TRY(k+1);  
T = T - X[k];// recover when backtracking  
}
}
}
int main(){  
n = 6; M = 15;  
T = 0;  
TRY(1);  
}
10  
Liệt kê hành trì nh giao hàng  
Một shipper nhận hàng từ cửa hàng (điểm 0) và phải đi  
qua tất cả N khá ch hàng 1, 2, 3, . . ., N (mỗi khá ch  
hàng đi qua đúng 1 lần) để giao hàng. Hã y liệt kê tất  
cả cá c phương á n cho shipper  
11  
Liệt kê hành trì nh giao hàng  
#include <bits/stdc++.h>  
#define MAX 100  
using namespace std;  
int N;  
int X[MAX];// permutation 1,2,...,N  
int appear[MAX];// appear[v] = 1 indicates that v has appeared  
void solution(){  
for(int i = 1; i <= N; i++) cout << X[i] << " "; cout << endl;  
}
bool check(int v, int k){  
return appear[v] == 0;  
}
12  
Liệt kê hành trì nh giao hàng  
void TRY(int k){// thu gia tri cho X[k]  
for(int v = 1; v <= N; v++){  
if(check(v,k)){  
X[k] = v;  
appear[v] = 1;// update  
if(k == N) solution();  
else TRY(k+1);  
appear[v] = 0;// recover  
}
}
}
int main(){  
N = 3;  
for(int v = 1; v <= N; v++) appear[v] = 0;  
TRY(1);  
}
13  
Liệt kê hành trì nh đón trả khá ch cho taxi  
Một taxi xuất phá t từ điểm 0 và cần phục vụ đón trả N  
khá ch 1, 2, …, N. Khá ch thứ i có điểm đón là i và điểm  
trả là N+i. Hã y liệt kê tất cả cá c phương á n đón trả cho  
taxi.  
Giải phá p  
Đưa về bài toá n liệt kê hoá n vị  
Do tí nh chất vận chuyển taxi nên điểm i sẽ nằm ngay  
trước điểm i+N trên mỗi hoá n vị của 1, 2, …, 2N  
→ mỗi hoá n vị của 1, 2, …, N, chè n thêm i+N vào ngay sau  
giá trị i (với mọi i = 1, 2, …, N)  
14  
Liệt kê hành trì nh đón trả khá ch cho taxi  
#include <bits/stdc++.h>  
#define MAX 100  
using namespace std;  
int N;  
int X[MAX];// permutation 1,2,...,N  
int appear[MAX];// appear[v] = 1 indicates that v has appeared  
void solution(){  
for(int i = 1; i <= N; i++)  
cout << X[i] << " " << X[i] + N << " ";  
cout << endl;  
}
bool check(int v, int k){  
return appear[v] == 0;  
}
15  
Liệt kê hành trì nh đón trả khá ch cho taxi  
void TRY(int k){// thu gia tri cho X[k]  
for(int v = 1; v <= N; v++){  
if(check(v,k)){  
X[k] = v;  
appear[v] = 1;// update  
if(k == N) solution();  
else TRY(k+1);  
appear[v] = 0;// recover  
}
}
}
int main(){  
N = 3;  
for(int v = 1; v <= N; v++) appear[v] = 0;  
TRY(1);  
}
16  
Liệt kê hành trì nh đón trả khá ch cho bus  
Một xe bus xuất phá t từ điểm 0 và cần phục vụ đón trả  
N khá ch 1, 2, …, N. Khá ch thứ i có điểm đón là i và  
điểm trả là N+i. Xe bus chở được tối đa Q khá ch cùng  
một lúc. Hã y liệt kê tất cả cá c phương á n đón trả cho  
xe bus.  
17  
Liệt kê hành trì nh đón trả khá ch cho bus  
Một xe bus xuất phá t từ điểm 0 và cần phục vụ đón trả  
N khá ch 1, 2, …, N. Khá ch thứ i có điểm đón là i và  
điểm trả là N+i. Xe bus chở được tối đa Q khá ch cùng  
một lúc. Hã y liệt kê tất cả cá c phương á n đón trả cho  
xe bus.  
Thiết kế giải phá p  
Kiểm soá t số hành khá ch trên xe bằng biến q: số khá ch  
đang có mặt trên xe  
Mỗi khi hành trì nh đi qua 1 điểm đón thì tăng q lên 1  
Mỗi khi hành trì nh đi qua 1 điểm trả thì giảm q đi 1 đơn vị  
18  
Liệt kê hành trì nh đón trả khá ch cho bus  
#include <bits/stdc++.h>  
using namespace std;  
#define MAX_N 100  
int N;// so khach  
int Q;// so cho tren bus cho hanh khach  
int X[2*MAX_N + 1];// bieu dien phuong an lo trinh X[1], X[2], . . . X[2N]  
int q;// so khach thuc su dang co tren xe ung voi phuong an bo phan hien tai  
bool appear[2*MAX_N+1];  
bool check(int v, int k){  
if(appear[v]) return false;  
if(v <= N){// v is pickup  
if(q >= Q) return false;  
}else{// v > N means drop-off  
if(!appear[v-N]) return false;  
}
return true;  
}
19  
Liệt kê hành trì nh đón trả khá ch cho bus  
void solution(){  
for(int i = 1; i <= 2*N; i++) cout << X[i] << " "; cout << endl;  
}
void TRY(int k){// thu gia tri cho X[k]  
for(int v = 1; v <= 2*N; v++){  
if(check(v,k)){  
X[k] = v;  
appear[v] = true;  
if(v <= N) q++; else q--;// update q incrementally  
if(k == 2*N) solution();  
else TRY(k+1);  
appear[v] = false;  
if(v <= N) q--; else q++;// recover status q  
}
}
}
20  
Tải về để xem bản đầy đủ
pdf 66 trang Thùy Anh 20660 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán ứng dụng - Chương 3: Đệ quy quay lui - Phạm Quang Dũng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_thuat_toan_ung_dung_chuong_3_de_quy_quay_lui_pham.pdf