Search一类的问题通常是人工智能方面最先接触到的话题，在小的时候大家想必都遇到过这样的一类益智题目：

一个农夫，一只羊，一头狼，和一棵白菜。现在有一条船，这条船每次只能盛这四个中的两个，当然只有农夫会开船。问：

农夫怎样才能把狼，样，和白菜运到河对岸，有两个限制条件：

狼和羊不能单独在一起，羊和白菜这两样也不能落单。

遇到这样的问题，相信大家一定在脑补：农夫先带过去一只，看看后面那两个有没有后果发生，没的话继续，有的话退回一步重新考虑。嗯，羊不能与狼和白菜共存，所以先带过去，然后第二次随便带狼或者白菜，带过去，然后把羊带回来，然后把第二次剩下的带过去，把羊留下，这样狼和白菜到了对岸，最后把羊带过去。当然这样的问题很简单，想一下就能找到方案。当遇到比较复杂的问题，比如：

路径规划问题，从一个城市到另一座城市，根据你的目标不同，可以搜寻最短的，最快的或者风景最好的，这是一个问题的目标（objective），然后根据设计选择不同的方向，这是行动（action），又或者：机器人机械臂的运动，速度快慢，旋转和移动，字谜游戏，机器翻译等等。

对于一个classifier（分类器），如果给定一个输入，经过一个转换之后得出的是一个单一的操作，而对于search（搜索）问题，输出是一系列的操作，重点是要根据现状考虑未来的动作，并且是基于状态的一种操作。

再回到刚刚提到的那个过河的问题，其实从初始状态可以画一棵树，初始状态分别有三种选择，这样每做出一个选择可以画出子分支，最后会发现能到达最终结果的就是刚刚跟大家分享的那两种方案。归结起来，对于一个搜索问题，包含：

初始状态，动作，对应的动作的代价，下一个状态，和最终的状态。

通常我们会用到数据结构中常用的tree的概念，构建一个search tree：

根节点是初始状态，叶节点是最终的状态，连接节点之间的边就是一个action，并伴随着一定的代价。从根节点到叶节点的所有路径的和就是这个方案的代价，通常会找出一条代价最小的方案。但是注意的是：

在编程中，我们通常不会用到树这样的数据结构，树在这里只是一种形象的表达，后面示例代码中可以看到更多解释。

在分析一棵树的过程中，通常会有这样几个参数：最大的深度D,也即每一条路径包含D条边，然后每个状态可以有b 种动作，经常把这个叫做branching factor。想找到一个最少代价的路径，存储的成本是O(D)，每次从叶节点回溯即可，时间成本就比较大，O（b的D次方），（1 + b + b*b ,,,, + b的D次方 ，等比数列求和，最后结果是 O（b的D次方））。面对这样一个指数级别的时间成本，通常会有两种做法，一是限定最大的搜索深度，而是对于之前到达过的状态，不重复访问。

最基本的：

回溯搜索：

先判断是不是最终结束的状态，是的话，更新最小的代价路径

对于当前状态的每一个action：

       寻找这个状态所有的子节点和到达子节点对应的代价。

       对于当前的状态重新调用回溯搜索。

返回最小代价的路径

深度优先搜索（depth-first search, DFS）：

基于回溯搜索，当遇到终止状态的时候即停止。

存储的成本是O(D)， 每次从叶节点回溯即可，时间成本就比较大，O（b的D次方）。

需要注意的是，这个时候并没有考虑每一个action的代价，比如从初始状态到下一个状态，默认代价是0。这跟之前接触的每一条边都有赋值不同，后面会再提到考虑代价的问题。

深度优先搜索适用于整个搜索树中有很多方案的搜索办法，这样，能比较快的返回搜索结果。不然，如果整棵树都没有方案，需要把整个树搜索一遍。

广度优先搜索(breadth-first search, BFS)：

假设每一个action有固定的一个代价值，c，整个搜索过程是按照由树的每一层进行的。

假设每个状态有b种可能的操作，最后的方案深度是d,树的深度是D, 那么：

存储的成本是O(b的d次方)，时间成本也是O（b的d次方），与D 没有关系。

由于读取搜索的方式的不同，一般，DFS使用堆栈存储节点的信息，这样保证最后入栈的节点得以出栈，然后再入栈该节点的所有子节点。BFS用队列存储，这样第一次存入的所有节点可以依次从头部出队列，然后再把所有的子节点压入队列。并且不难想象的是，这样的存储方式，存储的都是叶节点，中间的节点在产生子节点之前都已经出栈或者队列了。

来看一下一个用python写的简单的例子：

好，搜索是人工智能很基础的一个分支，下次接着来看其他搜索的方式。