广度优先算法(Breadth first search)

  1. 图片说明

  2. 图片说明

图片说明

  1. 结点的在扩展的时候不就等于生成吗? 为什么这里还有区别?

  2. 什么是空间复杂度? 为什么说空间复杂度是时间复杂度的b分之一?

  3. 什么是探索集? 什么是边缘节点集?他俩对应的时间复杂度是怎么来的?

  4. 一致代价搜索的复杂度是怎么来的呢?也就是上面的那个指数很抽象,有没有有逻辑一点的推理呢?

探索集说的是已经遍历的节点,边缘集是探索集的下一层,所以是它的b倍。b是节点的个数
空间复杂度就是你程序最多需要的内存,时间复杂度是你程序运行的时间,因为你始终需要存储探索集(然后你才能找到下一层),所以空间复杂度就是探索集大小,而时间复杂度是边缘集(也就是你搜索所有节点的个数)
中间相差指数级的一个底,也就是b倍