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 Chương 2 (1) : Giải Thuật Tìm Kiếm 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 3 Nguyễn Minh Thành  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 II. Giải thuật tìm kiếm 4 Nguyễn Minh Thành  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  So sánh III. Tìm Kiếm Tuyến Tính 5 Nguyễn Minh Thành  Có 2 loại tìm kiếm tuyến tính :  Vét cạn (exhaustive)  Dùng lính canh (sentinel) III. Tìm Kiếm Tuyến Tính – Vét Cạn 6 Nguyễn Minh Thành  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 III. Tìm Kiếm Tuyến Tính – Vét Cạn 7 Nguyễn Minh Thành  Cài đặt 1 : int LinearExhaustive(int a[], int N, int x) { int i=0; while ((i<N) && (a[i]!=x )) i++; if(i==N) return -1;// tìm hết mảng nhưng không có x else return i;// a[i] là phần tử có khoá x } III. Tìm Kiếm Tuyến Tính – Vét Cạn 8 Nguyễn Minh Thành  Cài đặt 2 : int LinearExhaustive(intA[], intn, intx) { for(int i=0; i<n; i++) if(A[i]==x) return i; return -1; } III. Tìm Kiếm Tuyến Tính – Vét Cạn 9 Nguyễn Minh Thành  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) III. Tìm Kiếm Tuyến Tính – Lính Căn 10 Nguyễn Minh Thành  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 III. Tìm Kiếm Tuyến Tính – Lính Căn 11 Nguyễn Minh Thành  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. III. Tìm Kiếm Tuyến Tính – Lính Căn 12 Nguyễn Minh Thành  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 } III. Tìm Kiếm Tuyến Tính – Lính Căn 13 Nguyễn Minh Thành  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; } III. Tìm Kiếm Tuyến Tính – Lính Căn 14 Nguyễn Minh Thành  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) IV. Tìm Kiếm Nhị Phân 15 Nguyễn Minh Thành  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ự IV. Tìm Kiếm Nhị Phân 16 Nguyễn Minh Thành  Ý 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. IV. Tìm Kiếm Nhị Phân 17 Nguyễn Minh Thành  Ví dụ : tìm x = 41 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 x ml m x r m x Tìm thấy x tại vị trí 6 IV. Tìm Kiếm Nhị Phân 18 Nguyễn Minh Thành  Ví dụ : tìm x = 45 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 x m m x r m x l m x l > r: Kết thúc: Không tìm thấy IV. Tìm Kiếm Nhị Phân 19 Nguyễn Minh Thành  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 <= right //còn phần tử chưa xét tìm tiếp. Lặp lại Bước 2. Ngược lại: Dừng //Ðã xét hết tất cả các phần tử. IV. Tìm Kiếm Nhị Phân 20 Nguyễn Minh Thành  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 <= right); return -1; // Tìm hết dãy mà không có x } IV. Tìm Kiếm Nhị Phân 21 Nguyễn Minh Thành  Cài đặt 2 (đệ quy) int BinarySearch(int a[], int l, int r, int x) { if(r < l) return -1; m = (l + r) / 2; if ( x < a[m]) BS(a,l,m-1,x); else if (x > a[m]) BS(a,m+1,r,x); return m; //là phần tửchính giữa } IV. Tìm Kiếm Nhị Phân 22 Nguyễn Minh Thành  Trường hợp xấu nhất là x nằm ở cuối mảng, số phép so sánh phải thực hiện là : log2n + 1  Vậy độ phức tạp của thuật toán : O(log2n)  Một số so sánh :  Tuy nhiên, mảng phải được sắp xếp trước. Hỏi Đáp 23 Nguyễn Minh Thành