Tìm đường trong mê cung – BFS, DFS và A*

Bài toán tìm đường là ví dụ điển hình của chủ đề Giải quyết vấn đề với sự trợ giúp của máy tính: mê cung được mô hình hoá thành lưới ô, mỗi bước đi sang một ô kề với giá như nhau. Tìm kiếm theo chiều rộng (BFS) dùng hàng đợi, tìm kiếm theo chiều sâu (DFS) dùng ngăn xếp, còn A* dùng hàng đợi ưu tiên theo f = g + h với h là khoảng cách theo ô ngang dọc tới đích. Chọn thuật toán, bấm Chạy hoặc Từng bước. Ô màu cam là ô đang chờ, số 1, 2, 3… cho biết thứ tự sẽ được lấy ra; ô đã xét tô màu đậm dần theo số bước từ điểm xuất phát nên thấy rõ BFS lan ra như sóng còn DFS đâm sâu theo một hướng. Khi tới đích, đường đi hiện màu đỏ và bảng kết quả ghi số ô đã xét, độ dài đường và cho biết đó có phải đường ngắn nhất không. Có thể vẽ tường, kéo điểm xuất phát và đích, chọn mê cung có vòng, chướng ngại ngẫu nhiên hoặc lưới trống. Câu hỏi gợi ý: – Vì sao đường BFS tìm được luôn ngắn nhất, còn đường của DFS thì không? – Trên lưới trống, thuật toán nào xét ít ô nhất? Vì sao? – Khi nào DFS tìm tới đích nhanh hơn BFS?