Giới thiệu Các thuật toán tìm kiếm
Tìm kiếm trên quy hoạch động
Bài toán cái túi cơ bản
• Tìm kiếm bằng đệ quy
Sử dụng thuật toán đệ quy cho bài toán cái túi
• Tìm kiếm phân vùng tìm kiếm
Phân tích quá trình chia vùng tìm kiếm với bài toán cái túi
![Giới thiệu Các thuật toán tìm kiếm trang 1 Giới thiệu Các thuật toán tìm kiếm trang 1](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-1_11G6gPlvT6.jpg)
Trang 1
![Giới thiệu Các thuật toán tìm kiếm trang 2 Giới thiệu Các thuật toán tìm kiếm trang 2](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-2_FuD5W7svMp.jpg)
Trang 2
![Giới thiệu Các thuật toán tìm kiếm trang 3 Giới thiệu Các thuật toán tìm kiếm trang 3](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-3_KUTJadchVc.jpg)
Trang 3
![Giới thiệu Các thuật toán tìm kiếm trang 4 Giới thiệu Các thuật toán tìm kiếm trang 4](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-4_ObEXRzDHgV.jpg)
Trang 4
![Giới thiệu Các thuật toán tìm kiếm trang 5 Giới thiệu Các thuật toán tìm kiếm trang 5](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-5_3bQebgtZcP.jpg)
Trang 5
![Giới thiệu Các thuật toán tìm kiếm trang 6 Giới thiệu Các thuật toán tìm kiếm trang 6](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-6_qPvGrWm3z3.jpg)
Trang 6
![Giới thiệu Các thuật toán tìm kiếm trang 7 Giới thiệu Các thuật toán tìm kiếm trang 7](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-7_CtmJZxz5ab.jpg)
Trang 7
![Giới thiệu Các thuật toán tìm kiếm trang 8 Giới thiệu Các thuật toán tìm kiếm trang 8](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-8_YnBggk3mw5.jpg)
Trang 8
![Giới thiệu Các thuật toán tìm kiếm trang 9 Giới thiệu Các thuật toán tìm kiếm trang 9](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-9_320CCpaksY.jpg)
Trang 9
![Giới thiệu Các thuật toán tìm kiếm trang 10 Giới thiệu Các thuật toán tìm kiếm trang 10](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/image/2024/02/14/7314/gioi-thieu-cac-thuat-toan-tim-kiem-trang-10_1em7xA1Hui.jpg)
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Giới thiệu Các thuật toán tìm kiếm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Giới thiệu Các thuật toán tìm kiếm
![Giới thiệu Các thuật toán tìm kiếm Giới thiệu Các thuật toán tìm kiếm](https://s1.tailieuhoc.vn/4ydyqpyrc4869mas/thumb/2024/02/14/gioi-thieu-cac-thuat-toan-tim-kiem_OXu5Vl5rwt.jpg)
Giới thiệu Các thuật toán tìm kiếm 1 Nội dung trình bày • Bài toán tìm kiếm • Tìm kiếm tuần tự, tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân • Một số tiếp cận khác Tìm kiếm dựa trên quy hoạch động Tìm kiếm dựa trên đệ quy Tìm kiếm dựa trên phân vùng 2 Bài toán tìm kiếm mở rộng • Tìm kiếm trên quy hoạch động Bài toán cái túi cơ bản • Tìm kiếm bằng đệ quy Sử dụng thuật toán đệ quy cho bài toán cái túi • Tìm kiếm phân vùng tìm kiếm Phân tích quá trình chia vùng tìm kiếm với bài toán cái túi 3 Bài toán cái túi • Tìm kiếm phương án lấy đồ cho cái túi Một tên trộm mang túi có thể mang được trụng lượng là C Đến một ngôi nhà có N vật, mỗi vật có trọng lượng là là wi và có giá trị là pi Tìm các đồ vật mà tên trộm có thể lấy được mà có tổng giá trị lớn nhất 4 Bài toán cái túi • Tiếp cận quy hoạch động Dựa trên mô tả về U(k,i) = max(U(k-wk)+pk,U(k-1,i)) • Tiếp cận tổ hợp Sử dụng các phương án có thể, kiểm tra lấy giá trị lớn nhất (sử dụng đệ quy) 5 Bài toán cái túi • Thuật toán xây dựng phương án buildsolution • Input: T, w[N], p[N] • Output: Ma trận PA • for(i=T->w[0]) PA[0,i]=p[0]; • For(i=0->w[0]-1) PA[0,i]=0; 6 Bài toán cái túi • Thuật toán xây dựng phương án buildsolution (t) • For(i=1->N-1) For(j=T->w[i]) • PA[i,j]=max(PA[i-1,j], PA[i-1,j-w[i]]+p[i]) For(j=w[i]-1->0) • PA[i,j]=PA[i-1,j]; 7 Bài toán cái túi • Thuật toán xây dựng phương án getsolution • Input: PA[N,T], w[N], p[N] • Output: các vật cần lấy • i=N • j=T • While(i>0 &&j>0) If(PA[i,j]!PA[i-1,j]) • Print(i) • J=j-w[i]; i=i-1; • If(PA[i,j]!=0) print(i) 8 Bài toán cái túi • Xây dựng bảng các phương án 9 T=19 wi pi 1 3 7 2 4 10 3 5 20 4 7 19 5 6 13 6 9 40 Bài toán cái túi • Xây dựng bảng các phương án 10 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 1 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 2 0 0 7 10 10 10 17 17 17 17 17 17 17 17 17 17 17 17 3 0 0 7 10 20 20 20 27 30 30 30 37 37 37 37 37 37 37 4 0 0 7 10 20 20 20 27 30 30 30 39 39 46 49 49 49 56 5 0 0 7 10 20 20 20 27 30 30 33 39 40 46 49 49 52 56 6 0 0 7 10 20 20 20 27 40 40 47 50 60 60 60 67 70 70 Bài toán cái túi • Xây dựng bảng các phương án 11 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 1 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 2 0 0 7 10 10 10 17 17 17 17 17 17 17 17 17 17 17 17 3 0 0 7 10 20 20 20 27 30 30 30 37 37 37 37 37 37 37 4 0 0 7 10 20 20 20 27 30 30 30 39 39 46 49 49 49 56 5 0 0 7 10 20 20 20 27 30 30 33 39 40 46 49 49 52 56 6 0 0 7 10 20 20 20 27 40 40 47 50 60 60 60 67 70 70 Bài toán cái túi • Tiếp cận đệ quy Sinh tổ hợp để xét 12 Bài toán cái túi • Phân tích xu hướng phân vùng để tìm kiếm với bài toán cái túi 13 14 Bài tập - Cài đặt thuật toán trên ngôn ngữ lập trình và chạy thử
File đính kèm:
gioi_thieu_cac_thuat_toan_tim_kiem.pdf