lOMoAR cPSD| 45764710 TRÍ TUỆ NHÂN TẠO Bài tập chương 2
1. Hãy xác ịnh không gian trạng thái của các bài toán sau:
1a) Bài toán ong nước: Cho 2 bình có dung tích lần lượt là m và n (lit). 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).
1b) Bài toán trò chơi sắp xếp 8 số.
1c) Bài toán Tháp Hà nội.
1d) Bài toán người ưa hàng: Người ưa hàng cần phải xác ịnh ược hành trình ngắn nhất
sao cho mỗi thành phố i ến úng một lần và quay trở lại thành phố xuất phát. Giả sử thành
phố xuất phát là thành phố 1, có tất cả n thành phố ánh số từ 1 ến n.
(Hướng dẫn: Mỗi trạng thái cho bởi danh sách các thành phố ã i qua cho ến thời iểm hiện
tại, trong ó không cho phép một thành phố nào ược xuất hiện nhiều hơn một lần trừ thành
phố 1 sau khi ã liệt kê tất cả các thành phố còn lại.
Các toán tử tương ứng với các hành ộng:
i tới thành phố 1 i tới thành phố 2 i tới thành phố 3).
2. Hãy biểu diễn không gian trạng thái của các bài toán trên bởi danh sách kề.
3. Thực hiện tìm kiếm theo bề rộng cho các bài toán: 1a) với m = 5, n= 4, k =3. 1b)
4. Thực hiện tìm kiếm theo chiều sâu cho các bài toán:
1a) với m = 5, n= 4, k =3 1c).
5. Thực hiện tìm kiếm leo ồi cho bài toán 1b).
6. Cho một không gian các trạng thái mà ở ó trạng thái ầu có nhãn là số 1, trạng thái tiếp
theo trạng thái có nhãn n là các trạng thái có nhãn là 2n và 2n+1. a)
Hãy viết một phần của không gian trạng thái với các nhãn từ 1 ến 15. b)
Giả sử trạng thái ích có nhãn là 11, hãy liệt kê thứ tự mà các ỉnh sẽ ược thăm
khi sử dụng các thủ tục tìm kiếm theo chiều rộng (breadth-firsth), tìm kiếm theo chiều
sâu (depth-first), tìm kiếm theo chiều sâu lặp (dept-limited search) với ộ sâu 3?
7. Hình vẽ sau ây cho biết một phần của cây tìm kiếm mở rộng. Mỗi cạnh có gán chi phí
thực hiện toán tử tương ứng, các lá cho biết giá trị của hàm heuristic, h.
Nút nào (chỉ ra bằng ký tự chữ cái) sẽ ược mở rộng tiếp theo nếu sử dụng một trong các
giải thuật tìm kiếm sau: a) Depth-first search? b) Breadth-first search? c) Best First Search (Best-FS) d) A* search? lOMoAR cPSD| 45764710 A h=20 3 B 5 19 C D 6 h=18 4 h=15 5 5 E F G H h=10 h=12 h=0 h=10
8. Trò chơi bốc bi: Có 2 ống bi có số bi lần lượt là m và n viên bi. Hai người chơi, mỗi
người ến lượt mình i chỉ ược phép bốc tối a k viên. a)
Xây dựng không gian tìm kiếm với m=10, n=8, k=5 b)
Cài ặt giải thuật minimax cho máy (người chơi thứ nhất là máy và người chơi thứ
hai là người sử dụng chương trình)?
9. Xem xét cây trò chơi cho trong hình dưới ây. Các giá trị của hàm ịnh giá ược cho bên
cạnh các nút lá. Giả sử nút gốc tương ứng với người chơi ở mức MAX, và việc tìm
kiếm luôn luôn ược thực hiện trên các con từ trái sang phải. a)
Tính toán giá trị cho các nút theo giải thuật minimax. Kết quả viết cạnh các nút tương ứng trên cây. b)
Tính toán giá trị cho các nút theo giải thuật alpha-beta. Những nút nào sẽ không
ược kiểm tra nếu sử dụng giải thuật alpha-beta pruning? c)
Max nên chọn i nhánh nào nếu tất cả các giá trị ã ược tính? A Max Min B C D E Max F G H I J K Min L M N O P Q R S T U V W X Y 2 3 8 5 7 6 0 1 5 2 8 4 10 2
10. Cho một phần của cây trò chơi như sau:
a. vẽ thêm các trạng thái ứng với ộ sâu d =3 lOMoAR cPSD| 45764710
b. Xác ịnh giá trị cho các nút lá trên cây (các nút ở ộ sâu d=3) theo hàm ánh giá ã xây dựng
trong bài giảng sau ó gán giá trị cho các nút trong của cây theo chiến lược minimax.
c. Xác ịnh giá trị cho các nút trên cây theo giải thuật alpha-beta. Những nút nào sẽ không
ược kiểm tra nếu sử dụng giải thuật alpha-beta pruning?
11. Cài ặt giải thuật tìm kiếm leo ồi.
12. Demo ít nhất 2 giải thuật tìm kiếm trên cây trò chơi ã học (tham khảo trên website AIMA).