Tài liệu Cấu trúc và chiến lược cho TK - Không gian trạng thái

Định nghĩa Không Gian Trạng Thái

Các chiến lược tìm kiếm trên không gian trạng thái:

TK hướng từ dữ liệu (data – driven)

TK hướng từ mục tiêu (goal – driven).

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

TK rộng (breath – first search)

TK sâu (depth – first search)

TK sâu bằng cách đào sâu nhiều lần (depth – first search with iterative deepening)

Sử dụng không gian trạng thái để biễu diễn suy luận với phép tính vị từ: Đồ thị Và/Hoặc (And/Or Graph)


Một KGTT (state space) là 1 bộ [N, A, S, GD] trong đó:

N (node) là các nút hay các trạng thái của đồ thị.

A (arc) là tập các cung (hay các liên kết) giữa các nút.

S (Start) là một tập chứa các trạng thái ban đầu của bài toán.

GD (Goal Description) là một tập chứa các trạng thái đích của bài toán được mô tả theo một trong hai đặc tính:

Đặc tính có thể đo lường được các trạng thái gặp trong quá trình tìm kiếm. VD: Tic-tac-toe, 8-puzzle,

Đặc tính của đường đi được hình thành trong quá trình tìm kiếm. VD: TSP

Đường đi của lời giải (solution path) là một con đường đi qua đồ thị này từ một nút thuộc S đến một nút thuộc GD.