CHƯƠNG 4
CÁC THUẬT TOÁN TÌM KIẾM
I. KHÁI NIỆM TÌM KIẾM
1. Đặt vấn đề
CHÌA KHÓA CỦA TA ĐÂU?
2/37
I. KHÁI NIỆM TÌM KIẾM
2. Khái niệm
Tì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òng
Ta có hình ảnh của chùm chìa khóa
Gian phòng gồm nhiều đồ đạc
3/37
3. BÀI TOÁN TÌM KIẾM
Dữ liệu vào:
- 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)
Dữ liệu ra:
- 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.
a0
a1
a2
a3
a4
Dữ liệu vào:
5
1
6
8
2
Ví dụ:
Số x=6
1 (Tìm thấy x trong mảng a)
Dữ liệu ra:
4/37
II. CÁC THUẬT TOÁN TÌM KIẾM
Tì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ếm
5/37
II. CÁC THUẬT TOÁN TÌM KIẾM
Tù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ại
Tì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ếm
Tìm kiếm trên dãy đã sắp: dãy tìm kiếm đã
6/37
sắp theo thứ tự tăng dần của khóa tìm kiếm
1. TÌM KIẾM TRÊN DÃY CHƯA SẮP
Vớ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
??
7/37
1.1.TÌM KIẾM TUẦN TỰ
So sánh khóa của đối tượng cần tìm với khóa của
a. Ý tưởng :
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ếp
Lặp lại công việc trên cho đến khi gặp một đối tượng
đối tượng đầu tiên trong dãy.
có khóa bằng với khóa cần tìm (thành công) hoặc đã
8/37
hết các đối tượng trong dãy (không thành công)
1.1TÌM KIẾM TUẦN TỰ
b. Minh họa
a0 5
a1 1
a2 6
a3 8
a4 2
Ví dụ 1: Cho dãy số
Tìm số x=6 trong dãy
x
6
Tìm thấy x
i=1
i=2
i=0
5
1
6
8
2
9/37
1.1.TÌM KIẾM TUẦN TỰ
Việc tìm kiếm có thể minh họa như sau
i=0; a0=5 <> x=6; i=i+1;
Chuyển sang đối tượng kế tiếp
i=1; a1=1 <> x=6; i=i+1;
Chuyển sang đối tượng kế tiếp
i=2; a2=6 = x; Tìm thấy x
10/37
Tìm kiếm kết thúc thành công
TÌM KIẾM TUẦN TỰ
Ví dụ 2 Ví dụ 2
- Cho dãy số
a0
a1 a1
a2
a3
a4
a5
a6
a7
3 48 11 36 25 23 42 7
- Minh họa việc tìm số x1=42 và số x2=43 trong - Minh họa việc tìm số x1=42 và số x2=43 trong
11/37
dãy bằng phương pháp tìm kiếm tuần tự dãy bằng phương pháp tìm kiếm tuần tự
TÌM KIẾM TUẦN TỰ
begin
i=0
No
(i Yes No (i i=i+1 Yes return 1 return 0 Giải thuật 12/37 end int tktt(int x, int a[], int n) { int i=0; while(i if (i return 0; } 13/37 • Độ phức tạp của thuật toán : O(n) Nhận xét : mỗi lần so sánh đều phải kiểm tra xem Để tránh điều đó người ta thêm đối tượng x vào dãy đã hết chưa (i a0 a1 a2 a3 a4 5 1 6 8 2 cuối dãy a (gán a[n]=x) a0 a1 a2 a3 a4 a5 5 1 6 8 2 6 14/37 begin i=0; a[n]=x No (x!= a[i]) Yes No (i i=i+1 Yes return 1 return 0 Giải thuật 15/37 end int tktt2(int x, int a[], int n) { int i=0; a[n]=x; while(a[i]!=x) i++; if (i return 0; } 16/37 • Độ phức tạp của thuật toán : O(n) Với một dãy đã sắp xếp theo theo thứ tự của khóa tìm kiếm thì việc tìm kiếm về cơ bản sẽ nhanh hơn Việc tìm kiếm có thể thực hiện bằng một trong hai phương pháp Tìm kiếm tuần tự hoặc 17/37 Tìm kiếm nhị phân Việc tìm kiếm giống như tìm kiếm trên dãy chưa sắp Quá trình tìm kiếm kết thúc khi gặp một trong 3 điều kiện Gặp đối tượng có khóa bằng với khóa của đối tượng cần tìm (tìm kiếm thành công) Gặp đối tượng có khóa “lớn hơn” khóa của đối tượng cần tìm (tìm kiếm không thành) 18/37 Đã duyệt hết dãy (tìm kiếm không thành) a1 a1 a2 a3 a4 1 2 5 6 8 Ví dụ: Cho dãy số được
sắp tăng Tìm số x=4 trong dãy 4 1 2 5 6 8 19/37 Không tìm thấy x begin i=0; a[n]=x No ( a[i] No Yes Giải thuật i=i+1 Yes return 1 return 0 20/37 end int tktt3(int x, int a[], int n) { int i=0; a[n]=x; while ( a[i] if (i return 0; } 21/37 • Độ phức tạp của thuật toán : O(n) Ý tưởng So sánh khóa cần tìm với khóa của đối tượng ở trung tâm của dãy đang xét m=(l+r)/2 Tìm kiếm kết thúc thành công nếu a[m]==x
Nếu a[m] > 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] < x, tìm kiếm được thực hiện với dãy phải a[m+1], ..., a[r] 22/37 Quá trình tìm kiếm tiếp tục cho đến khi gặp đối
tượng mong muốn (thành công) hoặc dãy khóa đang
xét trở nên rỗng Ví dụ a0 a1 a2 a4 a4 1 2 5 6 8 23/37 Quá trình tìm kiếm được minh họa như sau Dãy đang xét 1 2 5 6 8 4 < a[m]=5 l=0, r=4, m=2 1 2 5 6 8 4 > a[m]=1 l=0, r=1, m=0 1 2 5 6 8 l=1, r=1, m=1 4 > a[m]=2 1 2 5 6 8 Trườ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ông 24/37 4 l=2, r=1 Ví dụ 2 a0 a1 a2 a3 a4 a5 a6 a7 3 7 11 23 25 36 42 48 25/37 dãy bằng phương pháp tìm kiếm nhị phân Giải thuật 26/37 int tknp(int x, int a[], int n) { int l=0, r=n-1, m ; while (l<=r) { m= (l+r)/2 ; if (a[m]==x) return 1; if (a[m] > x) r=m-1; else l=m+1 ; 27/37 }
return 0;
} Độ phức tạp : O(log2(n)) int tknp2(int x, int a[], int l, int r) { if (r m = (l+r)/2; if (a[m]==x) return 1; if (a[m]>x) return tknp2(x, a, l, m-1) return tknp2(x,a, m+1, r); 28/37 } • Ý tưởng : • Lưu dãy khóa vào cây nhị phân tìm kiếm • Nế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ông • Nế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ái • Nếu khóa gốc nhỏ hơn x lặp lại quá trình tìm kiếm 29/37 trong cây con bên phải Ví dụ 1 33 48 11 36 25 23 42 7 30/37 bằng phương pháp tì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 ứng • Tìm x=42 A t B • t->key • B->key>x, tìm trong cây C • C->key C • D->key=x, tìm thấy x, kết D thúc tìm kiếm 31/37 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; 32/37 } 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)) 33/37 Không thuận lợi là O(n) Bài 1 Nhập vào một mảng một chiều n số nguyên Viết chương trình thực hiện các việc sau Nhập số nguyên x Thông báo x có xuất hiện trong dãy không, nếu (0 có thì nó ở vị trí thứ bao nhiêu theo thuật toán 34/37 tìm kiếm tuần tự, tìm kiếm nhị phân Bài 2 Nhập vào cây nhị phân tìm kiếm n số nguyên Viết chương trình thực hiện các yêu cầu sau Nhập số nguyên x Thông báo x có trong cây hay không theo thuật (0 35/37 toán tìm kiếm trên cây nhị phân tìm kiếm Bài 3 Tự cho các dãy khóa nguyên (n>10), mô tả quá trình tìm kiếm khóa x trong dãy khóa theo các thuật 36/37 toán tìm kiếm đã họcTÌM KIẾM TUẦN TỰ
TÌM KIẾM TUẦN TỰ CẢI TIẾN
Ví dụ
TÌM KIẾM TUẦN TỰ CẢI TIẾN
TÌM KIẾM TUẦN TỰ CẢI TIẾN
TÌM KIẾM TRÊN DÃY ĐÃ SẮP
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
x
i=1
i=2
i=0
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
(i
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
TÌM KIẾM NHỊ PHÂN
TÌM KIẾM NHỊ PHÂN
- Cho dãy số được sắp tăng
- Tìm số x=4 trong dãy
TÌM KIẾM NHỊ PHÂN
x
x
x
x
TÌM KIẾM NHỊ PHÂN
- 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
TÌM KIẾM NHỊ PHÂN
begin
l = 0; r = n-1
Yes
(r
No
return 0
l = m+1
r = m-1
m=(l+r)/2
Yes
No
No
Yes
a[m]>x
a[m]==x
return 1
end
TÌM KIẾM NHỊ PHÂN
TÌM KIẾM NHỊ PHÂN
TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM
TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM
- Cho dãy số
- Minh họa việc tìm số x1=42 và số x2=43 trong dãy
TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM
33
11
48
25
7
36
42
23
TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM
TÌM KIẾM TRÊN CÂY NHỊ PHÂN TÌM KIẾM
BÀI TẬP ÁP DỤNG
BÀI TẬP ÁP DỤNG
BÀI TẬP ÁP DỤNG
