Tìm kiếm và Giải quyết vấn đề
Tìm kiếm và giải quyết vấn đề là một nhánh của trí tuệ nhân tạo liên quan đến việc xây dựng các nhiệm vụ dưới dạng khám phá không gian trạng thái hoặc cấu hình và tìm kiếm các chuỗi hành động, gán ghép hoặc di chuyển để đạt được mục tiêu.
Definition
Giải quyết vấn đề dựa trên tìm kiếm biểu diễn một nhiệm vụ dưới dạng trạng thái ban đầu, một tập hợp các hành động biến đổi trạng thái, một kiểm tra mục tiêu và một chi phí đường đi, và giải quyết nó bằng cách khám phá một cách có hệ thống các trạng thái có thể đạt được cho đến khi tìm thấy trạng thái mục tiêu (hoặc đường đi có chi phí thấp nhất đến trạng thái đó).
Scope
Lĩnh vực này bao gồm việc xây dựng các vấn đề dưới dạng không gian trạng thái và các thuật toán khám phá chúng: tìm kiếm không có thông tin (mù) như tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu, tìm kiếm có thông tin (heuristic) như A* và tìm kiếm tốt nhất tham lam, tìm kiếm đối kháng cho các trò chơi hai người chơi và thỏa mãn ràng buộc. Nó đề cập đến cách các vấn đề được mô hình hóa dưới dạng trạng thái, hành động và kiểm tra mục tiêu, cũng như cách phân tích tính đầy đủ, tính tối ưu, thời gian và không gian. Nó không bao gồm việc học các heuristic tìm kiếm hoặc các hàm đánh giá từ dữ liệu, vốn thuộc về lĩnh vực con học máy riêng biệt.
Sub-topics
Core questions
- Làm thế nào để một nhiệm vụ trong thế giới thực được xây dựng thành một không gian trạng thái với các trạng thái, hành động và một kiểm tra mục tiêu?
- Khi nào một thuật toán tìm kiếm là đầy đủ (được đảm bảo tìm thấy một giải pháp nếu có) và tối ưu (được đảm bảo tìm thấy một giải pháp có chi phí thấp nhất)?
- Làm thế nào một hàm heuristic hướng dẫn tìm kiếm đến mục tiêu trong khi vẫn duy trì tính tối ưu?
- Làm thế nào để kiểm soát sự bùng nổ tổ hợp của không gian trạng thái bằng cách cắt tỉa hoặc sắp xếp có thông tin?
- Tìm kiếm thay đổi như thế nào khi một đối thủ đang chọn một số nước đi?
Key concepts
- không gian trạng thái
- cây tìm kiếm và đồ thị tìm kiếm
- tìm kiếm không có thông tin (mù)
- hàm heuristic
- tính chấp nhận được và tính nhất quán
- tìm kiếm A*
- hệ số phân nhánh và độ sâu tìm kiếm
- tính đầy đủ và tính tối ưu
- thỏa mãn ràng buộc
Key theories
- Heuristic chấp nhận được và tính tối ưu của A*
- Nếu một heuristic không bao giờ ước tính quá cao chi phí thực sự đến mục tiêu (là chấp nhận được), tìm kiếm A* sẽ mở rộng các nút theo thứ tự tốt nhất của f = g + h và được đảm bảo trả về một giải pháp tối ưu; tính nhất quán bổ sung đảm bảo không có nút nào được mở rộng lại.
- Sự đánh đổi giữa tìm kiếm không có thông tin và có thông tin
- Các chiến lược mù (tìm kiếm theo chiều rộng, chi phí đồng nhất, chiều sâu, lặp sâu dần) chỉ khác nhau ở thứ tự nút và đưa ra các đảm bảo mà không cần kiến thức miền, trong khi các ước tính heuristic về chi phí còn lại có thể giảm đáng kể không gian được khám phá với rủi ro mất tính tối ưu nếu heuristic không chấp nhận được.
- Xây dựng vấn đề dưới dạng tìm kiếm không gian trạng thái
- Một loạt các nhiệm vụ trở nên khả thi khi được chuyển thành tìm kiếm trên các trạng thái được kết nối bằng các hành động, làm cho việc lựa chọn biểu diễn trạng thái và các toán tử trở thành một quyết định thiết kế trung tâm quyết định hệ số phân nhánh và độ sâu giải pháp.
Clinical relevance
Tìm kiếm là nền tảng của một loạt các hệ thống thực tế: lập kế hoạch và điều hướng tuyến đường (A* trên mạng lưới đường bộ), các công cụ giải đố và trò chơi, cấu hình và lập lịch tự động, lập kế hoạch chuyển động của robot, và là xương sống của lập kế hoạch tự động và các bộ giải ràng buộc được sử dụng trong hậu cần và nghiên cứu hoạt động.
History
Tìm kiếm là trọng tâm của AI ngay từ những ngày đầu, với General Problem Solver của Newell và Simon (cuối những năm 1950) đã định hình trí thông minh là tìm kiếm thông qua các không gian vấn đề. Thuật toán A* (Hart, Nilsson, Raphael, 1968) đã mang lại cho tìm kiếm heuristic một nền tảng tối ưu nghiêm ngặt, và chuyên khảo năm 1984 của Pearl đã hệ thống hóa lý thuyết tìm kiếm heuristic. Khung này vẫn là một lăng kính tổ chức tiêu chuẩn trong các sách giáo khoa AI.
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- Sự khác biệt giữa tìm kiếm không có thông tin và tìm kiếm có thông tin là gì?
- Tìm kiếm không có thông tin (mù), chẳng hạn như tìm kiếm theo chiều rộng hoặc tìm kiếm theo chiều sâu, không sử dụng thông tin nào về mức độ gần của một trạng thái với mục tiêu và khám phá hoàn toàn dựa trên cấu trúc của không gian trạng thái. Tìm kiếm có thông tin (heuristic) sử dụng ước tính chi phí còn lại đến mục tiêu để ưu tiên các trạng thái cần mở rộng, điều này có thể hiệu quả hơn nhiều.
- Tại sao A* được sử dụng rộng rãi như vậy?
- A* kết hợp chi phí thực tế từ điểm bắt đầu (g) với ước tính heuristic đến mục tiêu (h), và khi heuristic là chấp nhận được, nó được đảm bảo tìm thấy một giải pháp tối ưu trong khi thường khám phá ít trạng thái hơn nhiều so với tìm kiếm không có thông tin. Sự cân bằng giữa tính tối ưu và hiệu quả này làm cho nó trở thành lựa chọn mặc định cho việc tìm đường.