Tìm kiếm không gian trạng thái

Tìm kiếm không gian trạng thái là việc khám phá có hệ thống tập hợp các trạng thái có thể đạt được từ một trạng thái ban đầu thông qua các hành động có sẵn, nhằm tìm ra một trạng thái thỏa mãn điều kiện mục tiêu hoặc một đường dẫn để đạt được trạng thái đó.

Definition

Tìm kiếm không gian trạng thái coi một vấn đề như một đồ thị với các nút là trạng thái và các cạnh là hành động, và tiến hành bằng cách mở rộng các trạng thái từ một biên (frontier) theo một chiến lược cố định cho đến khi tìm thấy trạng thái mục tiêu hoặc không gian được khám phá hết.

Scope

Chủ đề này bao gồm việc xây dựng một vấn đề dưới dạng không gian trạng thái (các trạng thái, hành động, mô hình chuyển đổi, kiểm tra mục tiêu, chi phí đường dẫn) và các chiến lược tìm kiếm không có thông tin (uninformed search strategies) khám phá nó mà không có hướng dẫn cụ thể theo miền: tìm kiếm theo chiều rộng (breadth-first), tìm kiếm chi phí đồng nhất (uniform-cost), tìm kiếm theo chiều sâu (depth-first), tìm kiếm theo chiều sâu giới hạn (depth-limited) và tìm kiếm lặp sâu dần (iterative-deepening). Nó bao gồm phân tích các chiến lược này theo tính đầy đủ (completeness), tính tối ưu (optimality), độ phức tạp thời gian (time complexity) và độ phức tạp không gian (space complexity), cũng như sự phân biệt giữa tìm kiếm cây (tree search) và tìm kiếm đồ thị (graph search) với việc phát hiện trạng thái lặp lại. Hướng dẫn heuristic được đề cập trong chủ đề riêng về tìm kiếm heuristic và A*.

Core questions

• Một vấn đề được biểu diễn như thế nào dưới dạng các trạng thái, hành động, mô hình chuyển đổi và kiểm tra mục tiêu?
• Tìm kiếm theo chiều rộng, theo chiều sâu, chi phí đồng nhất và lặp sâu dần khác nhau như thế nào trong việc sắp xếp biên của chúng?
• Các đảm bảo về tính đầy đủ, tính tối ưu, thời gian và không gian của mỗi chiến lược không có thông tin là gì?
• Tìm kiếm đồ thị tránh việc khám phá lại các trạng thái một cách lãng phí mà tìm kiếm cây cho phép như thế nào?

Key concepts

• trạng thái ban đầu và kiểm tra mục tiêu
• mô hình chuyển đổi và các trạng thái kế tiếp
• biên (danh sách mở) và tập hợp đã khám phá
• tìm kiếm theo chiều rộng
• tìm kiếm theo chiều sâu
• tìm kiếm chi phí đồng nhất
• lặp sâu dần
• tìm kiếm cây so với tìm kiếm đồ thị

Key theories

Thứ tự biên xác định chiến lược

Các thuật toán tìm kiếm không có thông tin chỉ khác nhau ở thứ tự mà chúng loại bỏ các trạng thái khỏi biên: một hàng đợi FIFO cho tìm kiếm theo chiều rộng, một ngăn xếp LIFO cho tìm kiếm theo chiều sâu và một hàng đợi ưu tiên theo chi phí đường dẫn cho tìm kiếm chi phí đồng nhất.

Lặp sâu dần như một tối ưu hiệu quả về không gian

Tìm kiếm lặp sâu dần theo chiều sâu liên tục chạy tìm kiếm theo chiều sâu giới hạn với các giới hạn tăng dần, kết hợp không gian tuyến tính của tìm kiếm theo chiều sâu với tính đầy đủ và tính tối ưu (trên chi phí đơn vị) của tìm kiếm theo chiều rộng.

Clinical relevance

Tìm kiếm không gian trạng thái không có thông tin là nền tảng khái niệm và triển khai cho việc tìm đường, giải câu đố, phân tích khả năng tiếp cận trong kiểm tra mô hình, và là cơ sở để xây dựng tìm kiếm heuristic và đối kháng; việc hiểu độ phức tạp của nó giúp định hướng khi nào tìm kiếm mù (blind search) khả thi so với khi nào cần đến heuristic.

History

Tìm kiếm không gian trạng thái có hệ thống bắt nguồn từ các thuật toán duyệt đồ thị của những năm 1950, bao gồm công trình về đường đi ngắn nhất của Moore và Dijkstra, và được coi là một mô hình giải quyết vấn đề trong AI sơ khai. Phân tích của Korf năm 1985 về lặp sâu dần đã thiết lập tính tối ưu của nó trong số các tìm kiếm cây chấp nhận được với không gian tuyến tính.

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

Khi nào tìm kiếm theo chiều rộng là tối ưu?

Tìm kiếm theo chiều rộng là tối ưu khi mỗi bước có cùng chi phí, vì nó tìm thấy mục tiêu nông nhất trước. Khi chi phí bước khác nhau, tìm kiếm chi phí đồng nhất (sắp xếp biên theo chi phí đường dẫn tích lũy) là chiến lược không có thông tin đảm bảo một giải pháp có chi phí thấp nhất.

Tại sao sử dụng lặp sâu dần thay vì tìm kiếm theo chiều rộng thông thường?

Tìm kiếm theo chiều rộng lưu trữ toàn bộ biên và có thể yêu cầu bộ nhớ theo cấp số nhân với độ sâu. Lặp sâu dần liên tục thực hiện tìm kiếm theo chiều sâu với các giới hạn độ sâu tăng dần, chỉ sử dụng bộ nhớ tuyến tính trong khi vẫn đầy đủ và tối ưu trên các bài toán chi phí đơn vị, với chi phí là việc mở rộng lại các nút nông.