约 619 个字 25 行代码 预计阅读时间 3 分钟
评判标准广度优先 (BFS)深度优先 (DFS)有限深度 (DLS)迭代加深 (IDS)简单表述从最浅节点开始扩展，探索所有可能性。序列为先进先出一条路径一直向下扩展，没有节点可以扩展就向前回溯，序列为先进后出在 DFS 基础上限制深度在一个常数 (l)，防止过深。逐步增加深度限制 (l)完备性 ( 是否有解 )YesNoYes, if l ≥ dYes最优性（是否最优解）No/YesNoNoNo/Yes时间O(bd+1)O(bm)O(bl)O(bd)空间O(bd+1)O(bm)O(bl)O(bd)注：DFS 不完备是因为可能陷入无穷循环，不满足最优性是因为默认
BFS¶Breadth-first Search （宽度优先搜索）
可以实现两类问题
从节点 A 出发，有前往节点 B 的路径吗从节点 A 出发，前往节点 B 的哪条路径最短Search Strategy （搜索策略）：扩展最浅的未扩展节点。Implementation（实现方法）：使用FIFO队列，即新的后继节点放在后面。
Breadth-first Search Algoruthm on a Graph （图的宽度优先搜索算法）
性能分析 ¶完备性：时间复杂性
Uniform-cost Search （一致代价搜索）¶是对广度优先搜索算法的引伸，扩展路径消耗 (g(n)) 最低的节点。即 (f(n) = g(n)) 即启发式搜索的效用函数，是当前路径的评价指标。
DFS | 深度优先搜索 ¶类似于“不撞南墙不回头”
BFS 常用于找单一的最短路线，它的特点是 " 搜到就是最优解 "，而 DFS 用于找所有解的问题，它的空间效率高，而且找到的不一定是最优解，必须记录并完成整个搜索，故一般情况下，深搜需要非常高效的剪枝（剪枝的概念请百度）。
剪枝 ¶Depth-limited Search （深度受限搜索）
若状态空间无限，深度优先搜索就会发生失败。这个问题可以用一个预定的深度限制(l)得到解决，即：深度(l)以外的节点被视为没有后继节点。缺点：如果我们选择(ld)，深度受限搜索也将是非最优的。
DLS | Depth-limited Search （深度受限搜索）¶Iterative Deepening Search （迭代加深搜索）¶例题 ¶全排列 ¶#include int number[10]={0,1,2,3,4,5,6,7,8,9};int num[10];bool vis[10]={0};void dfs(*int num,int n){ if (n==10){ for (int i=0;i