我正在读这本书 - 人工智能是一种现代方法 . 我看到这句话描述了统一成本搜索的时间复杂性
统一成本搜索以路径成本而非深度为指导，因此其复杂性不易用b和d表征 . 相反，让C成为最优解的成本，7并假设每个动作至少花费ε . 然后算法的最坏情况时间和空间复杂度为O（b ^（1 C /ε）），这可能远大于bd .
至于我的理解，C是最优解的成本，每个动作至少花费ε，因此C /ε将是到达目的地的步数 . 但我不知道这种复杂性是如何产生的，谢谢 .
如果分支因子为b，则每次展开节点时，都会遇到更多节点 . 因此，有
0级节点，
b级别为1的节点，在级别2的
b2个节点，在级别3的
b3个节点，
......
bk级别的节点 .
因此，假设在达到k级后搜索停止 . 发生这种情况时，您将访问的节点总数将是
1 b b2 ... bk =（bk 1 - 1）/（b - 1）
这种平等来自几何系列的总和 . 恰好是bk 1 /（b - 1）= O（bk）的情况，所以如果您的目标节点在层k中，那么您必须扩展O（bk）个总节点以找到您想要的节点 .
如果C是您的目的地成本，并且每一步都让您更接近目标，则您需要采取的步数由C /ε1给出.1的原因是您从距离0开始并以C /结束ε，所以你在距离上采取步骤
0，ε，2ε，3ε，......，（C /ε）ε
这里有1个C /ε总步骤 . 因此，有1个C /ε层，因此需要扩展的状态总数为O（b（1 C /ε）） .
希望这可以帮助！
templatetypedef的答案有点不正确 . 1与起始深度为0的事实无关 . 如果每个步长成本至少ε> 0，并且最优解的成本为C，那么最优解的最大深度发生在楼层（C / ε） . 但最坏的情况是时间/空间复杂度实际上是O（b（1层（C /ε）） . 1出现是因为在UCS中，我们只检查节点是否是目标，当我们选择它进行扩展时，而不是我们生成它（这是为了确保最优性） . 所以在最坏的情况下，我们可能会生成在目标节点的驻留级别之后的整个节点级别（这解释了1） . 相比之下，BFS应用目标测试时生成节点，因此没有相应的1因素 . 这是他错过的一个非常重要的点 .
很抱歉碰到一个看似不活跃的问题 .
2 回答
如果分支因子为b，则每次展开节点时，都会遇到更多节点 . 因此，有
0级节点，
b级别为1的节点，
在级别2的
b2个节点，
在级别3的
b3个节点，
......
bk级别的节点 .
因此，假设在达到k级后搜索停止 . 发生这种情况时，您将访问的节点总数将是
这种平等来自几何系列的总和 . 恰好是bk 1 /（b - 1）= O（bk）的情况，所以如果您的目标节点在层k中，那么您必须扩展O（bk）个总节点以找到您想要的节点 .
如果C是您的目的地成本，并且每一步都让您更接近目标，则您需要采取的步数由C /ε1给出.1的原因是您从距离0开始并以C /结束ε，所以你在距离上采取步骤
这里有1个C /ε总步骤 . 因此，有1个C /ε层，因此需要扩展的状态总数为O（b（1 C /ε）） .
希望这可以帮助！
templatetypedef的答案有点不正确 . 1与起始深度为0的事实无关 . 如果每个步长成本至少ε> 0，并且最优解的成本为C，那么最优解的最大深度发生在楼层（C / ε） . 但最坏的情况是时间/空间复杂度实际上是O（b（1层（C /ε）） . 1出现是因为在UCS中，我们只检查节点是否是目标，当我们选择它进行扩展时，而不是我们生成它（这是为了确保最优性） . 所以在最坏的情况下，我们可能会生成在目标节点的驻留级别之后的整个节点级别（这解释了1） . 相比之下，BFS应用目标测试时生成节点，因此没有相应的1因素 . 这是他错过的一个非常重要的点 .
很抱歉碰到一个看似不活跃的问题 .