Giải Thuật Tìm Kiếm – Wikipedia Tiếng Việt

Một giải thuật tìm kiếm không có thông tin là giải thuật không tính đến bản chất cụ thể của bài toán. Khi đó, các giải thuật dạng này có thể được cài đặt tổng quát, và cùng một cài đặt có thể được sử dụng trong một diện rộng các bài toán (do sử dụng trừu tượng hóa). Nhược điểm của các giải thuật này là phần lớn các không gian tìm kiếm kích thước cực kì lớn, và một quá trình tìm kiếm (đặc biệt tìm kiếm theo cây) sẽ cần một khoảng thời gian đáng kể cho các ví dụ nhỏ. Do đó, để tăng tốc độ quá trình tìm kiếm, đôi khi chỉ có thể dùng giải thuật tìm kiếm có thông tin.

Tìm kiếm trên danh sách

Có lẽ các giải thuật tìm kiếm trên danh sách là loại giải thuật tìm kiếm cơ bản nhất. Mục đích là tìm trong một tập hợp một phần tử chứa một khóa nào đó. Do đây là một bài toán thường gặp trong khoa học máy tính, nên độ phức tạp tính toán của các thuật toán này đã được nghiên cứu kỹ càng. Thuật toán đơn giản nhất là tìm kiếm tuyến tính. Thuật toán này kiểm tra từng phần tử trong danh sách theo thứ tự của danh sách đó. Nó có thời gian chạy khá lớn: O(n), trong đó n là số phần tử trong danh sách, nhưng có thể sử dụng thẳng cho một danh sách bất kỳ mà không cần tiền xử lý. Tìm kiếm nhị phân là một thuật toán cao cấp hơn với thời gian chạy là O(log n). Đối với các danh sách lớn, thuật toán này tốt hơn hẳn tìm kiếm tuyến tính, nhưng nó đòi hỏi danh sách phải được sắp xếp từ trước (xem thuật toán sắp xếp) và đòi hỏi khả năng truy nhập ngẫu nhiên (random access). Tìm kiếm nội suy (Interpolation search) tốt hơn tìm kiếm nhị phân đối với các danh sách rất lớn với phân bố gần đều. Thuật toán Grover là một thuật toán lượng tử cho phép tăng tốc độ gấp 4 lần so với tìm kiếm tuyến tính truyền thống trên các danh sách chưa được sắp xếp.

Bảng băm (hash table) cũng được dùng cho tìm kiếm trên danh sách. Nó đòi hỏi thời gian hằng số trong trường hợp trung bình, nhưng lại cần nhiều phụ phí về không gian bộ nhớ và thời gian chạy O(n) cho trường hợp xấu nhất. Một phương pháp tìm kiếm khác dựa trên các cấu trúc dữ liệu chuyên biệt sử dụng cây tìm kiếm nhị phân cân bằng (self-balancing binary search tree) và đòi hỏi thời gian chạy O(log n); các giải thuật loại này có thể coi là mở rộng của tư tưởng chính về tìm kiếm nhị phân để cho phép chèn và xóa nhanh. Xem mảng liên kết (associative array) để biết thêm về các cấu trúc dữ liệu tìm kiếm trên danh sách.

Đa số các giải thuật tìm kiếm trên danh sách, chẳng hạn tìm kiếm tuyến tính, tìm kiếm nhị phân, và cây tìm kiếm nhị phân cân bằng, có thể được mở rộng với một chút chi phí bổ sung để tìm tất cả các giá trị nhỏ hơn hoặc lớn hơn một khóa cho trước - một phép toán được gọi là tìm kiếm khoảng (range search). Bảng băm là ngoại lệ, các tìm kiếm khoảng không thể được thực hiện một cách hiệu quả trên bảng băm.

Tìm kiếm trên cây

Tìm kiếm trên cây là trung tâm của các kỹ thuật tìm kiếm. Các thuật toán này tìm kiếm trên các cây gồm các nút, cây này có thể là cây tường minh hoặc được xây dựng dần trong quá trình tìm kiếm. Nguyên lý cơ bản là: một nút được lấy ra từ một cấu trúc dữ liệu, các nút con của nó được xem xét và bổ sung vào cấu trúc dữ liệu đó. Bằng cách thao tác trên cấu trúc dữ liệu này, cây tìm kiếm được duyệt theo các thứ tự khác nhau, chẳng hạn theo từng mức (tìm kiếm theo chiều rộng) hoặc đi tới một nút lá trước rồi quay lui (tìm kiếm theo chiều sâu). Các ví dụ khác về tìm kiếm trên cây bao gồm: 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 và tìm kiếm chi phí đều

Tìm kiếm trên đồ thị

Nhiều bài toán về lý thuyết đồ thị có thể được giải quyết bằng các thuật toán tìm kiếm, chẳng hạn thuật toán Dijkstra, thuật toán Kruskal, giải thuật láng giềng gần nhất và giải thuật Prim. Các thuật toán này có thể được coi là các mở rộng của các thuật toán tìm kiếm trên cây.