Bài viết sưu tầm

Không gian trẠng thái cỦa bài toán.

Không gian trạng thái là tập tất cả các trạng thái có thể có và tập các toán tử  của bài toán.

Không gian trạng thái là một bộ bốn, ký hiệu: K= (T, S, G, F). Trong đó,

T: tập tất cả các trạng thái có thể có của bài toán

S: trạng thái đầu

G: tập các trạng thái đích

F: tập các toán tử

Ví dụ 1. Không gian trạng thái của bài toán đong nước là bộ bốn T, S, G, F xác đinh như sau:

T = { (x,y) / 0 <= x <= m; 0 <= y <= n }

S = (0,0)

G = { (x,k) hoặc (k,y) / 0 <= x <= m; 0 <= y <= n}

F = Tập các thao tác đong đầy, đổ ra hoặc đổ sang bình khác thực hiện trên một bình.

Ví dụ 2.  Không gian trạng thái của bài toán Tháp Hà nội với n = 3:

               T = { (x1, x2, x3)/ xi Î {1, 2, 3} }

               S = (1, 1, 1)

               G = {(3, 3, 3)}

               F = Tập các khả năng có thể chuyển đĩa đã xác định trong phần trước.

Ví dụ 3. Không gian trạng thái của bài toán trò chơi 8 số:

                T = { (a_ij)_3x3 / 0<= a_ij <= 8 và a_ij <> a_kl với i<> j hoặc k <> l}

                S = Ma trận xuất phát của bài toán,

                G = Ma trận cuối cùng của bài toán (các số nằm theo vị trí yêu cầu)

                F = {f_l, f_r, f_u, f_d}

Tìm kiếm lời giải trong không gian trạng thái là quá trình tìm kiếm xuất phát từ trạng thái ban đầu, dựa vào toán tử chuyển trạng thái để xác định các trạng thái tiếp theo cho đến khi gặp được trạng thái đích.