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

Không gian trạng thái của bài toán.

Kkhô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.

5. Biểu diễn không gian trạng thái dưới dạng đồ thị

5.1. Các khái niệm

• Đồ thị G = (V,E) trong đó V:tập đỉnh, E: tập cung (EÌV*V)

Chú ý

• G là đồ thị vô hướng thì (i, j) là một cạnh cũng như là (j, i) (tức là:(i, j)ÎE thì (j,i)ÎE)
• Nếu G là đồ thị có hướng thì cung (i, j) hoàn toàn khác với cung (j, i).

Ví dụ   xét dồ thị vô hướng G₁ và đồ thị có hướng G₂

 

 

G₁                                       G₂

 

• Tập đỉnh kề:

"nÎV, T(n)={mÎV/ (n,m) ÎE}được gọi là tập các đỉnh kề của n

• Đường đi:

p = (n₁,...,n_k) được gọi là đường đi từ đỉnh n₁ ® n_k  nếu n_i ÎV, "i=1,k ;

 (n_i, n_i+1)ÎE  "i=1, k -1

• Cây là đồ thị có đỉnh gốc n₀ÎV thoả:

Một đồ thị G=(V, E) gọi là cây nếu tồn tại một đỉnh n₀ÎV có những tính chất sau:

                    Ù                     Ù           

• "nÎV, nÎT(n₀), trong đó T(n₀): tập các đỉnh thuộc dòng dõi của n₀ (n₀ là tổ tiên của n)
• "nÎV, $!mÎV sao cho nÎT(m); m được gọi là cha của n.

5.2. Biểu diễn không gian trạng thái bằng đồ thị

Theo ngôn ngữ đồ thị, không gian trạng thái tương ứng với một đồ thị định hướng trong đó: Các trạng thái tương ứng với các đỉnh trong đồ thị, nếu tồn tại toán tử chuyển trạng thái   thì có cung (s, t)

Để thấy rõ mối tương quan, ta có bảng sau

KGTT	Đồ thị
Trạng thái Toán tử Dãy các trạng thái liên tiếp	Đỉnh Cung Đường đi

         

5.3. Biểu diễn đồ thị

Cho đồ thị G = (V,E) , giả sử V={1, 2,....,n}. Có hai cách thường dùng để biểu diễn đồ thị G lưu trữ trong máy tính.

i) Biểu diễn bằng ma trận kề

Đồ thị G được biểu diễn bởi ma trận kề A=(a_ij)_nxn, với n là số đỉnh của đồ thị, trong đó:

a_ij=          1                 nếu (i, j) ÎE

0                 trong trường hợp ngược lại

 

Nếu G là đồ thị vô hướng thì ma trận kề A là ma trận đối xứng.