Chương 13 Tìm kiếm

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level 19/09/2013 ‹#› /XX MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH TÌM KIẾM Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Định nghĩa Giải thuật tìm kiếm là một thuật toán trả về kết quả là một lời giải cho bài toán đó. Trong giải thuật tìm kiếm người ta thường cân nhắc giữa các lời giải có thể và tìm ra lời giải tối ưu nhất. Không gian tìm kiếm: tập hợp các lời giải có thể đối với 1 bài toán. Phân loại tìm kiếm Tìm kiếm không có thông tin Tìm kiếm trên danh sách TÌm kiếm trên cây Tìm kiếm trên đồ thị TÌm kiếm có thông tin Tìm kiếm đối kháng Thỏa mãn ràng buộc Tìm kiếm không có thông tin Một giải thuật không tính đến bản chất cụ thể của bài toán. Ưu điểm: Có thể được sử dụng cho nhiều bài toán. Nhược điểm: Không gian tìm kiếm rất lớn. Thời gian tìm kiếm lâu. Tìm kiếm trên danh sách Tìm một khóa nào đó trong 1 tập hợp các phần tử nào đó. Các thuật toán: Tìm kiếm tuyến tính – linear search Tìm kiếm nhị phân – binary search Tìm kiếm nội suy – interpolation search Fibonaccian search Jump search Secant search Bảng băm – hashtable Cây tìm kiếm nhị phân cân bằng – self-balancing binary search tree Tìm kiếm tuyến tính – linear search Ý tưởng của thuật toán: Thuật toán tiến hành kiểm tra từng phần tử trong danh sách theo thứ tự của danh sách đó. Ưu điểm: Đơn giản, dễ cài đặt Có thể áp dụng cho 1 danh sách bất kỳ mà không cần tiền xử lý. Nhược điểm: Thời gian chạy lớn: Trường hợp trung bình và xấu nhất O(n). Trường hợp tốt nhất O(1). Minh họa tìm x =10 Minh họa tìm x = 25 7 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 10 10 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 25 Đã tìm thấy tại vị trí 5 Đã hết mảng Tìm kiếm tuyến tính – linear search Giải thuật Bước 1: i = 1 //bắt đầu từ phần tử đầu tiên của dãy. Bước 2: so sánh a[i] với x, có 2 khả năng: a[i] = x: tìm thấy, dừng thuật toán. a[i] != x: sang bước 3. Bước 3: i = i+1 //xét phần tử kế tiếp trong mảng Nếu i > n: hết mảng, không tìm thấy, dừng. Ngược lại: lặp lại bước 2. Cài đặt Độ phức tạp Độ phức tạp trong thuật toán này chính là số lần thực hiện các phép so sánh. Mỗi bước của vòng lặp cần 2 phép so sánh: Đã hết danh sách chưa. Có bằng phần tử cần tìm không Do đó tại bước thứ i đã có 2i phép so sánh. Trong trường hợp xấu nhất ta có 2n phép so sánh  độ phức tạp O(n) Tìm kiếm nhị phân – binary search Ý tưởng của thuật toán: giả sử danh sách đã được sắp xếp, ta tiến hành chọn một phần tử ở giữa danh sách (middle), sau đó so sánh phàn tử cần tìm kiếm (target) và phần tử middle. Nếu target=middle: đã tìm thấy, kết thúc thuật toán. Nếu target>middle: tiếp tục tìm kiếm nửa bên phải của danh sách cũ. Nếu target r: Kết thúc: Không tìm thấy Tìm kiếm nhị phân – binary search Giải thuật Bước 1: left = 1, right = N //tì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 trong dãy con aleft …amid-1 right = mid – 1; a[mid] a[m]: đặt l = m + 1 Bước 3: Nếu xa[r]  m>r hay m<l: Không tìm thấy, dừng. Ngược lại quay lại bước 2. Ví dụ Tìm x = 32 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 4 7 9 9 12 13 17 19 21 24 32 36 44 45 54 55 63 66 70 Lần 1: l=0, r=19  m=0+(32-0)*(19-0)/(70-1) = 8 a[8]=19<32=x l=9 Lần 2: l=9, r=19  m=9+(30-24)*(19-9)/(70-24) = 11 a[11]=32=x  tìm thấy giá trị x= 32 tại vị trí m = 11 Ví dụ Tìm x = 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 4 7 9 9 12 13 17 19 21 24 32 36 44 45 54 55 63 66 70 Cài đặt So sánh giữa TKNP &TKNS Tính về tốc độ thực hiện thì tìm kiếm nội suy nhanh hơn hẳn tìm kiếm nhị phân. Ví dụ: với 1 tập hợp 232 (4 triệu) phần tử Tìm kiếm nhị phân cần thực hiện 32 bước Trong khi đó tìm kiếm nội suy chỉ cần 5 bước Đối với các tập phần tử lớn thì tốc độ thực hiện của TKNS gần như là hàm hằng. Bảng băm – hashtable Bảng băm – hashtable Ưu điểm: Thời gian chạy là O(1) trong trường hợp trung bình Nhược điểm Thời gian chạy là O(n) trong trường hợp xấu nhất. Đòi hỏi nhiều phụ phí về không gian bộ nhớ. Xem thêm phần hashing. Cây tìm kiếm nhị phân cân bằng Xem phần binary search tree Thời gian chạy: O(log n) Tìm kiếm khoảng – range search Các thuật toán tìm kiếm trên danh sách có thể được mở rộng thành tìm kiếm trên khoảng (range search) Bảng băm không dùng để tìm kiếm trên khoảng. Tìm kiếm trên cây Binary search tree: Tìm kiếm theo chiều rộng TÌm kiếm theo chiều sâu: Tìm kiếm trước (preorder) Tìm kiếm sau (postorder) Tìm kiếm giữa(inorder) Ngoài ra còn có một số các thuật toán tìm kiếm trên cây khác như: Tìm kiếm lặp sâu dần Tìm kiếm chiều sâu giới hạn Tìm kiếm hai chiều Tìm kiếm chi phí đều Tìm kiếm trên đồ thị Là các thuật toán mở rộng của tìm kiếm trên cây. Một số thuật toán tìm kiếm thường gặp: Thuật toán Dijkstra Thuật toán Kruskal Thuật toán láng giềng gần nhất Giải thuật Prim Tìm kiếm có thông tin Trong các thuật toán này ta sẽ sử dụng 1 hàm đánh giá heuristic đặc thù cho bài toán cần giải quyết đóng vai trò hướng dẫn trong quá trình tìm kiếm. Một hàm heuristic tốt sẽ làm cho quá trình tìm kiếm hoạt động hiệu quả hơn. Đa số các thuật toán tìm kiếm có thông tin đều là tìm kiếm trên cây. Tìm kiếm theo lựa chọn tốt nhất A* Tìm kiếm đối kháng Áp dụng trong các trò chơi đối kháng: cờ vua,cờ tướng, cờ caro… Trong loại tìm kiếm này ta phải tính đến mọi nước đi mà đối thủ sử dụng. Một số thuật toán tìm kiếm đối kháng thường gặp: Thuật toán min–max algorithm Thuật toán tỉa cây tìm kiếm – search tree prunning Thuật toán tỉa cây alpha-beta – alpha-beta prunning Tìm kiếm đối kháng Thỏa mãn ràng buộc Đây là một loại tìm kiếm để giải quyết các bài toán thỏa mãn ràng buộc mà trong đó, thay vì tìm một đường đi, lời giải chỉ đơn giản là một tập các giá trị được gán cho một tập các biến. Do các biến có thể được xử lý theo thứ tự tùy ý, các thuật toán thông thường dành cho tìm kiếm trên cây rất không hiệu quả. Các phương pháp thường gặp: Tìm kiếm tổ hợp Tìm kiếm quay lui Tìm kiếm quay lui Ý tưởng: Thử từng khả năng cho đến khi tìm thấy lời giải đúng. Là quá trình tìm kiếm theo độ sâu trong 1 tập các lời giải. Trong quá trình tìm kiếm nếu gặp 1 hướng lựa chọn ko thỏa mãn hoặc đã thử hết các lựa chọn trong hướng đó quay lui về điểm có các hướng khác và thử hướng tiếp theo. Thuật toán kết thúc khi tìm tháy lời giải hoặc khi không còn hướng lựa chọn nào nữa. Tìm kiếm quay lui Một số các loại tìm kiếm khác Các thuật toán tìm xâu ký tự (String searching algorithm) tìm kiếm các mẫu trong các xâu ký tự; cây hậu tố (suffix tree) là một cấu trúc dữ liệu thông dụng có tác dụng làm tăng hiệu quả của các thuật toán này . Giải thuật di truyền hay thuật toán gien sử dụng ý tưởng tiến hóa để làm các heuristic cho việc giảm không gian tìm kiếm . Các thuật toán sắp xếp cần thiết cho việc thực thi một số thuật toán tìm kiếm nhất định. Một số các loại tìm kiếm khác Giả lập luyện thép là một thuật toán tìm kiếm xác suất . Tìm kiếm Tabu là một kỹ thuật tránh việc các quá trình tìm kiếm rời rạc bị tắc trong các cực tiểu địa phương. Tìm kiếm liên bang (Federated search). Giải thuật Minimax được tối ưu hóa bằng kỹ thuật tỉa cây alpha-beta là một thuật toán dành cho tìm kiếm các nước đi tốt trong các trò chơi tổng bằng không. SẮP XẾP Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Định nghĩa Sắp xếp là một quá trình sắp đặt lại vị trí của các phần tử trong 1 danh sách theo một thứ tự nhất định nào đó. Có nhiều thuật toán sắp xếp đã được thiết kế, chúng được phân thành một số loại sau: Sắp xếp ổn định: sau khi tiến hành sắp xếp, thứ tự của các phần tử bằng nhau không bị thay đổi. Sắp xếp so sánh: Trong quá trình sắp xếp ta tiến hành so sánh các khóa và đổi chổ các phần tử cho nhau. Định nghĩa Một số các thuật toán sắp xếp thường gặp: Sắp xếp nổi bọt – bubble sort Sắp xếp chọn – selection sort Sắp xếp chèn – insertion sort Sắp xếp nhanh – quick sort Sắp xếp trộn – merge sort Sắp xếp vun đống – heap sort Sắp xếp theo cơ số - radix sort … Phân loại Các thuật toán sắp xếp được phân thành các loại sau đây: Insertion sort: Sắp xếp chèn Exchange sort: Sắp xếp nổi bọt, Sắp xếp nhanh Selection sort: Sắp xếp chọn, Sắp xếp vun đống Merge sort: Sắp xếp vun đống Distribution sort: Sắp xếp theo cơ số Sắp xếp nổi bọt – bubble sort Ý tưởng: Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó tiến hành so sánh hai phần tử đầu tiên, nếu chưa đúng thứ tự thì đổi chỗ. Tiếp tục làm như vậy với các cặp tiếp theo cho tới cuối danh sách. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy. Sau đó quay lại với hai phần tử đầu cho tới khi không cần phải đổi chỗ nữa. Sắp xếp nổi bọt – bubble sort Sắp xếp nổi bọt – bubble sort Bubble Sort – Ví dụ 46 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 i j 1 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Bubble Sort – Ví dụ 47 12 2 8 5 4 6 15 1 2 3 4 5 6 7 8 1 i j 2 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Bubble Sort – Ví dụ 48 2 12 4 8 5 6 15 1 2 3 4 5 6 7 8 1 i j 4 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Bubble Sort – Ví dụ 49 2 4 12 8 5 6 15 1 2 3 4 5 6 7 8 1 i j 5 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Bubble Sort – Ví dụ 50 2 4 5 12 8 6 15 1 2 3 4 5 6 7 8 1 i j 6 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Bubble Sort – Ví dụ 51 2 4 5 6 12 8 15 1 2 3 4 5 6 7 8 1 i j 8 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Bubble Sort – Ví dụ 52 2 4 5 6 8 12 15 1 2 3 4 5 6 7 8 1 i j 15 12 Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1] Sắp xếp nổi bọt – bubble sort Thời gian chạy: Với mỗi i = 1, 2, ..n-1 ta cần i phép so sánh. Số lần so sánh và đổi chỗ tối đa trong giải thuật là: Do đó độ phức tạp của thuật toán là O(n2) sum = (n - 1)+(n – 2) +…+2+1 = (n - 1)n/2 Cài đặt Cải tiến Bạn có thể cải tiến giải thuật trong trường hợp đối với 1 i cố định sau khi kết thúc vòng lặp j mà không thực hiện bất kỳ việc hoán chỗ nào  dừng thuật toán. Cài đặt cải tiến Sắp xếp chọn – selection sort Ý tưởng: Chọn phần tử nhỏ nhất trong danh sách hiện hành, đưa nó về vị trí đầu tiên của danh sách. Lặp lại quá trình trên cho đến khi danh sách chỉ còn 1 phần tử. Nghĩa là, thuật toán thực hiện n-1 lần việc đưa phần tử nhỏ nhất về vị trí đúng ở đầu dãy. Sắp xếp chọn – selection sort Selection Sort – Ví dụ 59 2 8 5 1 6 4 15 12 i min 2 3 4 5 6 7 8 1 Find MinPos(1, 8) Swap(a[i], a[min]) 60 2 8 5 12 6 4 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(2, 8) Swap(a[i], a[min]) Selection Sort – Ví dụ 61 2 8 5 12 6 4 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(3, 8) Swap(a[i], a[min]) Selection Sort – Ví dụ 62 2 4 5 12 6 8 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(4, 8) Swap(a[i], a[min]) Selection Sort – Ví dụ 63 2 4 5 12 6 8 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(5, 8) Swap(a[i], a[min]) Selection Sort – Ví dụ 64 2 4 5 6 12 8 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(6, 8) Swap(a[i], a[min]) Selection Sort – Ví dụ 65 2 4 5 6 8 12 15 1 i min 2 3 4 5 6 7 8 1 Find MinPos(7, 8) Swap(a[i], a[min]) 12 15 Selection Sort – Ví dụ Sắp xếp chọn – selection sort Sắp xếp chọn – selection sort Thời gian chạy: Số lượng các lần so sánh là: O(N2) Số lượng các lần đổi chổ là swap <= N-1  O(N) Độ phức tạp của thuật tán là: O(N2) + O(N) = O(N2) Độ phức tạp Tối thiểu Trung bình Tối đại O(n2) O(n2) O(n2) sum = (n - 1)+(n – 2) +…+2+1 = (n - 1)n/2 Sắp xếp chọn – selection sort Sắp xếp chèn – insertion sort Ý tưởng: Là một thuật toán bắt chước cách xếp bài của người chơi bài. Lần lượt rút từ phần tử thứ 2 để chèn vào vị trí thích hợp. Sắp xếp chèn – insertion sort 71 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 Insertion Sort – Ví dụ 72 2 8 5 1 6 4 15 12 i x 2 3 4 5 6 7 8 1 pos 2 Chèn a[1] vào (a[0], a[1]) Insertion Sort – Ví dụ 73 12 8 5 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Chèn a[2] vào (a[0] … a[2]) 8 Insertion Sort – Ví dụ 74 8 12 5 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Chèn a[3] vào (a[0] … a[3]) 5 Insertion Sort – Ví dụ 75 5 8 12 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Chèn a[4] vào (a[0] … a[4]) 1 Insertion Sort – Ví dụ 76 2 5 8 12 6 4 15 1 i x 2 3 4 5 6 7 8 1 pos Chèn a[5] vào (a[0]… a[5]) 6 Insertion Sort – Ví dụ 77 2 5 6 8 12 4 15 1 i x 2 3 4 5 6 7 8 1 pos Chèn a[6] vào (a[0] … a[6]) 4 Insertion Sort – Ví dụ 78 2 4 5 6 8 12 15 1 i x 2 3 4 5 6 7 8 1 pos Chèn a[7] vào (a[0] … a[7]) 15 Insertion Sort – Ví dụ 79 2 4 5 6 8 12 15 1 pos 2 3 4 5 6 7 8 1 Insertion Sort – Ví dụ Insertion Sort – Ví dụ Thời gian chạy: Tại lượt thứ i thuật toán cần trung bình i/2 phép so sánh tổng số phép toán: O(n2) sum = (1/2) + (2/2) + (3/2)+…+(n /2) = (n +1) * n/4 Sắp xếp chèn – insertion sort Sắp xếp chèn – insertion sort Sắp xếp nhanh – quick sort Ý tưởng: Chia danh sách thành 2 danh sách con bằng cách so sánh từng phần tử của danh sách với 1 phần tử chọn trước (phần tử chốt). Các phần tử nhỏ hơn hoặc bằng được đưa về phía trước và nằm trong danh sách con thứ 1. Các phần tử lớn hơn được đưa về phía sau và thuộc danh sách con thứ 2. Tiếp tục thực hiện các bước trên cho tới lúc các danh sách con chỉ còn 1 phần tử. Sắp xếp nhanh – quick sort Ví dụ chọn phần tử chốt với công thức: k = int((k1 + k2) / 2) + 1 85 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 left right 5 X STOP Không nhỏ hơn x i j STOP Không lớn hơn x Phân hoạch dãy Quick Sort – Ví dụ 86 2 8 5 1 6 12 15 4 2 3 4 5 6 7 8 1 left right 5 X STOP Không nhỏ hơn x i j STOP Không lớn hơn x Phân hoạch dãy Quick Sort – Ví dụ 87 2 1 5 8 6 12 15 4 2 3 4 5 6 7 8 1 left right i j Quick Sort – Ví dụ 88 6 X 2 4 5 8 6 12 15 1 2 3 4 5 6 7 8 1 left right i j STOP Không nhỏ hơn x STOP Không lớn hơn x Sắp xếp đoạn 3 Phân hoạch dãy Quick Sort – Ví dụ 89 2 4 5 6 8 12 15 1 2 3 4 5 6 7 8 1 left right i j Sắp xếp đoạn 3 Quick Sort – Ví dụ 90 2 4 5 6 8 12 15 1 2 3 4 5 6 7 8 1 Quick Sort – Ví dụ Sắp xếp nhanh – quick sort Sắp xếp nhanh – quick sort Thời gian chạy: Độ phức tạp Tối thiểu Trung bình Tối đại O(nlogn) O(nlogn) O(n2) Sắp xếp nhanh – quick sort Sắp xếp nhanh – quick sort Sắp xếp trộn – merge sort Ý tưởng trộn: giả sử ta có hai danh sách đã được sắp xếp, ta có thể trộn chúng lại để có 1 danh sách mới như sau: So sánh 2 phần tử đầu của dánh sách lấy phần tử nhỏ hơn cho vào danh sách mới. Tiếp tục cho tới khi một trong hai danh sách ban đầu rỗng. Cho tất cả các phần tử của danh sách còn lại vào cuối danh sách mới. Sắp xếp trộn – merge sort Sắp xếp trộn – merge sort Ý tưởng: Ta chia danh sách cần sắp xếp thành hai phần với k = (min + max)/2. Tiến hành sắp xếp trên hai danh sách con này. Sau đó trộn chúng lại với nhau. Sắp xếp trộn – merge sort Sắp xếp trộn – merge sort Sắp xếp trộn – merge sort Độ phức tạp thuật toán: Độ phức tạp Tối thiểu Trung bình Tối đại O(nlogn) O(nlogn) O(nlogn) Sắp xếp trộn – merge sort Sắp xếp trộn – merge sort Sắp xếp vun đống – heap sort Đống: heap là một cây nhị phân hoàn chỉnh có tính chất là khóa ở nút cha bao giờ cũng lớn hơn khóa ở các nút con. Sắp xếp vun đống – heap sort Chèn một phần tử vào 1 heap có sẵn Sắp xếp vun đống – heap sort Tạo một heap từ 1 dãy cho trước  Tạo một heap với phần tử đầu tiên. tiến hành chèn các phần tử còn lại vào heap trên. Sắp xếp vun đống – heap sort Xóa phần tử gốc ra khỏi heap: Sắp xếp vun đống – heap sort Ý tưởng: cơ bản là thực hiện việc sắp xếp thông qua việc tạo các heap Tạo ra 1 heap với các phần tử cần sắp xếp.  nút cha bao giờ cũng lớn nhất. Sắp xếp dãy dựa trên heap đã tạo ra. Nút gốc sẽ được đưa về cuối danh sách. Chuyển cây vừa xóa nút gốc về heap, tiếp tục việc tạo heap và sắp xếp cho tới khi chỉ còn 1 nút trong heap. Sắp xếp vun đống – heap sort Sắp xếp vun đống – heap sort Độ phức tạp thuật toán: Heap là một cây hoàn chỉnh, có N nút thì chiều cao của nó là log(n)+1 nên độ phức tạp là O(nlogn). Độ phức tạp Tối thiểu Trung bình Tối đại O(nlogn) O(nlogn) O(nlogn) Sắp xếp vun đống – heap sort Sắp xếp vun đống – heap sort HỎI ĐÁP