THUẬT TOÁN ỨNG DỤNG
CẤU TRÚC DỮ LIỆU VÀ THƯ VIỆN Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn 1 NộI dung  Danh sách tuyến tính  Tập hợp  Ánh xạ  Ngăn xếp  Hàng đợi  Sắp xếp 2 Danh sách tuyến tính
 Lưu trữ các đối tượng theo quan hệ tuyến tính (trước – sau)
 Thao tác: thêm, xóa, tìm kiếm 3 List #include using namespace std; int main(){ list L;
for(int i = 1; i<=5;i++){ L.push_back(i); } list::iterator it;
it = find(L.begin(),L.end(),3); L.insert(it,10);
for(it = L.begin(); it != L.end(); it++){
cout << *it << endl; } } 4 Vector #include using namespace std; int main(){
vector V(3,100); // initialize 3 elements 100
for(int v = 0; v <= 10; v++) V.push_back(v); cout << "vector: ";
for(int i = 0; i < V.size(); i++){
cout << V[i] << " "; } } 5 Tập hợp
 Lưu các đối tượng, không trùng nhau
 Thao tác: thêm, xóa, tìm kiếm 6 Tập hợp #include using namespace std; int main(){ set Y;
for(int i = 1; i <= 10; i++){ Y.insert(i); }
for(set::iterator it = Y.begin(); it != Y.end(); it++){
cout << *it << endl; } if(Y.find(7) != Y.end())
cout << "Y contains 7" << endl; else
cout << "Y does not contains 7" << endl; } 7 Ánh xạ
 Cấu trúc dữ liệu cất trữ các cặp (khóa, giá trị)
 Phục vụ tìm kiếm nhanh với khóa đầu vào 8 Ánh xạ #include using namespace std; int main(){ map m; for(int i = 1; i <= 5; i++) m.insert(pair(i,10*i)); m[6] = 100;
for(int k = 1; k <= 6; k++) cout << m[k] << endl; map m1; m1["abc"] = "abcabc"; m1["xyz"] = "xyzxyz"; string s = "abc";
cout << m1[s] << endl; } 9 Ánh xạ #include using namespace std; int main(){ map, pair > m2; m2[pair(2,5)] = pair(20,50);
m2[pair(3,5)] = pair(30,50); int i = 3; int j = 5; pair p = m2[pair(i,j)];
cout << p.first << "," << p.second << endl; } 10 Ngăn xếp
 Cấu trúc dữ liệu cất trữ các đối tượng một cách tuyến tính  Thao tác  Thêm 1 phần tử  Lấy ra 1 phần tử
 Nguyên tắc: Vào trước – ra sau 11 Hàng đợi
 Cấu trúc dữ liệu cất trữ các đối tượng một cách tuyến tính  Thao tác  Thêm 1 phần tử  Lấy ra 1 phần tử
 Nguyên tắc: vào trước – ra trước 12 Stack #include using namespace std; int main(){ stack S;
for(int i = 0; i < 5; i++){ S.push(i); } while(!S.empty()){ int v = S.top(); S.pop();
cout << v << endl; }} 13 Queue #include using namespace std; int main(){ queue Q;
for(int i = 0; i < 5; i++){ Q.push(i); } while(!Q.empty()){ int v = Q.front(); Q.pop();
cout << v << endl; } } 14 Sắp xếp #include #include using namespace std; int main(){ int N = 6;
double a[N] = {1.1, 5.5, 7.7, 2.2, 8.8, 3.3};
sort(a+3,a+N,greater());// decreasing order
for(int i = 0; i < N; i++) cout << a[i] << " "; cout << endl; sort(a,a+N);
for(int i = 0; i < N; i++) cout << a[i] << " "; } 15 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 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 = (x ,x ,…, x ) trong đó x  1 2 N i
A - tập rời rạc, đồng thời (x ,x ,..., x ) thỏa mãn các ràng i 1 2 N buộc C cho trước
 Tối ưu tổ hợp: trong số các bộ (phương án) x = (x ,x ,…, 1 2
x ) trong đó x  A - tập rời rạc, đồng thời (x ,x ,..., x ) N i i 1 2 N
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ụ x , x , x ,…, x 1 2 3 N
 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 () x = v x = v 1 1 x = v 1 k 1 2 (v ) . . . . 1 x = u 2 1 x = u 2 q . . . . . . . . (v ,u ) 1 q x = w x = w 3 1 3 h . . . .
(v ,u , w ) 1 q h . . . . 4 Đệ quy quay lui
 Tại mỗi thời điểm, ta có phương án bộ phận (x = v , x = v , 1 1 2 2
…, x = v ) → cần thử duyệt tiếp các khả năng cho x ? k-1 k-1 k
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