Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4: Các thuật toán tìm kiếm

CHƯƠNG 4CÁC THUẬT TOÁN TÌM KIẾM2/37I. KHÁI NIỆM TÌM KIẾM1. Đặt vấn đềCHÌA KHÓA CỦA TA ĐÂU?3/37I. KHÁI NIỆM TÌM KIẾM 2. Khái niệmTìm kiếm là việc kiểm tra xem có hay không một đối tượng có một số thông tin cho trước (đối tượng cần tìm) trong một tập các đối tượng cho trước (không gian tìm kiếm)Ví dụ: Tìm một chùm chìa khóa trong một gian phòngTa có hình ảnh của chùm chìa khóaGian phòng gồm nhiều đồ đạc4/373. BÀI TOÁN TÌM KIẾM Dãy a, có n đối tượng, mỗi đối tượng có một “khóa tìm kiếm” Khóa của đối tượng cần tìm (Key)- Nếu tìm thấy đối tượng có khóa ‘Key’ trong dãy a trả lại giá trị 1, ngược lại trả lại giá trị 0.Dữ liệu vào:Dữ liệu ra:Ví dụ:51682Dữ liệu vào:a0a1a2a3a4Số x=6Dữ liệu ra:1 (Tìm thấy x trong mảng a)5/37II. CÁC THUẬT TOÁN TÌM KIẾMTìm kiếm tuần tựTìm kiếm nhị phân Tìm kiếm trên cây nhị phân tìm kiếm6/37II. CÁC THUẬT TOÁN TÌM KIẾMTùy theo dữ liệu vào ta có thể phân chia bài toán tìm kiếm thành hại loạiTìm kiếm trên dãy chưa sắp: dãy tìm kiếm chưa được sắp xếp theo thứ tự khóa tìm kiếmTìm kiếm trên dãy đã sắp: dãy tìm kiếm đã sắp theo thứ tự tăng dần của khóa tìm kiếm 7/371. TÌM KIẾM TRÊN DÃY CHƯA SẮPVới một dãy chưa được sắp xếp thì cách tìm kiếm đơn giản nhất là tìm kiếm tuần tựTìm kiếm tuần tự là một phương pháp tìm kiếm khá phổ biến và hết sức đơn giản??8/371.1.TÌM KIẾM TUẦN TỰa. Ý tưởng :So sánh khóa của đối tượng cần tìm với khóa của đối tượng đầu tiên trong dãy.Nếu bằng nhau, kết thúc tìm kiếm (thành công)Nếu không bằng, chuyển sang đối tượng kế tiếpLặp lại công việc trên cho đến khi gặp một đối tượng có khóa bằng với khóa cần tìm (thành công) hoặc đã hết các đối tượng trong dãy (không thành công) 9/371.1TÌM KIẾM TUẦN TỰb. Minh họa51682a0a1a2a3a4Tìm số x=6 trong dãyVí dụ 1: Cho dãy sối=051682x6i=1i=2Tìm thấy x10/371.1.TÌM KIẾM TUẦN TỰViệc tìm kiếm có thể minh họa như saui=0; a0=5 x=6; i=i+1; i=1; a1=1 x=6; i=i+1;i=2; a2=6 = x; Tìm thấy xTìm kiếm kết thúc thành côngChuyển sang đối tượng kế tiếpChuyển sang đối tượng kế tiếp11/37Ví dụ 2TÌM KIẾM TUẦN TỰ34811362523427a0a1a2a3a4- Cho dãy số - Minh họa việc tìm số x1=42 và số x2=43 trong dãy bằng phương pháp tìm kiếm tuần tựa5a6a7Ví dụ 2a1- Minh họa việc tìm số x1=42 và số x2=43 trong dãy bằng phương pháp tìm kiếm tuần tự12/37Giải thuậtTÌM KIẾM TUẦN TỰi=0(i x, tìm kiếm được thực hiện với dãy trái a[l], ..., a[m-1]Nếu a[m] a[m]=112568l=1, r=1, m=1x4>a[m]=2x412568l=2, r=1Trường hợp dãy đang xét trở nên rỗng vì thế tìm kiếm kết thúc không thành công25/37Ví dụ 2TÌM KIẾM NHỊ PHÂN37112325364248a0a1a2a3a4- Cho dãy số a được sắp tăng dần- Minh họa việc tìm số x1=11 và số x2=37 trong dãy bằng phương pháp tìm kiếm nhị phâna5a6a726/37Giải thuật TÌM KIẾM NHỊ PHÂNbegin(rxreturn 0return 1YesYesYesNoNol = 0; r = n-1 r = m-1l = m+1endNo27/37TÌM KIẾM NHỊ PHÂNint tknp(int x, int a[], int n) { int l=0, r=n-1, m ; while (l x) r=m-1; else l=m+1 ; } return 0; } Độ phức tạp : O(log2(n))28/37TÌM KIẾM NHỊ PHÂNint tknp2(int x, int a[], int l, int r) { if (rx) return tknp2(x, a, l, m-1) return tknp2(x,a, m+1, r); }29/37TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM Ý tưởng :Lưu dãy khóa vào cây nhị phân tìm kiếmNếu t rỗng kết thúc tìm kiếm So sánh x với khóa gốc nếu bằng nhau tìm kiếm thành côngNếu khóa gốc lớn hơn x lặp lại quá trình tìm kiếm trong cây con bên tráiNếu khóa gốc nhỏ hơn x lặp lại quá trình tìm kiếm trong cây con bên phải30/37TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM 334811362523427- Cho dãy số Ví dụ 1- Minh họa việc tìm số x1=42 và số x2=43 trong dãy bằng phương pháp tìm kiếm trên cây nhị phân tìm kiếm31/37TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM Cây nhị phân tìm kiếm tương ứng334825113672342tABCD Tìm x=42 t->keykey>x, tìm trong cây C C->keykey=x, tìm thấy x, kết thúc tìm kiếm32/37TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM int tkcnp(int x, node *t ) { while (t!=NULL) { if (t->key==x) return 1; if (t->key>x) t= t->left ; else t=t->right ; } return 0; }33/37TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM int tkcnp2(int x, node *t ) { if (t=NULL) return 0; if (t->key==x) return 1; if (t->key>x) return tkcnp2(x, t->left) return tkcnp2(x,t->right); }Độ phức tạp : Thuận lợi là O(log2(n)) Không thuận lợi là O(n)34/37Bài 1 Viết chương trình thực hiện các việc sauNhập vào một mảng một chiều n số nguyên (010), mô tả quá trình tìm kiếm khóa x trong dãy khóa theo các thuật toán tìm kiếm đã học BÀI TẬP ÁP DỤNG