Tìm kiếm theo bề rộng (BFS)

Ở bài trước ta đã mô tả bài toán bằng không gian trạng thái và thấy lời giải chính là một đường đi trong đồ thị. Nhưng đồ thị đó có thể rất lớn, và có nhiều đường đi tới đích. Câu hỏi bây giờ là: dò các đường đi theo thứ tự nào cho khôn ngoan. Tìm kiếm theo bề rộng (Breadth-First Search, BFS) đưa ra một câu trả lời đơn giản mà mạnh mẽ.

BFS luôn mở rộng nút nông nhất trước: thăm hết mọi nút ở độ sâu d rồi mới sang độ sâu d+1. Nó duyệt đồ thị theo từng tầng, lan ra như sóng nước từ điểm bắt đầu. Hãy hình dung thả một viên sỏi xuống mặt hồ: sóng lan thành từng vòng tròn đồng tâm, vòng gần trước, vòng xa sau. BFS xét các nút đúng theo thứ tự đó, gần trước xa sau, nên nút đầu tiên chạm tới đích chắc chắn nằm trên một đường đi ngắn nhất tính theo số bước.

Đặt vấn đề: thứ tự dò quyết định tất cả

Bạn đứng ở một ga tàu điện ngầm và muốn tới một ga khác, mỗi chuyến tàu giữa hai ga kề nhau là một bước. Nếu dò bừa, chọn đại một hướng rồi cứ thế đi, bạn vẫn có thể tới nơi, nhưng lộ trình tìm được có thể vòng vèo qua ba chục ga trong khi thật ra chỉ cần bốn chặng. Vấn đề không nằm ở chỗ đồ thị khó, mà nằm ở thứ tự bạn xét các khả năng.

Mọi thuật toán tìm kiếm không thông tin đều làm đúng một việc: lấy một nút ra khỏi tập các nút đang chờ (gọi là biên, frontier), sinh các nút kề của nó, rồi đưa nút mới vào biên. Chúng chỉ khác nhau ở luật chọn nút nào ra trước, và chính luật đó quyết định thuật toán có tìm ra lời giải hay không, lời giải có ngắn nhất hay không, và tốn bao nhiêu bộ nhớ.

BFS chọn luật đơn giản nhất: ai vào biên trước thì ra trước. Vì nút gốc vào biên đầu tiên, rồi tới các con, rồi các cháu, trật tự vào biên trùng khớp với trật tự độ sâu, nên BFS quét cạn tầng 0, rồi tầng 1, rồi tầng 2, không bao giờ nhảy cóc. Chính tính không nhảy cóc ấy cho ta lời hứa mạnh nhất của BFS: nút đích đầu tiên nó chạm tới nằm ở tầng nông nhất có chứa đích, vì nếu có lời giải ít bước hơn thì BFS đã gặp ở tầng trước rồi.

Thử ngay: BFS lan theo tầng trên đồ thị

Biên của BFS cài bằng một hàng đợi, đúng luật ai vào trước ra trước. Theo dõi hàng đợi đổi thế nào sau mỗi lần mở rộng, và để ý BFS lan theo từng tầng.

Widget dưới đây chạy thật thuật toán chứ không phát lại kịch bản gõ sẵn. Hãy đổi đỉnh xuất phát, đổi đích, hoặc chuyển sang DFS để xem thứ tự mở rộng đổi theo.

BFS trên đồ thị: hàng đợi FIFO, lan theo tầng

Thuật toánBFS (bề rộng)DFS (chiều sâu)Xuất phátABCDEFĐíchBCDEFG

Bấm vào đồ thị để đặt

1def bfs(do_thi, bat_dau, dich):
2    bien = deque([bat_dau])
3    da_tham = {bat_dau}
4    while bien:
5        nut = bien.popleft()
6        for ke in do_thi[nut]:
7            if ke not in da_tham:
8                if ke == dich:
9                    return "tim thay"
10                da_tham.add(ke)
11                bien.append(ke)
12    return None

Hàng đợi (FIFO)

A

Đã thăm (explored)

(rỗng)

Khởi tạo: đưa nút gốc A vào hàng đợi FIFO và đánh dấu A đã thăm.

1/70.5×1×2×

đang mở rộng trong biên đã thăm đường đi

Ý tưởng cốt lõi

Muốn thực hiện đúng nguyên tắc "nông nhất trước", ta cần một cấu trúc dữ liệu nhớ đúng thứ tự các nút chờ mở rộng. Cấu trúc đó là hàng đợi.

• Cấu trúc dữ liệu phù hợp với "nông nhất trước" là hàng đợi FIFO (vào trước, ra trước).
• Lấy một nút ra khỏi đầu hàng đợi, sinh các nút kề, thêm chúng vào cuối hàng đợi.
• Đánh dấu nút đã thăm để không xét lại, tránh lặp vô hạn trên đồ thị có chu trình.
• BFS kiểm tra đích ngay khi vừa sinh ra nút (không đợi tới lúc lấy ra), giúp dừng sớm.

Vì sao hàng đợi FIFO lại đúng với "nông nhất trước"? Các nút ở tầng nông vào hàng đợi trước, nên theo luật vào trước ra trước, chúng cũng được lấy ra mở rộng trước. Khi mở rộng một nút tầng d, các con của nó (tầng d+1) được đẩy xuống cuối hàng đợi, xếp sau mọi nút tầng d còn lại. Nhờ vậy toàn bộ tầng d luôn được xử lý xong trước khi động tới tầng d+1. Nếu đổi hàng đợi FIFO thành ngăn xếp LIFO (vào sau ra trước), ta sẽ lao sâu vào một nhánh trước, và đó không còn là BFS nữa mà là tìm kiếm theo chiều sâu.

Một chi tiết cài đặt quan trọng: BFS kiểm tra đích ngay khi sinh nút, không đợi tới lúc lấy nút đó ra khỏi hàng đợi. Với BFS điều này không đổi tính đúng của lời giải mà chỉ giúp dừng sớm hơn một nhịp, vì nút đích được phát hiện ngay ở tầng nông nhất mà nó xuất hiện.

Kiểm đích sớm hay kiểm đích muộn

Phép kiểm tra đích có hai chỗ để đặt. Kiểm sớm là ngay khi sinh ra một nút kề thì hỏi luôn "nó có phải đích không". Kiểm muộn là cứ đẩy nút vào biên như thường, đợi tới lúc nó được lấy ra để mở rộng mới hỏi.

Với BFS trên đồ thị chi phí bước đều, kiểm sớm vừa an toàn vừa nhanh hơn: nút đích được sinh lần đầu tiên tại đúng tầng nông nhất mà nó xuất hiện, nên dừng ngay lúc đó không làm mất đường ngắn hơn nào, mà lại khỏi phải xử lý nốt phần còn lại của tầng đang xét.

Đừng biến điều đó thành thói quen mù quáng. Khi các cạnh có chi phí khác nhau, ở tìm kiếm chi phí đồng nhất hay A sao, kiểm sớm là sai: một nút đích vừa sinh qua đường đắt vẫn có thể được sinh lại sau đó qua đường rẻ hơn, dừng ngay lần đầu là trả về lời giải không tối ưu. Ở các thuật toán đó, phép kiểm tra đích buộc phải đặt lúc lấy nút ra khỏi biên. Kiểm sớm là ưu đãi riêng của bài toán chi phí đều, không phải quy tắc chung.

Tập đã thăm: lá chắn chống lặp

Trên một cái cây, mỗi nút có duy nhất một đường từ gốc xuống nên ta không bao giờ gặp lại nó hai lần. Nhưng không gian trạng thái thật gần như luôn là đồ thị, có nhiều đường dẫn tới cùng một trạng thái và thường có cả chu trình: trong mê cung, đi phải rồi đi trái là quay về chỗ cũ. Không có gì chặn lại thì BFS sẽ đưa cái ô cũ đó vào hàng đợi thêm lần nữa, sinh tiếp các nút kề của nó, và biên phình vô hạn dù không gian trạng thái chỉ hữu hạn.

Tập da_tham là lá chắn chống điều đó. Nó bảo đảm mỗi trạng thái chỉ vào hàng đợi đúng một lần, nhờ vậy tổng số nút BFS xử lý bị chặn bởi số trạng thái phân biệt chứ không phải số đường đi (lớn hơn rất nhiều). Cái giá là bộ nhớ lưu tập đã thăm cùng chi phí tra cứu, nhưng tập hợp băm cho tra cứu trung bình O(1) nên cái giá này gần như luôn xứng đáng.

Một điểm tinh tế: nên đánh dấu đã thăm lúc đẩy nút vào hàng đợi, không đợi tới lúc lấy ra. Nếu chỉ đánh dấu lúc lấy ra, nhiều nút cha cùng tầng có thể đẩy cùng một nút con vào hàng đợi trước khi ai kịp mở rộng nó, làm hàng đợi phồng lên với các bản sao thừa.

Mã nguồn Python

from collections import deque

def bfs(do_thi, bat_dau, dich):
    bien = deque([bat_dau])        # hàng đợi FIFO
    da_tham = {bat_dau}
    cha = {bat_dau: None}          # lưu vết để dựng đường đi
    while bien:
        nut = bien.popleft()       # lấy nút nông nhất ra
        for ke in do_thi[nut]:     # xét từng nút kề
            if ke not in da_tham:
                cha[ke] = nut
                if ke == dich:     # kiểm tra đích NGAY khi sinh
                    return lan_nguoc(cha, dich)
                da_tham.add(ke)
                bien.append(ke)    # thêm vào cuối hàng đợi
    return None                    # không tới được đích

def lan_nguoc(cha, dich):          # lần theo cha để dựng đường đi
    duong = []
    nut = dich
    while nut is not None:
        duong.append(nut)
        nut = cha[nut]
    return duong[::-1]

Bốn tính chất của BFS

Gọi b là hệ số phân nhánh (số nút kề trung bình), d là độ sâu của lời giải nông nhất. Bốn tính chất dưới đây là thước đo chuẩn để đánh giá bất kỳ thuật toán tìm kiếm nào.

• Đầy đủ: có. Nếu tồn tại lời giải, BFS chắc chắn tìm ra (khi b hữu hạn). Lý do là BFS quét cạn kiệt từng tầng, nên không thể bỏ sót một đích nằm ở độ sâu hữu hạn. Điểm này khiến BFS an toàn ngay cả khi đồ thị có nhánh vô hạn, nơi tìm kiếm theo chiều sâu có thể lạc mãi vào một nhánh.
• Tối ưu: có, nếu mọi bước có chi phí bằng nhau (BFS cho đường ít bước nhất). Khi chi phí các cạnh khác nhau, BFS không còn đảm bảo rẻ nhất, vì một đường nhiều bước nhưng cạnh rẻ có thể có tổng chi phí thấp hơn một đường ít bước nhưng cạnh đắt. Lúc đó ta cần tới tìm kiếm chi phí đồng nhất (Uniform Cost Search) học ở bài sau.
• Thời gian: O(b^d), phải sinh tới chừng đó nút trong trường hợp xấu. Ở tầng d số nút cỡ b^d, và tổng các tầng nông hơn cũng cùng bậc, nên chi phí thời gian bị chi phối bởi tầng cuối cùng.
• Bộ nhớ: O(b^d), phải lưu toàn bộ biên. Đây mới là điểm yếu lớn nhất của BFS: hàng đợi phải giữ cùng lúc mọi nút của tầng đang xét, và tầng càng sâu thì càng đông.

Bộ nhớ mới là kẻ thù

Với b = 10, ở độ sâu d = 12 số nút lên tới khoảng 10^12, cần lưu cỡ một petabyte: bất khả thi. Thời gian thường là thứ ta lo trước, nhưng bộ nhớ mới là thứ giết chết BFS. Đó là lý do ta cần tới DFS và tìm kiếm lặp sâu dần (bài sau).

Vì sao bộ nhớ mới là nút thắt cổ chai

Thời gian và bộ nhớ của BFS cùng bậc O(b^d), nhưng chúng tiêu hai tài nguyên rất khác nhau. Thời gian co giãn được: chạy lâu thì ta để nó chạy qua đêm hoặc chia ra nhiều máy. Bộ nhớ thì cứng: đúng lúc biên vượt dung lượng máy, chương trình chết đột ngột, không chậm dần cho ta kịp phản ứng. Tệ hơn, tốc độ tiêu bộ nhớ bám sát tốc độ sinh nút, nên một tiến trình BFS thường hết bộ nhớ chỉ sau vài chục giây, rất lâu trước khi ta kịp sốt ruột vì nó chậm. Đây là hệ quả toán học của việc phải giữ trọn một tầng trong bộ nhớ cùng lúc, nên muốn thoát thì phải đổi chiến lược duyệt chứ tối ưu vi mô đoạn mã không cứu được.

Khi nào nên chọn BFS

BFS không phải lựa chọn mặc định cho mọi bài. Nó tỏa sáng khi hội đủ mấy điều kiện sau.

• Chi phí mỗi bước bằng nhau và ta thật sự cần đường ít bước nhất: số nước đi tối thiểu của quân mã, số chặng ít nhất giữa hai ga.
• Lời giải nằm khá nông, tức d nhỏ. Chi phí bùng nổ theo b^d, nên mỗi đơn vị độ sâu tăng thêm nhân chi phí lên b lần.
• Hệ số phân nhánh nhỏ: đồ thị thưa làm biên phồng chậm hơn hẳn đồ thị dày.
• Bộ nhớ dư dả so với kích cỡ không gian trạng thái.

Ngược lại, hãy tránh BFS khi không gian vừa sâu vừa rộng, khi các cạnh có trọng số khác nhau (dùng tìm kiếm chi phí đồng nhất), hoặc khi ta có sẵn hàm ước lượng khoảng cách tới đích (dùng A sao, học ở bài sau). Trong hai trường hợp cuối, khăng khăng dùng BFS không chỉ chậm mà còn cho lời giải sai nghĩa.

Ứng dụng thực tế

• Đường đi ngắn nhất trên đồ thị không trọng số: lộ trình ít chặng nhất, khoảng cách ngắn nhất trong mê cung hay trên lưới ô vuông của game.
• Đo khoảng cách trong mạng xã hội: "sáu độ liên hệ" chính là độ sâu BFS, tầng 1 là bạn bè, tầng 2 là bạn của bạn, và cứ thế.
• Trình thu thập web: đi từ một trang hạt giống, lấy hết liên kết ở tầng một rồi mới đi sâu hơn, để các trang gần gốc được lập chỉ mục sớm.
• Tìm thành phần liên thông và kiểm tra đồ thị hai phía: một lần quét BFS đủ để gán nhãn toàn bộ thành phần chứa nút gốc, và nếu vừa quét vừa tô hai màu xen kẽ theo tầng thì kiểm tra được đồ thị có hai phía hay không.
• Lan truyền theo tầng: mô phỏng lửa cháy lan, nước ngập dâng dần, hiệu ứng tô loang (flood fill) trong phần mềm đồ họa.

Điểm chung: chúng đều quan tâm tới khoảng cách theo số bước từ một điểm xuất phát, và đó đúng là thứ mà cách duyệt theo tầng của BFS cho ta gần như miễn phí.

BFS so với DFS

Người anh em đối lập của BFS là tìm kiếm theo chiều sâu (Depth-First Search, DFS). DFS dùng ngăn xếp LIFO thay vì hàng đợi FIFO, nên nó lao thẳng xuống một nhánh cho tới cùng rồi mới quay lui thử nhánh khác. Hai thuật toán chỉ khác nhau ở đúng một chỗ, cấu trúc dữ liệu của biên, nhưng hành vi và đánh đổi thì rất khác.

Tiêu chí	BFS (hàng đợi FIFO)	DFS (ngăn xếp LIFO)
Thứ tự duyệt	theo tầng, nông trước	theo nhánh, sâu trước
Bộ nhớ	O(b^d), rất tốn	O(b·m), tiết kiệm
Đầy đủ	có (b hữu hạn)	không, có thể lạc vào nhánh vô hạn
Tối ưu	có khi chi phí đều	không

Ở đây m là độ sâu tối đa của không gian. Điểm mạnh của DFS là bộ nhớ: nó chỉ cần nhớ đường đi hiện tại cùng các nhánh chưa duyệt dọc đường, nên tốn O(b·m), nhỏ hơn hẳn O(b^d) của BFS. Đổi lại, DFS có thể bỏ qua lời giải nông để chui sâu vào một nhánh xa, thậm chí không dừng nếu nhánh đó vô hạn. Chọn BFS khi lời giải ở gần gốc và ta cần đường ngắn nhất; chọn DFS khi không gian sâu nhưng bộ nhớ eo hẹp. Bài sau sẽ giới thiệu tìm kiếm lặp sâu dần để lấy cái tốt của cả hai: đầy đủ và tối ưu như BFS, tốn ít bộ nhớ như DFS.

Bài tập thực hành

Bài tập 1: thứ tự thăm nút

Vẫn đồ thị trong bài, nếu đích là F (thay vì G), BFS thăm các nút theo thứ tự nào và trả về đường đi gì?

Gợi ý

BFS mở rộng A, rồi B, rồi C. Khi mở rộng C nó sinh F, và F là đích nên dừng ngay. Thứ tự mở rộng: A, B, C; đường đi trả về A → C → F (2 bước).

Bài tập 2: vì sao cần tập đã thăm

Điều gì xảy ra nếu bỏ tập da_tham khi chạy BFS trên một đồ thị có chu trình (ví dụ thêm cạnh E và D nối nhau)?

Gợi ý

Không có da_tham, thuật toán sẽ thêm lại những nút đã xét vào hàng đợi mỗi khi gặp chúng qua một cạnh khác, gây lặp và có thể không bao giờ dừng (hoặc dùng bộ nhớ vô hạn). Tập đã thăm bảo đảm mỗi nút chỉ được mở rộng đúng một lần.

Bài tập 3: cài đặt trả về đường đi

Hoàn thiện hàm bfs ở trên để nó trả về đường đi (danh sách nút) thay vì chuỗi "tim thay", dùng bảng cha.

Gợi ý

Mỗi lần thêm ke vào hàng đợi, lưu cha[ke] = nut. Khi gặp đích, gọi lan_nguoc(cha, dich): bắt đầu từ đích, liên tục nhảy về cha cho tới khi gặp None, rồi đảo ngược danh sách. Phần mã đã có sẵn lan_nguoc ở mục Mã nguồn.

Tự kiểm tra

Vì sao BFS dùng hàng đợi FIFO mà không phải ngăn xếp?

Vì FIFO bảo đảm nút nào vào trước (nông hơn) thì ra trước, đúng tinh thần "mở rộng nút nông nhất". Nếu thay bằng ngăn xếp LIFO, ta sẽ đi sâu vào một nhánh trước, đó chính là DFS chứ không còn là BFS.

BFS và DFS cùng có thời gian xấu nhất là hàm mũ. Vậy vì sao nói bộ nhớ mới là khác biệt sống còn?

Vì hai thuật toán khác nhau ở công thức bộ nhớ, không phải ở thời gian. BFS tốn O(b^d), hàm mũ theo độ sâu, do phải giữ trọn một tầng trong hàng đợi cùng lúc. DFS chỉ tốn O(b·m), tuyến tính theo độ sâu, do chỉ nhớ nhánh đang đi cùng các nút kề chưa duyệt.

Khác biệt này quyết định vì thời gian là tài nguyên co giãn được, còn bộ nhớ thì cứng: vượt ngưỡng là chương trình chết ngay. Thực tế BFS thường hết bộ nhớ sau vài chục giây, tức chết vì bộ nhớ rất lâu trước khi ta kịp phàn nàn rằng nó chậm.

Nếu mỗi cạnh có một trọng số riêng, BFS còn cho lời giải tối ưu không?

Không. BFS tối ưu theo số bước, không phải theo tổng chi phí. Ví dụ: từ A có cạnh trực tiếp tới đích G chi phí 100, đồng thời có đường A tới B tới G gồm hai cạnh chi phí 1 mỗi cạnh. BFS gặp G ngay ở tầng 1 và trả về đường một bước tốn 100, trong khi đường tối ưu tốn 2.

Khi chi phí các bước bằng nhau, "ít bước nhất" trùng với "rẻ nhất" nên BFS tối ưu. Khi chúng khác nhau, phải chuyển sang tìm kiếm chi phí đồng nhất: thay hàng đợi FIFO bằng hàng đợi ưu tiên theo tổng chi phí từ gốc, và chuyển phép kiểm tra đích sang lúc lấy nút ra khỏi biên.

Câu hỏi tự kiểm

Kiểm tra nhanh: BFS0/4 đúngchưa trả lời

1. 1BFS dùng cấu trúc dữ liệu nào để quản lý biên?
2. 2BFS cho lời giải tối ưu khi nào?
3. 3Điểm yếu sống còn thật sự của BFS là gì?
4. 4Vì sao kiểm đích sớm (ngay khi sinh nút) hợp lệ với BFS chi phí đều nhưng sai với thuật toán có trọng số cạnh?

Tóm tắt

BFS trả lời câu hỏi "dò các đường theo thứ tự nào" bằng một luật đơn giản tới bất ngờ: ai vào biên trước thì ra trước. Luật ấy, hiện thân qua hàng đợi FIFO, khiến việc duyệt lan theo từng tầng và không bao giờ nhảy cóc độ sâu. Từ tính chất cấu trúc nhỏ đó, mọi thứ khác suy ra: quét cạn từng tầng nên BFS đầy đủ; nút đích đầu tiên gặp phải nằm ở tầng nông nhất chứa đích nên BFS tối ưu khi mọi bước cùng chi phí, và chỉ khi đó; phải sinh cỡ b^d nút nên thời gian O(b^d); phải giữ trọn một tầng trong hàng đợi nên bộ nhớ cũng O(b^d), và đây mới là nút thắt cổ chai thật sự.

Hai chi tiết cài đặt cần nhớ: tập đã thăm là bắt buộc chứ không phải tùy chọn, vì không gian trạng thái thật là đồ thị có chu trình; kiểm đích sớm hợp lệ với BFS chi phí đều nhưng đừng mang thói quen đó sang thuật toán có trọng số cạnh. Cuối cùng, đối chiếu với DFS cho thấy bức tranh đánh đổi: BFS mua tính đầy đủ và tính tối ưu bằng bộ nhớ, DFS mua bộ nhớ bằng cách bán đi cả hai. Bài kế tiếp sẽ cho thấy có cách lấy được gần như tất cả những gì ta muốn.

Nhầm lẫn thường gặp

Ba hiểu nhầm hay gặp về BFS. Thứ nhất, tưởng BFS luôn cho đường rẻ nhất: nó chỉ cho đường ít bước nhất, và điều đó chỉ trùng với rẻ nhất khi mọi cạnh cùng chi phí; đồ thị có cạnh trọng số khác nhau thì phải dùng thuật toán khác. Thứ hai, bỏ tập đã thăm cho gọn: trên đồ thị có chu trình, thiếu tập đã thăm sẽ khiến cùng một nút bị thêm lại nhiều lần, gây lặp vô hạn hoặc ngốn bộ nhớ khủng khiếp. Thứ ba, coi nhẹ bộ nhớ vì thấy thời gian mới đáng lo: thực tế BFS thường chết vì hết bộ nhớ trước khi kịp hết thời gian, do phải giữ toàn bộ biên O(b^d) cùng lúc.

Ghi nhớ

BFS duyệt đồ thị theo tầng bằng hàng đợi FIFO, kiểm tra đích ngay khi sinh nút, và cho đường đi ít bước nhất khi mọi bước cùng chi phí. Đổi lại, nó tốn bộ nhớ O(b^d) vì phải giữ toàn bộ biên.