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

Giải bài toán trong không gian trạng thái, trước hết phải xác định dạng mô tả trạng thái bài toán sao cho bài toán trở nên đơn giản hơn, phù hợp bản chất vật lý của bài toán (Có thể sử dụng các xâu ký hiệu, véctơ, mảng hai chiều, cây, danh sách).

Mỗi trạng thái chính là mỗi hình trạng của bài toán, các tình trạng ban đầu và tình trạng cuối của bài toán gọi là trạng thái đầu và trạng thái cuối.

.Bài toán đong nước

Cho 2 bình có dung tích lần lượt là m và n (lít). Với nguồn nước không hạn chế, dùng 2 bình trên để đong k lit nước. Không mất tính tổng quát có thể giả thiết k <= min(m,n).

      Tại mỗi thời điểm xác định, lượng nước hiện có trong mỗi bình phản ánh bản chất hình trạng của bài toán ở thời điểm đó.

- Gọi x là lượng nước hiện có trong bình dung tích m và y là lượng nước hiện có trong bình dung tích n. Như vậy bộ có thứ tự (x,y) có thể xem là trạng thái của bài toán. Với cách mô tả như vậy, các trạng thái đặc biệt của bài toán sẽ là:

-                    Trạng thái đầu:  (0,0)                      

-                    Trạng thái cuối: (x,k) hoặc (k,y), 0 £x £m , 0 £y £n

Các thao tác sử dụng để chuyển trạng thái này sang trạng thái khác gồm:

Đổ đầy một bình, đổ hết nước trong một bình ra ngoài, đổ nước từ bình này sang bình khác. Như vậy, nếu trạng thái đang xét là (x,y) thì các trạng thái kế tiếp có thể chuyển đến sẽ là:

                                                  (m,y)

                                                  (x,n)

                                                  (0,y)

                                                  (x,0)

                         (x,y)                 (0, x+ y) nếu x+y < = n

                                                  (x+y -n,n) nếu x+y > n

                                                  (x+ y,0) nếu x+y < = m

            (m, x+y-m) nếu x+y > m