搜索算法简介

说到搜索算法，它是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。搜索算法在路径规划、行为决策、语句识别、语义分析等多个领域都发挥着非常重要的作用，下面会给大家做一些介绍，便于大家学习和理解。

一、搜索算法介绍

搜索算法就是穷举出一个问题的部分或所有可能情况，从中找出求解方法。但是搜索相比于单纯的枚举算法有了一定的方向性和目标性。搜索从解的所有可能中从一个状态转移到其他状态（按照要求向解的方向拓展），这样一直进行下去，直到找到答案（目标状态）为止。

二、搜索分类

搜索分为广度优先搜索（BFS）与深度优先搜索（DFS）

（1）广度优先搜索：

基本思想：从初始状态S开始，利用规则，生成所有可能的状态。构成的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。

生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。——在路径的寻找问题上用得比较多

这种思路可以用队列来模拟该过程：

具体实现过程：

1. 每次取出队列首元素（初始状态），进行拓展；

2. 然后把拓展所得到的可行状态都放到队列里面；

3. 将初始状态删除；

4. 一直进行以上三步直到求出可行解或队列为空。

（2）深度优先搜索:（回溯法）

基本思想：从初始状态，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态，若未出现，以此状态利用规则生成再下一层任一个结点，再检查，重复过程一直到叶节点（即不能再生成新状态节点），当它仍不是目标状态时，回溯到上一层结果，取另一可能扩展搜索的分支。采用相同办法一直进行下去，直到找到目标状态为止。

这种思路可以用栈来模拟该过程：

具体实现过程：

1. 次取出栈顶元素，对其进行拓展。

2. 若栈顶元素无法继续拓展，则将其从栈中弹出。继续1过程。

3. 不断重复直到获得目标状态（取得可行解）或栈为空（无解）。