4.17博客（广度优先搜索和深度优先搜素）

这周讲了搜索算法。
相比于单纯的枚举算法有了一定的方向性和目标性。算法是在解的空间里，从一个状态转移（按照要求拓展）到其他状态，这样进行下去，将解的空间中的状态遍历，找到答案（目标的状态）。
搜索算法分为广度优先搜索（BFS）和深度优先搜索（DFS）。

广度优先搜索

基本思想：从初始状态S 开始，利用规则，生成所有可能的状态。一层层的寻找所要的结果，如果没找到所需要的答案，就继续将这层寻找完，然后继续向下一层寻找，直到找到答案。

广度优先即是要按层数一层一层来遍历，先将一层全部扩展，然后再进行下一层。

这样利用队列先进先出（FIFO）的性质恰好可以来完成这个任务。

具体过程：

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

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

3 将初始状态删除

4 一直进行以上三步直到队列为空。

深度优先搜索

通俗的讲就是在寻找的过程中，一条路走到黑。和BFS做对比

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