Xem mẫu
- Chương 2 (1) : Giải Thuật Tìm Kiếm
Giảng viên : Nguyễn Minh Thành
Email : thanhnm@itc.edu.vn
- Nội Dung
I. Giới thiệu
II. Giải thuật tìm kiếm
III. Tìm kiếm tuyến tính
IV. Tìm kiếm nhị phân
2 Nguyễn Minh Thành
- I. Giới Thiệu
Tìm kiếm : là duyệt một danh sách và lấy ra phần tử thoả tiêu
chuẩn cho trước
Là một thao tác phổ biến trên máy tính và trong các ứng dụng
Tìm kiếm 1 dòng trong CSDL
Tìm kiếm hồ sơ, tập tin
Tìm kiếm 1 người trong một danh sách
…
Việc tìm kiếm nhanh thông tin trong một lượng lớn thông tin là
một điều cần thiết.
Các giải thuật tìm kiếm
3 Nguyễn Minh Thành
- II. Giải thuật tìm kiếm
Khảo sát việc tìm kiếm thường trên mảng và danh sách.
Có nhiều loại :
Tìm kiếm tuyến tính (tuần tự)
Tìm kiếm nhị phân
…
Cấu trúc :
Input
Mảng A gồm n phần tử
Giá trị x cần tìm
Output
Vị trí x trong A hoặc -1 nếu không tồn tại x
Thao tác cơ bản
4 So sánh
Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính
Có 2 loại tìm kiếm tuyến tính :
Vét cạn (exhaustive)
Dùng lính canh (sentinel)
5 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Vét Cạn
Thuật toán :
Lần lượt so sánh x với các phần tử của mảng A cho đến khi
gặp được phần tử cần tìm, hoặc hết mảng.
Ví dụ: A = {1, 25, 6, 5, 2, 37, 40}, x = 6
6 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Vét Cạn
Cài đặt 1 :
int LinearExhaustive(int a[], int N, int x)
{
int i=0;
while ((i
- III. Tìm Kiếm Tuyến Tính – Vét Cạn
Cài đặt 2 :
int LinearExhaustive(intA[], intn, intx)
{
for(int i=0; i
- III. Tìm Kiếm Tuyến Tính – Vét Cạn
Phép so sánh là phép toán sơ cấp được dùng trong thuật toán->
số lượng các phép so sánh sẽ là thước đo độ phức tạp của thuật
toán.
Mỗi vòng lặp có 2 điều kiện cần kiểm tra:
Kiểm tra cuối mảng
Kiểm tra phần tử hiện tại có bằng x hay không?
Trường hợp xấu nhất nằm ở cuối mảng A
Ta có 2*n+1 số phép so sánh
=> Số phép so sánh tăng/giảm tuyến tính theo số phần tử
Vậy độ phức tạp của thuật toán là : O(n)
9 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Lính Căn
Trong thuật toán vét cạn, có 2 điều kiện được kiểm tra:
Có thể bỏ việc kiểm tra điều kiện cuối mảng bằng cách dùng
“lính canh”.
Lính canh là phần tử có giá trị bằng với phần tử cần tìm và đặt
ở cuối mảng.
Thuật toán lính căn
10 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Lính Căn
Thuật toán lính căn
Tìm tuần tự từ đầu mảng cho đến khi tìm thấy x (chắc chắn sẽ
tìm thấy x)
Nếu x được tìm thấy tại vị trí lính canh thì x không thuộc mảng
A.
Ngược lại trả về vị trí của x trong mảng A.
11 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Lính Căn
Cài đặt 1 :
int LinearSentinel(int a[],int N,int x)
{ int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]
a[N] = x; // thêm phần tử thứ N+1
while (a[i]!=x )
i++;
if (i==N)
return -1; // tìm hết mảng nhưng không có x
else
return i; // tìm thấy x tại vị trí i
}
12 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Lính Căn
Cài đặt 2 :
int LinearSentinel(int a[], int n, int x)
{
a[n] = x; //đặtlínhcanh
for (int i=0; ;i++)
if (a[i] == x) break;
if(i==n) i=-1;
return i;
}
13 Nguyễn Minh Thành
- III. Tìm Kiếm Tuyến Tính – Lính Căn
Số phép so sánh trong trường hợp xấu nhất : n+2
Vậy độ phức tạp của thuật toán là O(n)
Tuy nhiên, thực nghiệm cho thấy trong trường hợp n lớn, thời gian
tìm kiếm giảm khi dùng phương pháp lính canh.
Với n=15000: nhanh hơn khoảng 20% (0.22s so với 0.28s)
14 Nguyễn Minh Thành
- IV. Tìm Kiếm Nhị Phân
Khi một mảng đã được sắp thứ tự, tận dụng điều này ta có thể giảm
một số thao tác cho thuật toán tìm kiếm.
Thuật toán tìm kiếm nhị phân
Input:
Dãy A, n phần tử đã được sắp xếp
Giá trị x cần tìm
Output: giống với thuật toán tìm kiếm tuần tự
15 Nguyễn Minh Thành
- IV. Tìm Kiếm Nhị Phân
Ý tưởng
So sánh x với phần tử chính giữa mảng A.
Nếu x là phần tử giữa thì dừng.
Nếu không : xác định xem x có thể thuộc nửa trái hay nửa phải
của A.
Lặp lại 2 bước trên với nửa đã được xác định.
16 Nguyễn Minh Thành
- IV. Tìm Kiếm Nhị Phân
Ví dụ : tìm x = 41
x x x
3 14 16 19 22 41 46 51 63 71
1 2 3 4 5 6 7 8 9 10
Tìm thấy x tại
vị trí 6
l m m r
m
17 Nguyễn Minh Thành
- IV. Tìm Kiếm Nhị Phân
Ví dụ : tìm x = 45
x x x x
3 14 16 19 22 41 46 51 63 71
1 2 3 4 5 6 7 8 9 10
l m m r
l > r: Kết thúc:
Không tìm thấy
m
m
18 Nguyễn Minh Thành
- IV. Tìm Kiếm Nhị Phân
Các bước của giải thuật
Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử
Bước 2:
mid = (left+right)/2; // lấy mốc so sánh
So sánh a[mid] với x, có 3 khả năng :
a[mid] = x: Tìm thấy. Dừng
a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1
right =mid - 1;
a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright
left = mid + 1;
Bước 3:
Nếu left
- IV. Tìm Kiếm Nhị Phân
Cài đặt 1
int BinarySearch(int a[],int N,int x )
{ int left =0; right = N-1;
int mid;
do{
mid = (left + right)/2;
if (x == a[mid])
return mid;//Thấy x tại mid
else if (x < a[mid])
right = mid -1;
else
left = mid +1;
}while (left
nguon tai.lieu . vn
