深度优先搜索生成的节点总数是多少

假设:’d’ 是树的有限深度;’b’ 是分支因子;’g’ 是最浅的目标节点。

据我所知,最坏情况是目标节点位于树的最右下角节点。因此,总生成的节点数应该是 O(bg),对吗?然而,我的老师告诉我这是错误的,因为最坏情况是除了以目标节点为根的子树外,所有的树都被探索了。他提到了一些关于 O(bd) – O(b(g-d)) 的事情…. 我不完全确定

我不太明白他的意思,所以有人能告诉我哪个答案是正确的吗?


回答:

我建议你画一棵树,标记被探索的节点,并计算它们的数量。

如果你使用广度优先搜索,你的推理是正确的,因为你只会到达每个分支的深度 g(总共探索了 O(b**g) 个节点)。

如果你使用深度优先搜索,你老师的推理是正确的,因为除了包含目标的部分外,你会到达树的所有部分的深度 d(总共探索了 O(b**d - b**(d-g)) 个节点)。

enter image description here

目标是绿色圆圈。

蓝色节点是被探索的。

红色节点是未被探索的。

为了计算被探索的节点数量,我们计算树中的总数,然后减去红色节点的数量。

深度 = 2 = d

目标深度 = 1 = g

分支因子 = b = 3

请注意,我将树中节点的总数称为 O(b**d)。严格来说,总数是 b**d + b**(d-1) + b**(d-2) + ... + 1,但这是 O(b**d)

Related Posts

Keras Dense层输入未被展平

这是我的测试代码: from keras import…

无法将分类变量输入随机森林

我有10个分类变量和3个数值变量。我在分割后直接将它们…

如何在Keras中对每个输出应用Sigmoid函数?

这是我代码的一部分。 model = Sequenti…

如何选择类概率的最佳阈值?

我的神经网络输出是一个用于多标签分类的预测类概率表: …

在Keras中使用深度学习得到不同的结果

我按照一个教程使用Keras中的深度神经网络进行文本分…

‘MatMul’操作的输入’b’类型为float32,与参数’a’的类型float64不匹配

我写了一个简单的TensorFlow代码,但不断遇到T…

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注