Tổng hợp bài giảng môn Thuật toán ứng dụng_Thầy Phạm Quang Dũng| Trường Đại học Bách Khoa Hà Nội
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
Môn: Thuật toán ứng dụng
Trường: Đại học Bách Khoa Hà Nội
Thông tin:
Tác giả:
Preview text:
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