Bài giảng Thuật toán ứng dụng: Bài thực hành số 2 - TS. Bùi Quốc Trung, TA. Đặng Xuân Vương

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST

Báo xấu

7
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài thực hành "Thuật toán ứng dụng - Bài thực hành số 2: Tìm kiếm vét cạn" hướng dẫn sinh viên áp dụng phương pháp tìm kiếm vét cạn để giải quyết các bài toán tối ưu hóa. Bài thực hành bao gồm lý thuyết tìm kiếm vét cạn và các ví dụ cụ thể như CVRPCOUNT, BCA, TSP, CBUS và TAXI, giúp sinh viên hiểu rõ hơn về thuật toán và cách áp dụng vào thực tế. Sinh viên sẽ được thực hành trên các bài toán kinh điển này. Mời các bạn cùng tham khảo bài giảng để biết thêm chi tiết!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Thuật toán ứng dụng: Bài thực hành số 2 - TS. Bùi Quốc Trung, TA. Đặng Xuân Vương

Thuật toán ứng dụng Bài thực hành số 2: Tìm kiếm vét cạn TS. Bùi Quốc Trung, TA. Đặng Xuân Vương Trường Đại học Bách khoa Hà Nội Viện Công nghệ thông tin và Truyền thông Ngày 6 tháng 4 năm 2021 TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 1 / 39
Mục lục 1 Lý thuyết 2 CVRPCOUNT 3 BCA 4 TSP 5 CBUS 6 TAXI TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 2 / 39
Mục lục 1 Lý thuyết 2 CVRPCOUNT 3 BCA 4 TSP 5 CBUS 6 TAXI TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 3 / 39
Cách thực thi chương trình Sử dụng vòng lặp, i.e for loop, while loop,... Sử dụng hàm đệ quy ... TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 4 / 39
Mô hình giải bài Tìm kiếm vét cạn: Thử mọi cấu hình có thể của lời giải và chọn ra cấu hình phù hợp nhất. Tham lam Chia để trị Quy hoạch động ... TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 5 / 39
Tìm kiếm vét cạn Liệt kê lời giải Trực tiếp sinh ra cấu hình đầy đủ của lời giải từ cấu hình trước đó. Thường được thực hiện bằng vòng lặp. Ví dụ: Bài toán cái túi (liệt kê các dãy nhị phân độ dài n), Bài toán người du lịch (liệt kê các hoán vị của n số tự nhiên đầu tiên),... Quay lui Cấu hình lời giải được sinh từng phần, thường có trình tự. Nếu không thể tiếp tục sinh lời giải thì quay về bước trước (quay lui). Thường thực hiện bằng hàm đệ quy. Có thể tối ưu bằng kỹ thuật nhánh và cận. ... TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 6 / 39
Chú ý Tìm kiếm vét cạn = Đệ quy = Quay lui = Nhánh và cận TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 7 / 39
Đệ quy quay lui - cách 1 1 2 void _try ( x ) { 3 // x la phan cau hinh loi giai can duoc bo sung 4 if ( x thuoc neo de quy ) { 5 Xu ly va thoat ham de quy ; 6 } 7 Duyet tung kha nang ( i ) { 8 Neu kiem_tra (x , i ) { 9 // Kiem tra dieu kien va can 0 Luu trang thai hien tai ; 1 Cap nhat trang thai ; 2 _try ( x_ ); 3 // x_ la phan cau hinh tiep theo 4 Khoi phuc trang thai hien tai ; // Quay lui 5 } 6 } 7 } TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 8 / 39
Đệ quy quay lui - cách 2 8 9 void _try (x , s ) { 0 // x la phan cau hinh loi giai can duoc bo sung 1 // s la trang thai hien tai 2 if ( x thuoc neo de quy ) { 3 Xu ly va thoat ham de quy ; 4 } 5 Duyet tung kha nang ( i ) { 6 Neu kiem_tra (x , s , i ) { 7 // Kiem tra dieu kien va can 8 _try ( x_ , s_ ); 9 // x_ la phan cau hinh tiep theo 0 // s_ la trang thai sau khi gan i cho x 1 } 2 } 3 } TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 9 / 39
Mục lục 1 Lý thuyết 2 CVRPCOUNT 3 BCA 4 TSP 5 CBUS 6 TAXI TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 10 / 39
Đề bài Có K xe tải giống hệt nhau, mỗi xe chứa tối đa Q gói hàng. Có n khách hàng, khách hàng i yêu cầu d[i] gói hàng. Mỗi khách hàng được phục vụ bởi đúng 1 xe. Mỗi xe phục vụ tối thiểu 1 khách hàng. Yêu cầu: Đếm số cách sắp xếp lộ trình các xe để phục vụ các khách hàng theo yêu cầu. TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 11 / 39
Thuật toán Gọi x[i] là xe tải phục vụ khách hàng i, x[i] ∈ [0..K − 1]. Thử mọi trường hợp của x[i], ∀i ∈ [0..n − 1] và kiểm tra các ràng buộc. Với mỗi cách chọn x[i], ∀i ∈ [0..n − 1] hợp lệ, gọi c[k] là số khách hàng xe thứ k phục vụ, ta có thêm K −1 c[k]! cách xếp lộ trình cho k=0 xe. Vì các xe tải giống hệt nhau, cần chia số kết quả cho k!. TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 12 / 39
Code 1 void _try ( int i ) { 2 if ( i == n ) { 3 int tmp = 1; 4 for ( int k = 0; k < K ; k ++) { 5 tmp *= custom_factorial ( c [ k ]); 6 } 7 res += tmp ; 8 return ; 9 } 0 for ( int k = 0; k < K ; k ++) { 1 if ( q [ k ] >= d [ i ]) { 2 q [ k ] -= d [ i ]; // init : q [ k ] = Q 3 c [ k ]++; // init : c [ k ] = 0 4 _try ( i +1); 5 q [ k ] += d [ i ]; 6 c [ k ] - -; 7 } 8 } 9 } TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 13 / 39
Mục lục 1 Lý thuyết 2 CVRPCOUNT 3 BCA 4 TSP 5 CBUS 6 TAXI TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 14 / 39
Đề bài Có n môn học và m giáo viên, mỗi giáo viên chỉ có thể dạy các môn trong danh sách cho trước. Các môn học trùng giờ không thể được dạy bởi cùng một giáo viên. Tải của một giáo viên là số khóa học giáo viên phải dạy. Yêu cầu: Tìm cách xếp lịch để tải của giáo viên có tải cao nhất là nhỏ nhất. TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 15 / 39
Thuật toán Gọi x[i] là giáo viên sẽ dạy môn i. Thử mọi trường hợp của x[i], i ∈ [0..n] và kiểm tra các ràng buộc cũng như tải của giáo viên. Kết hợp nhánh cận: Nếu tải lớn nhất hiện tại lớn hơn hoặc bằng lời giải tốt nhất, ta cắt nhánh. TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 16 / 39
Code 0 void _try ( int x ) { 1 if ( x == n ) { 2 res = min ( res , curLoad ); 3 return ; 4 } 5 for ( int i = 0; i < m ; i ++) { 6 if ( check (i , x )) { 7 int oldLoad = curLoad ; 8 t [ i ][ x ] = 1; // Giao vien i day mon x 9 l [ i ]++; // Tai cua giao vien i 0 curLoad = max ( curLoad , l [ i ]); 1 _try ( x +1); 2 t [ i ][ x ] = 0; 3 l [ i ] - -; 4 curLoad = oldLoad ; 5 } 6 } 7 } TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 17 / 39
Code 8 bool check ( int i , int x ) { 9 if (( a [ i ][ x ] == 0) || ( l [ i ] + 1 >= res )) { 0 return false ; 1 } 2 for ( int j = 0; j < o [ x ]. size (); j ++) { 3 if (( t [ i ][ o [ x ][ j ]] == 1)) { 4 return false ; 5 } 6 } 7 return true ; 8 } TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 18 / 39
Mục lục 1 Lý thuyết 2 CVRPCOUNT 3 BCA 4 TSP 5 CBUS 6 TAXI TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 19 / 39
Đề bài Cho một đồ thị đầy đủ có trọng số. Yêu cầu: Tìm một cách di chuyển qua mỗi đỉnh đúng một lần và quay về đỉnh xuất phát sao cho tổng trọng số các cạnh đi qua là nhỏ nhất (chu trình hamilton nhỏ nhất). TrungBQ, VuongDX (HUST) Tìm kiếm vét cạn Ngày 6 tháng 4 năm 2021 20 / 39