Tìm kiếm theo chiều rộng (BFS)
Thả một hòn đá xuống ao, những gợn sóng lan ra đều thành từng vòng. Tìm kiếm theo chiều rộng duyệt đồ thị theo cùng cách đó: trước hết là mọi thứ cách điểm xuất phát một bước, rồi mọi thứ cách hai bước, cứ thế tiếp tục. Chính thứ tự đơn giản đó giúp nó tìm được đường đi ngắn nhất.
Ý tưởng
Đồ thị là một tập hợp các đỉnh nối với nhau bằng cạnh: địa điểm và con đường, con người và tình bạn, các ô của mê cung và lối đi giữa chúng. Tìm kiếm theo chiều rộng trả lời câu hỏi: bắt đầu từ đây, tôi có thể tới đâu, và cần ít nhất bao nhiêu bước? Thuật toán giữ một hàng đợi các đỉnh còn phải thăm. Lấy đỉnh từ đầu và thêm đỉnh mới vào cuối nghĩa là các đỉnh được xử lý theo thứ tự được phát hiện.
Từng bước
Đưa điểm xuất phát vào hàng đợi với khoảng cách 0. Lấy đỉnh ở đầu hàng đợi. Với mỗi đỉnh kề chưa từng thấy, ghi khoảng cách của nó bằng khoảng cách của đỉnh hiện tại cộng một, ghi nhớ đỉnh hiện tại là đường nó được tới, rồi thêm nó vào cuối hàng đợi. Bỏ qua các đỉnh kề đã thấy. Lặp lại cho đến khi hàng đợi rỗng, hoặc đến khi tới đích.
Ví dụ
Xét một đồ thị có các cạnh A–B, A–C, B–D, C–D, C–E và D–F, bắt đầu từ A. Lấy A ra khỏi hàng đợi, ta tìm thấy B và C ở khoảng cách 1. Lấy B, tìm thấy D ở khoảng cách 2. Lấy C, thấy D đã được thấy rồi, và tìm thấy E ở khoảng cách 2. Lấy D, tìm thấy F ở khoảng cách 3. E và F không tìm thấy gì mới, và hàng đợi rỗng. Lần theo các đỉnh đã ghi nhớ từ F được F ← D ← B ← A, nên một đường đi ngắn nhất từ A đến F là A → B → D → F, dài ba cạnh.
Vì sao khoảng cách là đúng
Mọi đỉnh ở khoảng cách 1 vào hàng đợi trước bất kỳ đỉnh nào ở khoảng cách 2, mọi đỉnh ở khoảng cách 2 trước bất kỳ đỉnh nào ở khoảng cách 3, cứ thế tiếp tục, vì các đỉnh kề của một đỉnh chỉ được đưa vào hàng đợi khi chính đỉnh đó ra khỏi hàng đợi. Vì vậy đường đi đầu tiên tới một đỉnh là đường có ít cạnh nhất, và BFS không bao giờ phải sửa khoảng cách. Mỗi đỉnh được lấy một lần và mỗi cạnh được xét từ cả hai đầu, nên khối lượng công việc tăng theo số đỉnh cộng số cạnh.
Lịch sử và ứng dụng
Konrad Zuse mô tả tìm kiếm theo chiều rộng vào năm 1945, trong công trình về ngôn ngữ Plankalkül của ông, công trình này mãi đến năm 1972 mới được xuất bản. Edward F. Moore phát minh lại nó vào năm 1959 để tìm đường ngắn nhất ra khỏi mê cung, và C. Y. Lee dùng nó vào năm 1961 để đi dây trên bảng mạch. Ngày nay nó được dùng để tìm số nước đi ít nhất trong câu đố, số bậc cách biệt trong mạng xã hội, các trang mà trình thu thập web tới trước, và ô trống gần nhất trong trò chơi. Khi các cạnh có độ dài, thuật toán Dijkstra là dạng tổng quát của nó.
Khám phá
Mở ứng dụng và nhấn Bước. Đỉnh đang được thăm được làm nổi bật, các đỉnh đang chờ trong hàng đợi có màu xanh dương, và các đỉnh đã thăm có màu xanh lá, mỗi đỉnh kèm khoảng cách của nó. Hàng đợi hiện dưới đồ thị, đầu hàng đợi trước. Chuyển thao tác nhấp sang Đích và chọn một đỉnh để dừng ở đó và xem đường đi ngắn nhất, hoặc tạo đồ thị mới với nhiều đỉnh và cạnh hơn.
Câu hỏi thường gặp
Độ phức tạp thời gian của BFS là bao nhiêu?
O(V + E) với V đỉnh và E cạnh: mỗi đỉnh vào và ra khỏi hàng đợi một lần, và mỗi cạnh được xét từ cả hai đầu. Thuật toán cần thêm O(V) bộ nhớ cho hàng đợi và các khoảng cách.
Vì sao BFS dùng hàng đợi?
Vì vào trước, ra trước giữ các đỉnh theo thứ tự được phát hiện, cũng là thứ tự khoảng cách của chúng. Nếu dùng ngăn xếp, việc tìm kiếm sẽ đi sâu trước: đó là tìm kiếm theo chiều sâu.
BFS có tìm được đường đi ngắn nhất trong đồ thị có trọng số không?
Nói chung là không: nó đếm số cạnh, không đếm độ dài của chúng. Với đồ thị có trọng số không có cạnh âm, hãy dùng thuật toán Dijkstra. Nếu mọi trọng số đều là 0 hoặc 1, có thể dùng một biến thể gọi là 0-1 BFS.
BFS được dùng ở đâu?
Giải câu đố và mê cung với ít nước đi nhất, tìm bạn của bạn trong mạng xã hội, thu thập web theo từng mức, phát quảng bá trong mạng, và làm khối xây dựng cho các thuật toán khác như tìm luồng cực đại.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử tìm kiếm theo chiều rộng