Thời gian chạy của BFS là O (b^d)Chiều rộng tìm kiếm đầu tiên phân nhánh yếu tố
b là phân nhánh yếu tố d là độ sâu (# cấp) của đồ thị từ bắt đầu nút.
Tôi googled cho một lúc, nhưng tôi vẫn không thấy ai đề cập đến cách họ tìm ra này "b"
yếu tốVì vậy, tôi biết phân nhánh có nghĩa là "# của đứa trẻ đó mỗi nút có"
Ví dụ, hệ số phân nhánh cho cây nhị phân là 2.
vì vậy đối với biểu đồ BFS, là b = trung bình tất cả hệ số phân nhánh của mỗi nút trong biểu đồ của chúng tôi.
hoặc b = MAX (trong tất cả các yếu tố chi nhánh của mỗi nút)?
Ngoài ra, bất kể cách nào chúng tôi chọn b, dường như vẫn còn mơ hồ để tiếp cận thời gian chạy của chúng tôi. Ví dụ: nếu biểu đồ của chúng tôi có 30000 nút, chỉ có 5 nút có 10000 nhánh và tất cả phần còn lại của 29955 nút chỉ có 10 nhánh. và chúng tôi có thiết lập độ sâu là 100.
Có vẻ O (b^d) không có ý nghĩa trong trường hợp này.
Ai đó có thể giải thích một chút. Cảm ơn bạn!
Nói đúng ra 'd' là KHÔNG độ sâu của đồ thị. Đó là độ sâu của giải pháp cạn nhất. – nhahtdh
ý của bạn là gì? – runcode
Nếu có nhiều giải pháp và giải pháp ở độ sâu khác nhau thì BFS sẽ chấm dứt khi tìm thấy một giải pháp, giải pháp này là giải pháp cạn nhất. Trừ khi bạn muốn tìm kiếm toàn bộ cây, sau đó d có thể được xác định khác nhau. – nhahtdh