几种常见的搜索算法

目录

广度优先搜索（BFS）

深度优先搜索（DFS）

爬山法（Hill Climbing）

最佳优先算法（Best-first search strategy） 

回溯法 （Backtracking）

分支限界算法（Branch-and-bound Search Algorithm）

A*算法

这个不用我多说了吧……

同上……

DFS的变形，不同的是每次选择的是最优的一个子结点，即局部最优解

例如，对于8数码问题，设置一个函数表示放错位置的数目，每次选择子结点中放错最少的结点

步骤：

1.建立一个栈，将根结点放入栈

2.判断栈顶元素是否是目标结点，如果是，算法结束，如果不是，进入第三步

3.栈顶元素出栈，根据评估函数计算的顺序将此结点的子结点入栈

4.如果栈空，则输出失败，否则，进入第二步

是DFS和BFS的结合

每次找到的是所有结点中最好估计值的那个结点

找到的是全局最优解

步骤：

1.根据评估函数建立一个堆（或用优先队列），将根结点放入堆中

2.判断栈顶元素是否是目标结点，如果是，算法结束，如果不是，进入第三步

3.移出堆顶元素结点，将此结点的所有子结点加入堆

4.如果堆空，输出失败，否则，进入第二步

找到所有选择，走不通则回溯

假定问题的解是一个向量(a1,a2,a3,...,an)，其中的每个元素ai都是问题的一个元素

步骤：

建立一个问题的部分解v=(a1,a2,...,ak)

若这个部分解是可行解，则继续，若不是可行解，删除ak，加入ak情况的另一种可能

若ak的可能已经遍历完，回溯并寻找ak-1的下一个可能

算法改进：搜索剪枝

 剪枝（pruning）可以帮助我们减少搜索空间，更快的找到解

剪枝的思想就是就是通过某种判断，避免一些不必要的遍历过程，就是如果发现此分支不可能找到最优解，就立刻回溯

剪枝的策略需要具体问题具体分析，这里不细讲

回溯法框架：

递归法

迭代法

分支限界法与回溯法的区别 1.求解目标不同       1.回溯法的求解目标是找出解空间树中满足约束条件的所有解      2.分支限界法的求解目标则是尽快找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解      3.分支限界法通常用于解决离散值的最优化问题 2.搜索方式不同       1.回溯法以深度优先的方式（遍历结点）搜索解空间树      2.分支限界法以广度优先或最小耗费优先的方式搜索解空间树 3.对扩展结点的扩展方式不同       1.分支限界法中，每一个活结点只有一次机会成为扩展结点       2.活结点一旦成为扩展结点，就一次性产生其所有儿子结点 4.存储空间的要求不同       1.分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大 

转载自最佳优先搜索（Best-First Search） 

分支限界算法可以用来寻找最优解，在平均情况下不必穷尽搜索

分支限界算法的搜索类似于最佳优先算法并做了一些改进（比如剪枝）

两个要点：

如何产生分支

如何产生界限

基本思想：

用一种方法分开解空间

用一种方法预测一系列解的最小界（lower bound），用一种方法预测最优解的最大界（upper bound）

如果一个解的最小界超出了整个解空间的最大界，那么这个解不可能是最优的，我们就可以提前终止此分支

分支界限适合最小化问题

平均情况下，许多分支能较早被终止，但许多NP难问题在最坏情况下仍是指数级的

个人感觉类似最佳优先算法，都是维护一个优先队列或堆，将结点按照某个值优先的情况放进去，不同的是这次需要一个估计函数h(n)

算法思想：对于优先队列，每取出一个结点n，将他的所有儿子结点n'放入优先队列，优先级由函数f(n)计算出

g(n)：起点到结点n的代价

h(n)：结点n到终点的估计代价

f(n)=g(n)+h(n)

A*算法是一种启发式算法

设h*(n)为结点n到目标结点的实际最小代价

只要h(n)