Các lựa chọn cần rõ đến mức thực hiện được
Một robot không có bản đồ nhưng cảm nhận được tường bên phải, phía trước và bên trái. Với quy tắc **bám tường bên phải**, ở mỗi lượt robot kiểm: nếu phải trống thì quay phải 90° rồi tiến một bước; nếu phải bị chặn nhưng trước trống thì tiến một bước; nếu cả phải và trước bị chặn thì quay trái 90° rồi kiểm lại. **Quay** chỉ đổi hướng; **rẽ** trong trường hợp đầu gồm quay và tiến. Có thể viết những bước này thành danh sách hoặc sơ đồ khối.
Bài luyện
Robot bám tường bên phải: bên phải bị chặn, phía trước trống. Nó làm gì theo quy tắc đã nêu?
Đi sang phải bị tường chặn.
Chỉ xét trái khi cả phải và trước đều bị chặn.
Phía trước vẫn có lối đi.
Phải chặn nên robot dùng lựa chọn kế tiếp là đi thẳng.
Lời giải
Thứ tự ưu tiên là phải → trước → trái. Khi phải có tường còn trước trống, robot tiến thẳng một bước.
Bài luyện
Cả bên phải và phía trước đều có tường. Vì sao lệnh “quay trái 90°” chưa phải là “rẽ trái một bước”?
Robot còn ở vị trí cũ sau lệnh quay.
Quay không tự làm robot đi lùi.
Robot không có bản đồ trong ví dụ.
Quay trái 90° đã đổi hướng sang trái.
Lời giải
Lệnh quay thay đổi hướng nhìn. Muốn sang ô bên trái, robot còn cần kiểm lối phía trước mới và lệnh tiến một bước.
Một ví dụ không bảo đảm giải mọi mê cung
Cách bám tường cho thấy thuật toán biến lựa chọn trực giác thành quy tắc rõ ràng. Nó **không luôn tìm được lối ra**: nếu robot bám một vòng tường khép kín còn lối ra nằm ở phần khác, robot có thể lặp lại. Trong mê cung ở hình minh họa của SGK, đường đi theo tường dẫn tới lối ra; khi dùng mê cung khác phải kiểm cấu trúc và điều kiện dừng. Cách đi này cũng không hứa là đường ngắn nhất.
Bài luyện
Nhận xét nào đúng về thuật toán bám tường trong bài?
Một lần quay chưa bảo đảm đến lối ra.
Một vòng tường tách khỏi lối ra có thể làm robot lặp.
Bám tường không tối ưu hóa độ dài đường.
Ví dụ không dùng bản đồ.
Lời giải
Thuật toán chỉ dựa vào tường quanh robot. Nó có thể theo mãi một vòng tường không nối tới lối ra, nên hình SGK là ví dụ minh họa theo điều kiện của mê cung đó.
Đang học