Page 1
goupee.vn goupee.com THUẬT TOÁN ỨNG DỤNG ĐỆ QUY QUAY LUI Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn 1 fb.com/goupee.vn
Contenu du document
Page 2
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 3
goupee.vn goupee.com Đệ 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 fb.com/goupee.vn
Page 4
goupee.vn goupee.com Đệ quy quay lui () x = v x = v x1 = vk 1 1 1 2 (v ) . . . . 1 x2 = u1 x = u 2 q . . . . (v ,u ) . . . . 1 q x = w x3 = wh 3 1 . . . . (v ,u ,w ) 1 q h . . . . 4 fb.com/goupee.vn
Page 5
goupee.vn goupee.com Đệ 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 fb.com/goupee.vn
Page 6
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 7
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 8
Liệt kê nghiệm nguyên dương của goupee.vn goupee.com 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 fb.com/goupee.vn
Page 9
Liệt kê nghiệm nguyên dương của goupee.vn goupee.com 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 fb.com/goupee.vn
Page 10
Liệt kê nghiệm nguyên dương của goupee.vn goupee.com 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 fb.com/goupee.vn
Page 11
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 12
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 13
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 14
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 15
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 16
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 17
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 18
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 19
goupee.vn goupee.com 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 fb.com/goupee.vn
Page 20
goupee.vn goupee.com 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 fb.com/goupee.vn
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !