几种常见的搜索算法简介

广度优先搜索（BFS）

类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

对于状态数很多时，广度优先搜索可以采用循环队列或动态链表来处理，对于这两种搜索算法，其主要区别如下表：

双向广度优先搜索

在广度优先搜索的基础上进行优化，采用双向搜索的方式，即从起始节点向目标节点方向搜索，同时从目标节点向起始节点方向搜索。 

特点

1. 双向搜索只能用于广度优先搜索中。

2. 双向搜索扩展的节点数量要比单向少的多。

算法

A*算法是利用问题的规则和特点来制定一些启发规则，由此来改变节点的扩展顺序，将最有希望扩展出最优解的节点优先扩展，使得尽快找到最优解。

• 对每一个节点，有一个估价函数F来估算起始节点经过该节点到达目标节点的最佳路径的代价。

• 每个节点扩展的时候，总是选择具有最小的F的节点。

• F=G+B×H：G为从起始节点到当前节点的实际代价，已经算出，H为从该节点到目标节点的最优路径的估计代价。F要单调递增。

• B最好随着搜索深度成反比变化，在搜索深度浅的地方，主要让搜索依靠启发信息，尽快的逼近目标，而当搜索深的时候，逐渐变成广度优先搜索。

散列函数

散列函数（或散列算法，又称哈希函数，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

Rabin-Karp字符串搜索算法是一个相对快速的字符串搜索算法，它所需要的平均搜索时间是O(n).这个算法是创建在使用散列来比较字符串的基础上的。

深度优先搜索（DFS）

如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。

基本思想是

为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。

1. 减少节点数，思想：尽可能减少生成的节点数

2. 定制回溯边界，思想：定制回溯边界条件，剪掉不可能得到最优解的子树

在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵活地去定制回溯搜索的边界。

在深度优先搜索的过程当中，往往有很多走不通的“死路”。假如我们把这些“死路”排除在外，不是可以节省很多的时间吗？打一个比方，前面有一个路径，别人已经提示：“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。这样，浪费了很多的时间。针对这种情况，我们可以把“死路”给标记一下不走，就可以得到更高的搜索效率。

爬山法（Hill Climbing）

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

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

步骤：

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

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

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

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

回溯法 （Backtracking）

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

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

步骤：

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

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

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

算法改进：搜索剪枝

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

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

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

回溯法框架：

递归法

Backtrack(k,X[1...K-1])
    if(k>n) output(X[1...N])
    else
        for each element x in S(k):
               if(constraint(x,X[1...k-1]))
                    X[k]=x
                    backtrack(k+1,X[1...k])

迭代法

IterativeBacktrack()
    k=1
    while k>0
        while set S(k) is not empty
            get a new element x from set S(k)
            if(constraint(x,X[1,k-1]))
                X[k]=x
                if(solution(X)) output(X)
                else k++
        k--

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

分支限界法与回溯法的区别

求解目标不同 

1. 回溯法的求解目标是找出解空间树中满足约束条件的所有解

2. 分支限界法的求解目标则是尽快找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解

3. 分支限界法通常用于解决离散值的最优化问题

搜索方式不同 

1. 回溯法以深度优先的方式（遍历结点）搜索解空间树

2. 分支限界法以广度优先或最小耗费优先的方式搜索解空间树

对扩展结点的扩展方式不同 

1. 分支限界法中，每一个活结点只有一次机会成为扩展结点

2. 活结点一旦成为扩展结点，就一次性产生其所有儿子结点

存储空间的要求不同 

1. 分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大 

转载本站文章《几种常见的搜索算法简介》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SearchingAlgorithms/8274.html