廣度優先搜索生成的節點數量是多少？

Question

該號碼。根據我的書： N(BFS) = b + b^2 + .... + b^d + (b^(d+1) - b)其中b是分支因子，d是深度最淺的節點。但不應該只是b + b^2 + .... + b^d？因爲那個，據我所知不是。的節點直到目標的深度。那麼爲什麼那裏有+ (b^(d+1) - b)？

Answer 1

我認爲你所指的情況是當生成節點時評估測試條件;那麼BFS擴展最小深度處「目標」下的所有節點，除了目標節點本身的子節點。如果目標是在深度d，最壞的情況是最後一片葉子不擴大（因爲它的目標）：

1 + b + b^2 + ... + b*(b^d - 1) = 1 + b + b^2 + ... + b^(d+1) - b = (b^(d+2) - 1)/(b - 1) 

Answer 2

有通過廣度優先搜索取決於在多個生成的節點的差異您使用的算法的變體。

如果應用目標測試到每個節點時，選擇它用於擴展（彈出開放列表/隊列的），那麼生成的節點的數量將是（在最壞的情況下）：

1 + b + b^2 + b^3 + ... + b^d + (b^(d+1) - b)，

其中d是解決方案深度，而b是分支因子（任何節點的後繼最大數目）。

這是因爲在實際選擇目標節點進行擴展之前，您必須生成目標節點的兄弟的子節點。而在最壞的情況下，目標節點將成爲選擇擴展的開放列表中的最後一個。

但是，這種通用的圖形搜索算法有一點小小的調整，就是目標測試在生成時應用於每個節點，而不是在選擇擴展時使用。

因此，假設解決方案再次處於深度d。再次，在最壞的情況下，它是在該級別生成的最後一個節點。然後生成的節點總數爲：

1 + b + b^2 + b^3 + ... + b^d。

所以在第一種情況下的空間複雜度爲： O(b^(d+1))， 而在第二種情況： O(b^d)。