Không gian trạng thái

Vacuum World, một bài toán tìm đường đi ngắn nhất với không gian trạng thái hữu hạn

Không gian trạng thái (tiếng Anh: state space) là tập hợp tất cả các kiểu hình có thể có của một hệ bất kỳ.^[1] Nó là một trừu tượng hữu ích trong việc lý giải cách vận hành của một hệ cho trước và thường được sử dụng rộng rãi trong lĩnh vực trí tuệ nhân tạo cũng như lý thuyết trò chơi.

Các hình trạng ban đầu và tình trạng sau cuối của một bài toán được gọi là trạng thái đầu và trạng thái cuối tương ứng. Một không gian trạng thái đạt được từ trạng thái đầu bao gồm tất cả các kiểu hình được sinh ra nhờ việc áp dụng những phép dịch chuyển chấp nhận được của vị trí trống.^[2]

Trong khoa học máy tính

Trong khoa học máy tính, không gian trạng thái được biểu diễn bằng một nhóm bốn yếu tố gồm N, A, S, GD, trong đó:^[3]

• N (Node) là tập hợp các nút hay các trạng thái của đồ thị.
• A (Arc) là tập các cung, các liên kết giữa từng nút.
• S (Start) là tập con không rỗng của N, chứa các trạng thái ban đầu của bài toán.
• GD (Goal Description) là một tập con không rỗng của N, chứa (các) trạng thái đích của bài toán.

Tham khảo

1. Nykamp, Duane. “State space definition”. Math Insights. Truy cập ngày 17 tháng 11 năm 2019.
2. Nguyễn Thanh Thủy (1995). Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri thức. Nhà xuất bản Giáo dục. tr. 48.
3. Võ Huỳnh Trâm & Trần Ngân Bình (2007). Giáo trình Trí tuệ nhân tạo. Khoa Công nghệ thông tin và Truyền thông, Trường Đại học Cần Thơ. tr. 45.