Kỹ thuật BFS tìm đường ngắn nhất trong Mê Cung

Khái niệm

Mê cung trên lưới ô là một đồ thị: mỗi ô là một đỉnh, mỗi bước đi sang ô kề không bị tường chặn là một cạnh có trọng số bằng nhau.

BFS (Breadth-First Search) duyệt theo từng lớp khoảng cách từ điểm xuất phát: trước hết mọi ô cách 1 bước, rồi 2 bước, 3 bước… Lần đầu tiên chạm ô ra chính là đường ngắn nhất, vì mọi đường dài hơn đều được xét sau.

Ví dụ

BFS xuất phát từ ô vào, mở rộng dần các ô lân cận và ghi lại "cha" của từng ô. Khi chạm ô ra, truy ngược chuỗi cha để vẽ lại đường đi tối ưu.

Đây chính là thuật toán mà bộ giải mê cung của Logicholic dùng để đưa gợi ý đường tối ưu từng bước.

Minh hoạ động