• home > theory > algorithm > Searching >

    几种常见的搜索算法简介

    Author:zhoulujun Date:

    搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法。有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法


    广度优先搜索(BFS)

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

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

    遍历方式深度优先搜索遍历广度优先搜索遍历
    所用数据结构队列
    一般优化

    最优性剪枝

    可行性剪枝

    Hash判重

    双向搜索

    双向广度优先搜索

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

    特点

    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

    上一篇:First page
    下一篇:Last page