几种图搜索算法的对比

宽度优先搜索

这种搜索方式就是从根部逐层搜索,在下一层的任何节点扩展之前,上一层深度的所有节点都已经展开过。一般到达一层后将本层的所有节点放入一个FIFO队列,进行迭代扩展。

优点: 时间复杂度相对较低,易于实现和理解

缺点: 空间复杂度太高,对于复杂的图进行搜索可能会耗费大量的内存。在扩展倒数第二层的时候需要存储最后一层的所有节点

一致代价搜索

这种搜索方式制定了一个路径消耗函数g(n),该函数描述根节点到n的路径消耗(假设每个边上有相关的消耗值),每次都扩展当前g(n)最小的边缘节点

优点: 肯定能得到最优解

缺点: 时间复杂度和空间复杂度过高

深度优先搜索

受限深度优先搜索

迭代加深深度优先搜索

双向搜索

无信息搜索策略对比

宽度优先 一致代价 深度优先 受限深度优先 迭代加深深度优先 双向搜索
完备性 分支因子有限的情况下完备 单步代价存在下界且分支因子有限的情况下完备 不完备 不完备 分支因子有限的情况下完备 双向都是用宽度优先搜索且分支因子有限的情况下完备
时间复杂度 $ O(b^d) $ $ O(b^{1+\lfloor{C^*/\varepsilon}\rfloor})$ $ O(b^m) $ $ O(b^l) $ $ O(b^d) $ $ O(b^{d/2}) $
空间复杂度 $ O(b^d) $ $ O(b^{1+\lfloor{C^*/\varepsilon}\rfloor})$ $ O(b^m) $ $ O(b^l) $ $ O(b^d) $ $ O(b^{d/2}) $
最短路径最优解 单步代价相同时是最优解 是最优解 不是最优解 不是最优解 单步代价相同时是最优解 单步代价相同且双向都使用宽度优先搜索时是最优解

b: 分值因子
d: 最浅解的深度
l: 深度界限
m: 搜索树最大深度
$ C^* $: 最优解的代价
$ \varepsilon $: 所有路径的最小代价