Mê cung tìm đường

Mô phỏng này cho phép học sinh xem ba thuật toán tìm đường tìm kiếm trong mê cung. Các ô đã khám phá chuyển màu xanh lam, biên là màu hổ phách, và đường đi cuối cùng phát sáng màu xanh lá. Học sinh chọn A sao, Dijkstra hoặc BFS, thay đổi tốc độ, bật hoặc tắt bùn tốn kém và tạo mê cung mới. Các chỉ số hiển thị số nút đã khám phá, độ dài đường đi và chi phí đường đi. Khi bật bùn, BFS tìm đường ngắn nhất về số bước nhưng không rẻ nhất, còn A sao khám phá ít ô hơn nhiều. Mô phỏng hữu ích cho các bài tin học về thuật toán và các đánh đổi.

• Chạy A* trên mê cung và ghi nhận Số nút đã khám phá, Độ dài đường đi và Chi phí đường đi.
• Đổi Thuật toán sang Dijkstra rồi sang BFS trên cùng một mê cung và so sánh ba chỉ số.
• Tắt Bùn (chi phí 3) và xem liệu ba đường có chi phí bằng nhau không.
• Nhấn Mê cung mới và dự đoán thuật toán nào sẽ khám phá nhiều ô nhất.
• Giảm Bước/s xuống để xem vùng xanh lam đã khám phá và biên màu hổ phách lan rộng ra sao.

1. 1So sánh cách BFS, Dijkstra và A sao khám phá một mê cung.
2. 2Giải thích sự khác nhau giữa đường ngắn nhất và đường rẻ nhất.
3. 3Mô tả cách heuristic giúp A sao khám phá ít ô hơn.
4. 4Dùng số ô đã khám phá để đánh giá hiệu quả của một thuật toán.

Câu hỏi giáo viên thường đặt ra