algorithm - 迭代加深深度优先搜索和广度优先搜索生成的节点总数是多少

Question

根据分支因子“b”和最浅目标深度“d”，迭代深化深度优先搜索和广度优先搜索生成的节点总数是多少

score 1 · Accepted Answer

在这里我在这个网站上找到了这个，它可能对你正在寻找的东西有帮助，这个数字真的取决于 d 和 b 的值：

迭代深化 DFS 最坏情况节点数：

N(IDS) = (b)d + (d – 1)b2 + (d – 2)b3 + ...。+ (2)bd-1 + (1)bd = O(bd)

BFS 最坏情况生成的节点数：

N(BFS) = b + b2 + b3 + b4 + ...。bd + (bd + 1 – b) = O(bd + 1)

使用实数的示例：

分支因子 = 10，最浅目标深度 = 5

N(IDS) = 50 + 400 + 3000 + 20000 + 100000 = 123450

N(BFS) = 10 + 100 + 1000 + 10000 + 100000 + 999990 = 1111100

score 0 · Accepted Answer

正如在维基百科上看到的：

“在迭代深化搜索中，深度为d的节点被扩展一次，深度为d-1的节点被扩展两次，依此类推，直到搜索树的根节点被扩展d+1次。[5] 所以迭代深化搜索中的扩展总数是 IDS 扩展数

示例：对于b=10和d=5 示例 “

2 回答 2