Bài tập TTNT: nền tảng và tìm kiếm
Luyện về tác tử và các thuật toán tìm kiếm (Phần I và II). Tự làm trước, bí thì mở Gợi ý. Lời giải chi tiết nằm trong từng bài học tương ứng.
Bài 1: phân loại môi trường
Robot hút bụi tự hành trong một căn hộ có người và thú cưng đi lại. Hãy phân loại môi trường này theo các trục: quan sát được hay không, tất định hay ngẫu nhiên, tĩnh hay động.
Gợi ý
Robot chỉ thấy quanh nó (quan sát một phần), kết quả hành động có thể lệch (ngẫu nhiên), và người, thú cưng di chuyển nên môi trường thay đổi cả khi robot không làm gì (động). Xem lại bài Tác tử thông minh.
Bài 2: BFS hay DFS thăm trước
Cho đồ thị có A nối B và C; B nối D; C nối D. Bắt đầu từ A. BFS và DFS thăm các nút theo thứ tự nào? Quy ước: khi một nút có nhiều hàng xóm chưa thăm, luôn xét B trước C.
Gợi ý
BFS dùng hàng đợi FIFO nên đi theo tầng. Thăm A, đưa B rồi C vào hàng đợi. Lấy B ra thăm, đưa D vào. Lấy C ra thăm, D đã nằm trong hàng đợi nên không thêm lại. Cuối cùng lấy D. Thứ tự: A, B, C, D.
DFS lao sâu hết một nhánh rồi mới quay lui. Thăm A, xét hàng xóm đầu tiên là B nên đi xuống B. Từ B, hàng xóm chưa thăm là D nên đi tiếp xuống D. Từ D, hàng xóm chưa thăm là C nên đi xuống C. Tới đây không còn nút mới, thuật toán quay lui rồi dừng. Thứ tự: A, B, D, C.
Một chỗ rất dễ nhầm khi cài DFS bằng ngăn xếp tường minh: ngăn xếp là LIFO nên nút đẩy vào
sau lại được lấy ra trước. Nếu đẩy B rồi C thì C nằm trên cùng và bị lấy trước, cho ra
A, C, D, B, tức là ngược với quy ước xét B trước C. Muốn ngăn xếp tôn trọng đúng quy ước
đó thì phải đẩy hàng xóm theo thứ tự ngược lại (đẩy C trước, B sau) để B nằm trên cùng.
Bản DFS đệ quy không gặp bẫy này vì nó duyệt hàng xóm đúng theo thứ tự bạn viết.
Xem lại các bài Tìm kiếm theo bề rộng (BFS) và Tìm kiếm theo chiều sâu (DFS).
Bài 3: tính f = g + h trong A*
Một nút có chi phí đã đi g = 4 và heuristic h = 5. Một nút khác có g = 6, h = 2.
A* sẽ mở rộng nút nào trước?
Gợi ý
Tính f = g + h cho cả hai: nút một có f = 9, nút hai có f = 8. A* luôn lấy f nhỏ
nhất trước, nên mở rộng nút hai. Xem lại bài Tìm kiếm A*.
Bài 4: heuristic có phóng đại không
Chi phí thực từ nút X tới đích là 7. Một heuristic gán h(X) = 9. Heuristic này có làm
A* mất tính tối ưu không?
Gợi ý
h(X) = 9 lớn hơn chi phí thực 7, tức phóng đại (không admissible). A* có thể bỏ
qua đường tối ưu qua X và trả về lời giải đắt hơn. Heuristic phải luôn nhỏ hơn hoặc bằng
chi phí thực còn lại. Xem lại bài Tìm kiếm A*.
Bài 5: cực trị địa phương
Giải thích vì sao leo đồi có thể dừng ở một điểm không phải lời giải tốt nhất, và nêu một cách khắc phục.
Gợi ý
Leo đồi chỉ đi lên nên kẹt ở cực trị địa phương: mọi hàng xóm đều kém hơn nhưng đó chưa phải đỉnh toàn cục. Khắc phục: cho phép thỉnh thoảng đi xuống (tôi luyện mô phỏng), hoặc khởi động lại ngẫu nhiên nhiều lần. Xem lại bài Tìm kiếm cục bộ.
Bài 6: tính giá trị minimax
Một cây trò chơi: nút gốc là lượt MAX, có hai con là nút MIN. Con trái có hai lá 3 và 5; con phải có hai lá 2 và 9. Giá trị minimax của gốc là bao nhiêu?
Gợi ý
Tính từ lá lên: con trái (MIN) chọn nhỏ nhất là 3; con phải (MIN) chọn nhỏ nhất là 2. Gốc (MAX) chọn lớn nhất giữa 3 và 2, tức là 3. Xem lại bài Tìm kiếm đối kháng.
Bài 7: BFS đầy đủ nhưng tốn bộ nhớ
Một cây tìm kiếm có mỗi nút sinh ra 10 nút con, lời giải nằm ở độ sâu 6. Vì sao BFS dễ cạn bộ nhớ trong khi DFS vẫn chạy được trên cùng cây này? Đổi lại DFS có rủi ro gì?
Gợi ý
BFS phải giữ cả một tầng biên, số nút cỡ b mũ d, tức khoảng 10 mũ 6 nút, tăng theo
hàm mũ theo độ sâu. DFS chỉ giữ một nhánh đang đi cùng các anh em của nó, bộ nhớ cỡ
b*m nên nhẹ hơn nhiều. Đổi lại, nếu một nhánh sâu vô hạn thì DFS có thể lao mãi và không
đầy đủ. Xem lại các bài BFS và DFS.
Bài 8: khi heuristic bằng không
Trong A*, nếu đặt h(n) = 0 cho mọi nút thì thuật toán rút gọn về thuật toán tìm kiếm
nào đã học? Việc này có làm mất tính tối ưu không?
Gợi ý
Khi h = 0 thì f = g + h = g, chỉ còn chi phí đã đi, nên A* trở thành tìm kiếm theo chi
phí đều (Dijkstra). h = 0 không bao giờ phóng đại nên vẫn chấp nhận được, A* vẫn tối ưu,
chỉ là mất định hướng nên phải mở rộng nhiều nút hơn. Xem lại bài Tìm kiếm A*.
Bài 9: cắt tỉa alpha-beta có đổi kết quả không
Một cây trò chơi được minimax cho giá trị gốc là 7. Nếu chạy cắt tỉa alpha-beta trên đúng cây đó, giá trị gốc thu được là bao nhiêu, và thứ gì thực sự thay đổi?
Gợi ý
Alpha-beta chỉ bỏ qua những nhánh chắc chắn không thể ảnh hưởng tới lựa chọn của gốc, nên giá trị gốc vẫn đúng bằng 7. Thứ thay đổi là số nút phải duyệt (ít hơn), không phải đáp án. Xem lại bài Tìm kiếm đối kháng.
Bài 10: đếm số nút BFS phải mở
Một cây tìm kiếm có mỗi nút sinh ra đúng 2 nút con (b = 2), lời giải nằm ở độ sâu
d = 4. Ước lượng số nút BFS phải sinh ra trong trường hợp xấu nhất để chạm tới độ sâu 4,
và so sánh với bộ nhớ mà DFS cần trên cùng cây.
Gợi ý
BFS sinh hết từng tầng: tầng 0 có 1 nút, tầng 1 có 2, tầng 2 có 4, tầng 3 có 8, tầng 4 có
16, tức 2 mũ độ sâu. Cộng lại 1 + 2 + 4 + 8 + 16 = 31 nút cho tới tầng 4, riêng tầng
sâu nhất đã là 16 nút. DFS chỉ giữ một nhánh đang đi cùng các anh em, bộ nhớ cỡ b*d = 2*4 = 8 nút, nhẹ hơn nhiều dù có thể phải duyệt lại nhiều đường. Xem lại các bài BFS và
DFS.
Bài 11: heuristic nào chấp nhận được
Với ba nút, heuristic gán các giá trị h(A) = 3, h(B) = 6, h(C) = 4. Chi phí thực còn
lại tới đích là h*(A) = 5, h*(B) = 4, h*(C) = 4. Heuristic ở nút nào phá vỡ tính chấp
nhận được?
Gợi ý
Chấp nhận được nghĩa là h không vượt quá chi phí thực h*. So từng nút: A có 3 <= 5
đạt, C có 4 <= 4 đạt (bằng vẫn được), nhưng B có 6 > 4 nên phóng đại. Chỉ cần một nút
phóng đại là A* có thể mất tính tối ưu. Xem lại bài Tìm kiếm A*.
Bài 12: một bước cắt tỉa alpha-beta
Cây trò chơi: gốc MAX có hai con MIN. Con trái có hai lá 3 và 5; con phải có hai lá 2 và 9. Duyệt từ trái sang phải. Sau khi biết giá trị con trái, tới con phải bạn đọc lá 2 trước. Có cần đọc lá 9 nữa không, và giá trị gốc là bao nhiêu?
Gợi ý
Con trái (MIN) cho min(3, 5) = 3, nên gốc MAX đã chắc chắn được ít nhất 3 (alpha = 3).
Sang con phải, đọc lá đầu là 2: vì đây là nút MIN, giá trị của nó chỉ có thể nhỏ hơn hoặc
bằng 2, mà 2 < alpha = 3 nên gốc sẽ không bao giờ chọn con phải. Lá 9 bị cắt bỏ,
khỏi cần đọc. Giá trị gốc vẫn là 3, đúng như minimax đầy đủ. Xem lại bài Tìm kiếm đối
kháng.
Bài 13: leo đồi kẹt ở đâu
Trên bảy vị trí 1..7, hàm mục tiêu nhận các giá trị [1, 3, 2, 4, 6, 5, 7] (giá trị càng
cao càng tốt). Leo đồi bắt đầu ở vị trí 1 và mỗi bước chỉ chuyển sang hàng xóm kề bên có
giá trị cao hơn. Nó dừng ở đâu, và bỏ lỡ đỉnh nào?
Gợi ý
Từ vị trí 1 (giá trị 1) leo sang vị trí 2 (giá trị 3) vì cao hơn. Tại vị trí 2, hai hàng xóm là vị trí 1 (giá trị 1) và vị trí 3 (giá trị 2), cả hai đều thấp hơn 3, nên leo đồi dừng lại ở vị trí 2, một cực trị địa phương. Nó bỏ lỡ đỉnh toàn cục ở vị trí 7 (giá trị 7) vì phải đi xuống qua vị trí 3 mới sang được. Xem lại bài Tìm kiếm cục bộ.
Bài 14: tác tử phản xạ hay dựa mục tiêu
Hai hệ thống: (a) máy điều nhiệt bật lò sưởi ngay khi nhiệt độ xuống dưới 20 độ và tắt khi vượt 22 độ; (b) robot giao hàng lập lộ trình tới cửa nạp điện khi pin yếu, cân nhắc nhiều đường đi. Mỗi hệ thuộc loại tác tử nào?
Gợi ý
Máy điều nhiệt chỉ ánh xạ trực tiếp cảm biến hiện tại sang hành động theo luật cố định, nó là tác tử phản xạ đơn giản, không hình dung tương lai. Robot cân nhắc các đường đi để đạt đích nạp điện, nó là tác tử dựa trên mục tiêu, có xét kết quả hành động dẫn tới đâu. Xem lại bài Tác tử thông minh.
Câu hỏi tự kiểm
- 1BFS đảm bảo tìm ra đường đi rẻ nhất khi nào?
- 2Nhược điểm bộ nhớ chính của BFS trên cây phân nhánh rộng và sâu là gì?
- 3A* đảm bảo tối ưu khi heuristic có tính chất nào?
- 4Leo đồi dừng lại ở điểm mà mọi hàng xóm đều kém hơn nhưng đó chưa phải điểm tốt nhất toàn cục. Đó gọi là gì?