Thuật toán tìm kiếm là một trong những bài toán quan trọng nhất của Artificial Intelligence. Chủ đề này sẽ giải thích tổng quan về các thuật toán tìm kiếm trong AI.
Các tác nhân giải quyết vấn đề:
Trong Artificial Intelligence, các kỹ thuật Tìm kiếm là phương pháp giải quyết vấn đề phổ biến. Tác nhân hợp lý hoặc tác nhân giải quyết vấn đề trong AI hầu hết sử dụng các chiến lược hoặc thuật toán tìm kiếm này để giải quyết một vấn đề cụ thể và mang lại kết quả tốt nhất. Tác nhân giải quyết vấn đề là tác nhân dựa trên mục tiêu và sử dụng biểu diễn nguyên tử. Trong chủ đề này, chúng ta sẽ tìm hiểu các thuật toán tìm kiếm giải quyết vấn đề khác nhau.
Thuật toán tìm kiếm:
- Search: Tìm kiếm là quy trình từng bước để giải quyết vấn đề tìm kiếm trong một không gian tìm kiếm nhất định. Một vấn đề tìm kiếm có thể có ba yếu tố chính:
- Search Space: Không gian tìm kiếm đại diện cho một tập hợp các giải pháp khả thi mà một hệ thống có thể có.
- Start State: Là trạng thái mà từ đó tác nhân bắt đầu tìm kiếm.
- Goal test: Là một chức năng quan sát trạng thái hiện tại và trả về trạng thái mục tiêu có đạt được hay không.
- Search tree: Cây biểu diễn bài toán tìm kiếm được gọi là cây Tìm kiếm. Gốc của cây tìm kiếm là nút gốc tương ứng với trạng thái ban đầu.
- Actions: Nó cung cấp mô tả về tất cả các hành động có sẵn cho đại lý.
- Transition model: Mô tả về những gì mỗi hành động thực hiện, có thể được biểu diễn dưới dạng mô hình chuyển tiếp.
- Path Cost:: Đây là một hàm ấn định chi phí số cho mỗi đường dẫn.
- Solution: Đây là một chuỗi hành động dẫn từ nút bắt đầu đến nút mục tiêu.
- Optimal Solution: Nếu một giải pháp có chi phí thấp nhất trong tất cả các giải pháp.
Thuộc tính của thuật toán tìm kiếm:
Sau đây là bốn thuộc tính cơ bản của thuật toán tìm kiếm để so sánh hiệu quả của các thuật toán này:
Completeness: Thuật toán tìm kiếm được cho là hoàn chỉnh nếu nó đảm bảo trả về một giải pháp nếu có ít nhất bất kỳ giải pháp nào tồn tại cho bất kỳ đầu vào ngẫu nhiên nào.
Optimality: Nếu một giải pháp được tìm thấy cho một thuật toán được đảm bảo là giải pháp tốt nhất (chi phí đường dẫn thấp nhất) trong số tất cả các giải pháp khác, thì một giải pháp như vậy được cho là một giải pháp tối ưu.
Time Complexity: Độ phức tạp về thời gian là thước đo thời gian để một thuật toán hoàn thành nhiệm vụ của nó.
Space Complexity: Đó là không gian lưu trữ tối đa cần thiết tại bất kỳ thời điểm nào trong quá trình tìm kiếm, vì mức độ phức tạp của vấn đề.
Các loại thuật toán tìm kiếm
Dựa trên các vấn đề tìm kiếm, chúng ta có thể phân loại các thuật toán tìm kiếm thành các thuật toán tìm kiếm không có thông tin (tìm kiếm mù) và tìm kiếm có thông tin (tìm kiếm theo kiểu Heuristic).
Uninformed/Blind Search
Tìm kiếm không thông báo không chứa bất kỳ kiến thức miền nào như độ gần, vị trí của mục tiêu. Nó hoạt động theo cách thô bạo vì nó chỉ bao gồm thông tin về cách đi ngang qua cây và cách xác định các nút lá và mục tiêu. Tìm kiếm không thông tin áp dụng một cách trong đó cây tìm kiếm được tìm kiếm mà không có bất kỳ thông tin nào về không gian tìm kiếm như các toán tử trạng thái ban đầu và thử nghiệm cho mục tiêu, vì vậy nó còn được gọi là tìm kiếm mù. Nó kiểm tra từng nút của cây cho đến khi đạt được nút mục tiêu.
Nó có thể được chia thành năm loại chính:
- Breadth-first search
- Uniform cost search
- Depth-first search
- Iterative deepening depth-first search
- Bidirectional Search
Informed Search
Các thuật toán tìm kiếm thông tin sử dụng kiến thức domain. Trong một tìm kiếm được thông báo, thông tin sự cố có sẵn có thể hướng dẫn tìm kiếm. Các chiến lược tìm kiếm được cung cấp thông tin có thể tìm ra giải pháp hiệu quả hơn so với chiến lược tìm kiếm không có thông tin. Tìm kiếm thông tin còn được gọi là tìm kiếm theo phương pháp Heuristic.
Heuristic là một cách có thể không phải lúc nào cũng được đảm bảo cho các giải pháp tốt nhất nhưng được đảm bảo để tìm ra một giải pháp tốt trong thời gian hợp lý.
Tìm kiếm thông tin có thể giải quyết nhiều vấn đề phức tạp mà không thể giải quyết theo cách khác.
Một ví dụ về các thuật toán tìm kiếm được thông báo là một vấn đề của người bán hàng đi du lịch.
- Greedy Search
- A* Search
