jam*_*mes 3 algorithm artificial-intelligence breadth-first-search time-complexity
在我的algoritham分析课程中,老师告诉我们,Breath First搜索的时间复杂度是O(V + E)但现在在人工智能课程中,老师说BFS的复杂性是O(b d).当我问他问题时,他给了我一个合乎逻辑的理由,即"在理论计算机科学中,O(V + E)是合适的,因为图形是输入到搜索算法的显式数据结构.在AI中,图形通常表示由初始状态,动作和转移模型隐含地且经常是无限的.因此,复杂性以O(b d)"表示.现在我有两个问题
在人工智能中 - 你通常处理巨大/无限的图形,因此对于这些图形而言不具有O(V+E)信息性并且不够好,所以我们试图获得更好的约束.这个界限是O(B^d),B分支因子在哪里,是d解决方案的深度.这背后的理性是,如果你在每个深度"分支"到B方向,你最终会探索O(B^d)节点.
更重要的是 - 请注意,算法课程中的经典BFS是探索算法 - 需要探索整个图形(探索所有顶点),而在AI中我们将它用作寻路 - 您将探索直到我们找到从源到目标的路径.(没有必要,有时候无法探索整个图表)
另请注意,如果您在树上查看(没有节点被发现两次),分支因子B和所有叶子都是深度的d- B + B^2 + B^3 + ... + B^d < B^(d+1)树中确实存在节点,因此如果您确实需要
O(V + E)和O(b ^ d)如何相等,第一个看起来像线性复杂,第二个看起来是指数.
在第一个中,图形是输入,因此它在输入的大小上是线性的 - 图形.
第二个也是图形大小的线性 - 并且在解的深度上呈指数 - 一个不同的因子,仍然 - 不需要遍历一个顶点多一次,所以在图形的大小中仍然是线性的.
所以,在这里-基本上O(B^d)是一个子集的O(V+E),是更多的信息,然后它,如果你可以"苦"的事实,你是复杂的函数d,这是不是输入的一部分.
当我们谈论大O符号时,它意味着输入可能是上限,它应该保持不变,因为它是一个上限.Big O是否只处理一些有限的数据输入？
如果图是无限的,那么对于每个f(n),对于每个常数c,N - ,大O都不是信息性的c*f(n) < infinity,所以在谈论无限图时它是无用的.