BỘ MÔN KHOA HỌC MÁY TÍNH
CT332: TRÍ TUỆ NHÂN TẠO
BÀI THỰC HÀNH SỐ 1
BIỂU DIỄN KHÔNG GIAN TRẠNG THÁI & TÌM KIẾM MÙ
I. Mục tiêu
Biểu diễn bài toán trên không gian trạng thái và áp dụng giải thuật tìm kiếm mù – tìm kiếm thiếu thông tin bổ sung để tìm ra giải pháp cho bài toán đong nước. Ngôn ngữ sử dụng: C.
II. Nội dung
- Mô tả bài toán Cho 2 bình nước, bình thứ nhất có sức chứa được X lít (Bình X), bình thứ hai có sức chứa Y lít (Bình Y) và 1 vòi bơm (Xem hình bên dưới). Cả hai bình X và Y đều không có vạch chia. Làm cách nào đong được Z lít. Biết rằng chúng ta có thể thực hiện các thao tác/ hành động sau đây để đong nước.
Hành động 1. Sử dụng vòi bơm để đong đầy nước bình X. Nghĩa là sau khi thực hiện hành động này thì bình nước X có được X lít nước, đúng với sức chứa của bình X. Ví dụ: Bình X hiện tại đang có 4 lít và bình có sức chứa là 9 lít thì sau khi thực hiện hành động này thì bình X có 9 lít nước. Hành động 2. Sử dụng vòi bơm để đong đầy nước bình Y. Tương tự như hành động 1 thì bình nước cũng sẽ có được Y lít nước, đúng với sức chứa của bình Y. Ví dụ: Bình Y hiện tại đang có 3 lít và bình có sức chứa là 4 lít thì sau khi thực hiện hành động này thì bình Y có 4 lít nước.
Hành động 3. Rót hết nước trong X ra. Sau khi thực hiện phép toán này thì lượng nước của bình X bằng 0. Ví dụ: Bình X hiện tại đang có 3 lít thì sau khi thực hiện hành động này thì bình X có 0 (empty) lít nước. Hành động 4. Rót hết nước trong Y ra. Tương tự như hành động 3 thì lượng nước của bình Y bằng 0. Ví dụ: Bình Y hiện tại đang có 2 lít thì sau khi thực hiện hành động này thì bình Y có 0 (empty) lít nước. Hành động 5. Rót nước từ bình X sang bình Y. Ví dụ: Có hai bình X (có sức chứa là 9) và Y (có sức chứa là 4). Hiện tại lượng nước trong bình X là 8 và lượng nước trong bình Y là 3. Sau khi thực hiện hành động chuyển nước từ bình X sang bình Y. Thì lượng nước trong X là 7 và lượng nước trong bình Y là 4. Sinh viên xem thêm ví dụ trong bảng bên dưới. Ví dụ 1: Bình X (Sức chứa là 9) Bình Y (Sức chứa là 4) Lượng nước hiện tại 8 3 Sau khi rót nước từ X sang Y 7 4
Ví dụ 2: Bình X (Sức chứa là 9) Bình Y (Sức chứa là 4) Lượng nước hiện tại 2 1 Sau khi rót nước từ X sang Y 0 3
Hành động 6. Rót nước từ bình Y sang bình X. Tượng tự như hành động 5. Ví dụ: Có hai bình X (có sức chứa là 9) và Y (có sức chứa là 4). Hiện tại lượng nước trong bình X là 8 và lượng nước trong bình Y là 3. Sau khi thực hiện hành động chuyển nước từ bình Y sang bình Y. Thì lượng nước trong X là 9 và lượng nước trong bình Y là 2. Sinh viên xem thêm ví dụ trong bảng bên dưới. Ví dụ 1: Bình X (Sức chứa là 9) Bình Y (Sức chứa là 4) Lượng nước hiện tại 8 3 Sau khi rót nước từ Y sang X 9 2
Ví dụ 2: Bình X (Sức chứa là 9) Bình Y (Sức chứa là 4) Lượng nước hiện tại 2 1 Sau khi rót nước từ X sang Y 3 0
Ví dụ một lời giải cho bài toán đong nước: Bình X có sức chứa là 9 và bình Y là 4. Mục đích người ta cần đong được bình nước được 6 lít nước. Dưới đây là một lời giải có thể thực hiện để đong được bình nước 6.
-
- Biểu diễn trạng thái bắt đầu Gán lượng nước trong bình x = 0 và bình y = 0
-
- In trạng thái (State): Viết hàm để in lượng nước trong bình X và bình Y.
-
- Kiểm tra trạng thái có phải trạng thái mục tiêu: Lượng nước trong bình x hoặc bình y bằng với giá trị mục tiêu (goal)
-
- Xây dựng các hành động làm thay đổi trạng thái: Trạng thái hiện tại là cur_state và kết quả sau khi thực hiện thao tác/ hành động được lưu vào *result. Nếu thao tác thực hiện thành công thì kết quả trả về là 1 (int), ngược lại trả về 0.
STT Tên hàm Ý nghĩa hàm 1 int pourWaterFullX(State cur_state, State *result) Làm đầy nước bình X. Sử dụng vòi bom để bom đầy nước cho bình X. 2 int pourWaterFullY(State cur_state, State *result) Làm đầy nước bình Y. Sử dụng vòi bom để bom đầy nước cho bình Y. 3 int pourWaterEmptyX(State cur_state, State *result) Làm rỗng nước bình X. Rót hết nước trong X ra ngoài. 4 int pourWaterEmptyY(State cur_state, State *result) Làm rỗng nước bình Y. Rót hết nước trong Y ra ngoài. 5 int pourWaterXY(State cur_state, State *result) Chuyển nước từ bình X sang bình Y. 6 int pourWaterYX(State cur_state, State *result) Chuyển nước từ bình X sang bình Y.
3.4. Hành động làm đầy nước bình X (pourWaterFullX): hành động này được thực hiện nếu lượng nước trong bình X < sức chứa của bình X, nghĩa là bình X chưa đầy.
3.4. Hành động làm đầy nước bình Y (pourWaterFullY): hành động này được thực hiện nếu lượng nước trong bình Y < sức chứa của bình Y, nghĩa là bình Y chưa đầy.
3.4. Hành động làm rỗng nước bình X (pourWaterEmptyX): hành động này được thực hiện nếu bình X có chứa nước (X>0).
3.4. Hành động làm rỗng nước bình Y (pourWaterEmptyY): hành động này được thực hiện nếu bình Y có chứa nước (Y>0).
3.4. Hành động chuyển nước từ bình X sang bình Y (pourWaterXY): hành động này được thực hiện nếu bình X có chứa nước (x>0) và bình Y chưa đầy (y<tankcapacity_Y). Lưu ý: Cần viết hai hàm max và min của hai số nguyên x và y trước khi viết hàm chuyển nước từ bình X sang bình Y.
Kết quả chương trình:
-
- Mô hình minh họa dựng cây tìm kiếm – duyệt theo chiều sâu: Lưu ý: Những cung triển khai không gian trạng thái có màu xanh (đậm) là phép toán tương ứng hợp lệ, những cung màu đỏ (nhạt) là những phép toán triển khai không hợp lệ.
Lượng nước
bình Y
Lượng nước
bình X
0, 0
0, 0 0, 0
Làm rỗng
X
Làm rỗng
Y
0, 4 0, 0
Chuyển
nước Y -> X
0, 0
Chuyển
nước X -> Y
Làm đầy
Y
Làm đầy
X
9, 4 0, 4 0, 4 0, 0 0, 4 4, 0
Làm
rỗng Y
9, 0
Làm đầy
X
Làm đầy
X
Làm đầy
Y
Làm đầy
Y
Làm rỗng
X
Làm rỗng
X
Làm rỗng
Y ChuyX -> Yển nước
Chuyển nước
X -> Y
Chuyển nước
Y -> X
Chuyển nước
Y -> X
4, 4
0, 0 4, 0 0, 4 4, 0
9, 0
-
- Kiểm tra trạng thái Quá trình duyệt cây tìm kiếm không gian trạng thái, chúng ta cần kiểm tra xem trạng thái mới sinh ra có tồn tại trong ngăn xếp (Open/ Close) hay chưa, để tránh vòng lặp xảy ra trong quá trình duyệt. Hàm find_State dùng để kiểm tra xem trang thái có tồn tại trong Ngăn xếp hay chưa?
-
- Duyệt chiều sâu trên Cây tìm kiếm không gian trạng thái (depth-first search): // Giải thuật tìm kiếm theo chiều sâu depth-first search (dfs) Procedure depth – first – search; Begin % khởi đầu Open:= [start]; Closed:= [ ]; // được cài đặt bằng ngăn xếp While open ≠ [ ] do % còn các trạng thái chưa khảo sát Begin Lấy một phần tử từ ngăn xếp open, gọi nó là X; If X là mục tiêu then trả lời kết quả (thành công) % tìm thấy đích else begin Phát sinh các con của X; Đưa X vào ngăn xếp closed; Loại các con của X nằm trong open hoặc closed; Đưa các con còn lại vào ngăn xếp open; End; Trả lời kết quả (thất bại); % không còn trạng thái nào End; //
-
- In kết quả duyệt chiều sâu:
-
- Bài tập 2: Biểu diễn trạng thái và các phép toán (hành động) của bài toán, gọi các hành động và xây dựng cây tìm kiếm không gian trạng thái theo chiều sâu cho bài toán đong nước. Các bước thực hiện: Khai báo các hằng cần thiết cho bài toán đong nước Khai báo cấu trúc trạng thái: State Cài đặt các hàm hành động chuyển trạng thái: hàm làm đầy nước, làm rỗng bình, chuyển nước từ bình x sang bình y và ngược lại, và những hàm liên quan đến State. Cài đặt cấu trúc Node để hỗ trợ xây dựng cây trong quá trình duyệt. Cài đặt cấu trúc ngăn xếp để lưu trữ trạng thái duyệt. Cài đặt thuật toán toán duyệt theo chiều sâu (DFS) Cài đặt hàm in kết quả tìm kiếm. Viết hàm main() cho chương trình.
-
- Bài tập 3: Biểu diễn trạng thái và các phép toán (hành động) của bài toán, gọi các hành động và xây dựng cây tìm kiếm không gian trạng thái theo chiều rộng (DBF) cho bài toán đong nước. Các bước thực hiện: Khai báo các hằng cần thiết cho bài toán đong nước Khai báo cấu trúc trạng thái: State Cài đặt các hàm hành động chuyển trạng thái: hàm làm đầy nước, làm rỗng bình, chuyển nước từ bình x sang bình y và ngược lại, và những hàm liên quan đến State. Cài đặt cấu trúc Node để hỗ trợ xây dựng cây trong quá trình duyệt. Cài đặt cấu trúc Hàng đợi (QUEUE) để lưu trữ trạng thái duyệt. Cài đặt thuật toán toán duyệt theo chiều rộng (BFS). Sinh viên lưu ý Open và Close được khai báo kiểu QUEUE và sử dụng các hàm tương ứng với QUEUE để đưa một phần tử vào hàng đợi hoặc lấy một phần tử từ hàng đợi. Cài đặt hàm in kết quả tìm kiếm. Viết hàm main() cho chương trình. Mô hình minh họa cây tìm kiếm, duyệt theo chiều rộng: Lưu ý: Những cung triển khai không gian trạng thái có màu xanh (đậm) là phép toán tương ứng hợp lệ, những cung màu đỏ (nhạt) là những phép toán triển khai không hợp lệ.
Cài đặt cấu trúc hàng đợi
-
- Bài tập 4: Sử dụng thư viện C++. Biểu diễn trạng thái và các phép toán (hành động) của bài toán, gọi các hành động và xây dựng cây tìm kiếm không gian trạng thái theo chiều sâu (DFS) cho bài toán đong nước. Để duyệt theo chiều sâu, chúng ta cần sử dụng Ngăn xếp (Stack) để lưu trữ các đỉnh trong quá trình duyệt. Bài tập này các em không cần cài đặt cấu trúc Stack mà các em sử dụng
Hàm in kết quả tìm kiếm trạng thái:
Hàm kiểm tra xem một trạng thái có thuộc ngăn xếp (Open/Close)
Chương trình cài đặt tìm kiếm trạng thái với sự hỗ trợ của STL.
-
- Bài tập 5: Sử dụng thư viện C++ Biểu diễn trạng thái và các phép toán (hành động) của bài toán, gọi các hành động và xây dựng cây tìm kiếm không gian trạng thái theo chiều rộng (BFS) cho bài toán đong nước. Để duyệt theo chiều rộng, chúng ta cần sử dụng Hàng đợi (Queue) để lưu trữ các đỉnh trong quá trình duyệt. Bài tập này các em không cần cài đặt cấu trúc Queue mà các em sử dụng thư viện có sẵn của thư viên STL. Để sử dụng tính năng này, em phải viết chương trình bằng ngôn ngữ C++ và phải đặt tên chương trình có phần mở rộng *.cpp hoặc *.cc. Các bước thực hiện: Khai báo các hằng cần thiết cho bài toán đong nước Khai báo cấu trúc trạng thái: State Cài đặt các hàm hành động chuyển trạng thái: hàm làm đầy nước, làm rỗng bình, chuyển nước từ bình x sang bình y và ngược lại, và những hàm liên quan đến State.