Chiều rộng tìm kiếm đầu tiên phân nhánh yếu tố

Question

Thời gian chạy của BFS là O (b^d)

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!

Answer 1

Thời gian chạy thường được trích dẫn là BFS là O (m + n) trong đó m là số cạnh và số nút. Điều này là do mỗi đỉnh được xử lý một lần và mỗi cạnh tối đa hai lần.

Tôi nghĩ O (b^d) được sử dụng khi sử dụng BFS, giả sử một trò chơi cờ vua, nơi mỗi vị trí có một hệ số phân nhánh tương đối ổn định và động cơ của bạn cần tìm kiếm một số vị trí nhất định . Ví dụ, b là khoảng 35 cho cờ vua và Deep Blue có độ sâu tìm kiếm là 6-8 (lên đến 20).

Trong trường hợp này, vì biểu đồ tương đối tuần hoàn, b^d xấp xỉ bằng m + n (chúng bằng nhau cho cây). O (b^d) hữu ích hơn khi b được cố định và d là điều bạn kiểm soát.

Answer 2

trong đồ thị O (b^d), các b = MAX. Vì nó là trường hợp xấu nhất. kiểm tra liên kết này từ princeton http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Breadth-first_search.html - đi đến phần phức tạp thời gian

Answer 3

Để trích dẫn từ Trí tuệ nhân tạo - Một cách tiếp cận hiện đại bởi Stuart Russel và Peter Norvig:

Thời gian và sự phức tạp không gian luôn coi đối với một số biện pháp khó khăn của vấn đề. Trong khoa học máy tính lý thuyết, thước đo điển hình là kích thước của biểu đồ không gian trạng thái, | V | + | E |, trong đó V là tập các đỉnh (các nút) của đồ thị và E là tập các cạnh (liên kết). Điều này là thích hợp khi biểu đồ là cấu trúc dữ liệu rõ ràng được nhập vào chương trình tìm kiếm. (Bản đồ của Romania là một ví dụ về điều này.) Trong AI, biểu đồ thường được biểu diễn ngầm bởi trạng thái ban đầu, các hành động và mô hình chuyển tiếp và thường xuyên vô cùng. Vì những lý do này, độ phức tạp được biểu thị dưới dạng ba đại lượng: b, hệ số phân nhánh hoặc số lượng người kế thừa tối đa của bất kỳ nút nào; d, độ sâu của nút mục tiêu nông nhất (nghĩa là số bước dọc theo đường dẫn từ gốc); và m, chiều dài tối đa của bất kỳ đường dẫn nào trong không gian trạng thái.Thời gian thường được đo lường về số lượng các nút được tạo trong quá trình tìm kiếm và không gian về số lượng nút tối đa được lưu trữ trong bộ nhớ. Đối với hầu hết các phần, chúng tôi mô tả sự phức tạp về thời gian và không gian để tìm kiếm trên cây; đối với một đồ thị, câu trả lời phụ thuộc vào cách "thừa" các đường dẫn trong vùng trạng thái là gì.

này sẽ cho bạn một cái nhìn sâu sắc rõ ràng về sự khác biệt giữa O (| V | + | E |) và b^d