Cau hoi GK TTNT 2

Xây dựng không gian trạng thái và hàm heuristic cho các bài toán đong dầu

Bài giải chi tiết
Bài toán đong dầu
Cho 2 bình có dung tích lần lượt là m và n (lit). Với nguồn dầu không hạn chế, dùng 2 bình trên để đong k lit dầu. 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 dầu 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 dầu hiện có trong bình dung tích m và y là lượng dầu 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
Ví dụ 1: Bài toán đong dầu với m = 5, n= 4, k =3.
Mức 1: Trạng thái đầu (0;0)
Mức 2: Các trạng thái (5;0), (0;4) Mức 3: (5;4), (1;4), (4,0)
Mức 4: (1;0), (4;4) Mức 5: (0;1), (5;3)
Ở mức 5 ta gặp trạng thái đích là (5;3) vì vậy có được lời giải như sau:
(0;0)( (0;4) ( (4;0) ( (4;4) ( (5;3)
Để có được lời giải này ta phải lưu lại vết của đường đi, có thể trình bày quá trình tìm kiếm dưới dạng bảng sau:





Xây dựng không gian trạng thái và hàm heuristic cho các bài toán Tháp Hà Nội



Bài toán xác định khi biết được từng đĩa đang nằm ở cọc nào. Hay nói cách khác, có hai cách xác định:
- Cọc 1 hiện đang chứa những đĩa nào? Cọc 2 hiện đang chứa những đĩa nào? Và cọc 3 đang chứa những đĩa nào.
- Đĩa lớn thứ i hiện đang nàm ở cọc nào? ( i = 1 … n )
Như vậy cách mô tả trạng thái bài toán không duy nhất, vấn đề là chọn cách mô tả nào để đạt được mục đích dễ dàng nhất.
Theo trên, với cách thứ nhất ta phải dùng 3 danh sách động vì số đĩa trên mỗi cọc là khác nhau trong từng thời điểm khác nhau.
Cách thứ hai, nhìn qua thì khó mô tả nhưng dựa vào khái niệm về bộ có thứ tự trong toán học, cách này mô tả bài toán hiệu quả hơn. Thật vậy, nếu gọi xi là cọc chứa đĩa lớn thứ i, trong đó xi({1, 2, 3}, i({1 ..n}. Khi đó bộ có thứ tự (x1, x2, . . ,xn) có thể dùng làm dạng mô tả trạng thái đang xét của bài toán. Với cách mô tả này thì:
- Trạng thái đầu là (1,1,. . .,1)
- Trạng thái cuối là (3,3,. . .,3)
Bài toán Tháp Hà Nội với n=3.
Mỗi trạng thái là một bộ ba (i, j, k). Có các trường hợp như sau