Tìm theo chiều rộng (BFS — breadth-first search) là cách tìm đường ngắn nhất bằng cách lan ra từng "lớp": trước hết xét mọi nơi đi được trong 1 bước, rồi mọi nơi đi được trong 2 bước, rồi 3 bước… cho tới khi chạm đích. Lần đầu tiên chạm đích chắc chắn là đường ngắn nhất, vì mọi đường ngắn hơn đều đã được xét trước. Đây là thuật toán mà máy tính dùng để tìm số bước ít nhất cho câu đố trượt trên băng, câu đố 15, mê cung. Khi các bước có độ dài khác nhau, như đường trên bản đồ, người ta dùng thuật toán Dijkstra và A*.
Hình dung bằng giọt mực
Nhỏ một giọt mực vào giữa tờ giấy thấm. Mực loang ra thành vòng tròn, mỗi giây rộng thêm một chút. Nếu tờ giấy có những đường cắt (tường mê cung), mực lan theo các lối còn mở. Điểm nào bị mực chạm tới trước tiên là điểm gần nhất theo đường đi. Tìm theo chiều rộng làm đúng như vậy, chỉ là theo từng bước rời rạc thay vì liên tục.
Thuật toán từng bước
- Đặt điểm xuất phát vào một hàng đợi (như hàng người xếp hàng mua vé: ai vào trước được phục vụ trước). Ghi "khoảng cách = 0".
- Lấy điểm đầu hàng ra. Xét mọi nơi đi được từ đó trong một bước.
- Với mỗi nơi chưa từng ghé, ghi khoảng cách bằng khoảng cách của điểm hiện tại cộng 1, ghi lại "đến từ đâu", và cho vào cuối hàng đợi.
- Lặp lại bước 2–3 cho tới khi lấy ra được điểm đích, hoặc hàng đợi rỗng (không có đường).
- Lần ngược theo các ghi chú "đến từ đâu" từ đích về xuất phát để có đường đi.
Hai chi tiết quan trọng: đánh dấu nơi đã ghé để không xét lại (nếu không, thuật toán có thể đi vòng mãi), và dùng hàng đợi vào trước ra trước để đảm bảo xét hết các nơi cách 1 bước trước khi xét nơi cách 2 bước.
Áp dụng cho câu đố trượt trên băng
Với câu đố trượt, mỗi "nơi" là một trạng thái (vị trí vật), mỗi "bước" là một lần trượt theo một trong bốn hướng. Từ mỗi trạng thái có tối đa bốn trạng thái kế tiếp.
| Lớp (số bước) | Những vị trí có thể tới (ví dụ) |
|---|---|
| 0 | Vị trí xuất phát |
| 1 | Tối đa 4 điểm dừng sau một lần trượt |
| 2 | Các điểm dừng mới từ các điểm ở lớp 1, bỏ những điểm đã gặp |
| 3 | Tiếp tục lan ra… |
| k | Lớp đầu tiên chứa ô đích: k là số bước ít nhất |
Vì số điểm dừng thường không nhiều, BFS giải một câu đố trượt cỡ vừa trong chưa tới một phần nghìn giây. Nó không chỉ cho biết số bước ít nhất mà còn cho biết có bao nhiêu đường ngắn nhất khác nhau — điều quan trọng khi thiết kế câu đố có đúng một lời giải tối ưu (bài tự đặt câu đố hay).
Lịch sử ngắn
- Năm 1945: kỹ sư máy tính Đức Konrad Zuse mô tả một phương pháp giống BFS trong luận văn về ngôn ngữ lập trình Plankalkül của ông (chỉ được công bố rộng rãi nhiều năm sau).
- Năm 1959: Edward F. Moore (Phòng thí nghiệm Bell, Mỹ) công bố thuật toán tìm đường ngắn nhất trong mê cung, thường được coi là mô tả BFS kinh điển.
- Năm 1956–1959: Edsger Dijkstra (Hà Lan) nghĩ ra thuật toán tìm đường ngắn nhất khi các cạnh có độ dài khác nhau. Ông kể đã nghĩ ra nó trong khoảng hai mươi phút khi ngồi uống cà phê ở Amsterdam cùng vị hôn thê, công bố năm 1959.
- Năm 1968: Peter Hart, Nils Nilsson và Bertram Raphael (Viện Nghiên cứu Stanford) công bố thuật toán A*, kết hợp Dijkstra với một "ước lượng khoảng cách còn lại" để tìm nhanh hơn. Thuật toán ra đời trong dự án robot Shakey.
BFS, Dijkstra và A*: khác nhau thế nào
| Thuật toán | Dùng khi | Ý tưởng | Ví dụ ứng dụng |
|---|---|---|---|
| Tìm theo chiều rộng (BFS) | Mọi bước có "giá" như nhau | Lan ra từng lớp theo số bước | Câu đố trượt, mê cung, số người trung gian giữa hai người trên mạng xã hội |
| Dijkstra | Các bước có độ dài, chi phí khác nhau (không âm) | Luôn mở rộng điểm có tổng quãng đường nhỏ nhất hiện tại | Định tuyến mạng, bản đồ |
| A* | Như Dijkstra, và có cách ước lượng khoảng cách còn lại tới đích | Ưu tiên điểm có "quãng đã đi + ước lượng còn lại" nhỏ nhất | Ứng dụng chỉ đường, robot, câu đố 15 |
| Tìm theo chiều sâu (DFS) | Chỉ cần tìm một đường, không cần ngắn nhất | Đi sâu hết một nhánh rồi mới quay lại | Sinh mê cung, kiểm tra có đường hay không |
Với câu đố 15, A* dùng ước lượng "tổng khoảng cách Manhattan" — mỗi miếng số cách vị trí đúng bao nhiêu ô theo hàng và cột. Ước lượng này không bao giờ vượt quá số nước thật cần, nên A* vẫn đảm bảo tìm ra lời giải ngắn nhất, nhưng nhanh hơn BFS hàng nghìn lần.
Giới hạn: bùng nổ tổ hợp
BFS phải nhớ mọi trạng thái đã ghé. Với câu đố có quá nhiều trạng thái — như câu đố 15 với hơn 10 nghìn tỷ trạng thái, hay cờ vua — bộ nhớ không đủ. Đó là lúc cần những kỹ thuật thông minh hơn: A* với ước lượng tốt, tìm kiếm hai chiều (lan từ cả xuất phát và đích, gặp nhau ở giữa — chỉ cần lan khoảng một nửa số bước mỗi bên), hay cắt bỏ các trạng thái chắc chắn vô ích như "thế chết" trong câu đố đẩy thùng.
Góc nhìn hôm nay: chạy BFS bằng bút chì
- Vẽ một mê cung nhỏ trên giấy kẻ ô (8 × 8).
- Viết số 0 vào ô xuất phát.
- Viết số 1 vào mọi ô trống kề ô số 0.
- Viết số 2 vào mọi ô trống chưa có số kề ô số 1. Cứ thế tiếp tục.
- Khi ô đích có số, đó là số bước ít nhất. Lần ngược từ đích, mỗi lần bước sang ô có số nhỏ hơn 1 đơn vị, sẽ ra đường ngắn nhất.
Cách làm này đôi khi được gọi là "thuật toán lan sóng" (wavefront), dùng trong định tuyến dây nối trên bảng mạch điện tử từ thập niên 1960. Sau khi làm bằng tay một lần, trẻ sẽ hiểu máy tính "nghĩ" thế nào khi tìm đường.
Câu hỏi thường gặp
Tìm theo chiều rộng là gì?
Là thuật toán tìm đường bằng cách xét lần lượt mọi nơi đi được trong 1 bước, rồi 2 bước, rồi 3 bước, dùng hàng đợi và đánh dấu nơi đã ghé. Lần đầu tiên chạm đích chính là đường ngắn nhất khi mọi bước có giá như nhau.
Vì sao tìm theo chiều rộng luôn ra đường ngắn nhất?
Vì thuật toán xét hết mọi nơi cách k bước trước khi xét nơi cách k + 1 bước. Khi đích được chạm tới lần đầu ở lớp k, mọi đường ngắn hơn đều đã được xét và không tới đích, nên k là số bước ít nhất.
Thuật toán Dijkstra khác tìm theo chiều rộng thế nào?
Dijkstra dùng khi các bước có độ dài hoặc chi phí khác nhau, như đường trên bản đồ. Nó luôn mở rộng điểm có tổng quãng đường nhỏ nhất hiện tại. Khi mọi bước dài bằng nhau, Dijkstra hoạt động giống tìm theo chiều rộng.
Thuật toán A* là gì?
A* là cải tiến của Dijkstra, công bố năm 1968, ưu tiên điểm có tổng quãng đã đi cộng ước lượng quãng còn lại tới đích nhỏ nhất. Nếu ước lượng không vượt quá thực tế, A* vẫn tìm đúng đường ngắn nhất nhưng nhanh hơn nhiều.
Máy tính tìm lời giải ngắn nhất cho câu đố thế nào?
Máy tính coi mỗi cách sắp xếp là một trạng thái và mỗi nước đi là một bước, rồi dùng tìm theo chiều rộng hoặc A* để tìm chuỗi bước ngắn nhất từ trạng thái ban đầu tới đích.