Khác biệt giữa bản sửa đổi của “Giải thuật tìm kiếm”

Trong ngành [[khoa học máy tính]], một '''giải thuật tìm kiếm''' là một [[thuật toán]] lấy đầu vào là một bài toán và trả về kết quả là một lời giải cho bài toán đó, thường là sau khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuật toán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là các thuật toán tìm kiếm. Tập hợp tất cả các lời giải có thể đối với một bài toán được gọi là [[không gian tìm kiếm]]. [[Tìm kiếm bằng vét cạn]] (''brute-force search'') hay các thuật toán tìm kiếm "sơ đẳng"/không có thông tin sử dụng phương pháp đơn giản nhất và trực quan nhất. Trong khi đó, các thuật toán tìm kiếm có thông tin sử dụng [[heuristics]] để áp dụng các tri thức về cấu trúc của [[không gian tìm kiếm]] nhằm giảm thời gian cần thiết cho việc tìm kiếm.

 

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 (khoa học máy tính)|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]] có 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.

 

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: [[big O notation|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à [[big O notation|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ị p hân đối với các danh sách rất lớn với phân bố gần đều. [[Giải thuật Grover]] là một [[máy tính lượng 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.