搜索方法小结 2006/09/11 rickone

不管哪种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解（可行解），搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解，我们用两张表来进行搜索，一个叫OPEN表，表示那些已经展开但还没有访问的结点集，另一个叫CLOSE表，表示那些已经访问的结点集。

一、蛮力搜索（DFS，BFS）
DFS和BFS是最基本的搜索算法，用上面的形式表示它们是非常相似的。

BFS（Breadth-First-Search 宽度优先搜索）
首先将起始结点放入OPEN表，CLOSE表置空，算法开始时：
1、如果OPEN表不为空，从表中开始取一个结点S，如果为空算法失败
2、S是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到3
3、将S的所有后继结点展开，就是从S可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表末尾，并把S放入CLOSE表，重复算法到1

DFS（Depth-First-Search 深度优先搜索）
首先将起始结点放入OPEN表，CLOSE表置空，算法开始时：
1、如果OPEN表不为空，从表中开始取一个结点S，如果为空算法失败
2、S是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到3
3、将S的所有后继结点展开，就是从S可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表开始，并把S放入CLOSE表，重复算法到1

没看出有什么不同？擦干净了眼镜再看一遍吧。

知道BFS和DFS有什么不同吗？B和D嘛。-_-!

仔细观察OPEN表中待访问的结点的组织形式，BFS是从表头取结点，从表尾添加结点，也就是说OPEN表是一个队列，没错，BFS首先就要让你想到‘队列’；而DFS，它是从OPEN表头取结点，也从表头添加结点，也就是说OPEN表是一个栈！

DFS用到了栈，所以有一个很好的实现方法，那就是递归，系统栈是计算机程序中极重要的部分之一，你不想递归？怕它用完了？放那儿也是浪费。而且用递归也有个好处就是，在系统栈中只需要存结点最大深度那么大的空间，也就是在展开一个结点的后续结点时可以不用一次全部展开，用一些环境变量记录当前的状态，在递归调用结束后继续展开。

利用系统栈实现的DFS
函数 dfs(结点 s)
{
      s超过最大深度了吗？是：相应处理，返回；
      s是目标结点吗？是：相应处理；否则：
      {
            s放入CLOSE表；
            for(c=s.第一个子结点 ；c不为空 ；c=c.下一个子结点() )
                  if(c不在CLOSE表中)
                        dfs(c)；递归
      }
}

如果指定最大搜索深度为n，那系统栈最多使用n个单位，它相当于有状态指示的OPEN表，状态就是c，在栈里存了前面搜索时的中间变量c，在后面的递归结束后，c继续后移。在象棋等棋类程序中，就是用这样的DFS的基本模式搜索棋局局面树的，因为如果用OPEN表，有可能还没完成搜索OPEN表就暴满了，这是难于控制的情况。

我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。

二、启发式搜索
为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。打个比方，估值函数就像一台显微镜，一双‘慧眼’，它能分辨出看上去一样的孩子们的手，哪个很脏，有细菌，哪个没有，很干净，然后对那些干净的孩子进行奖励。（我不是老师，不会打比方，呵）对，这里似乎需要‘排序’，排序是要有代价的，而花时间做这样的工作会不会对整体搜索效率有所帮助呢，这完全取决于估值函数。

排序，怎么排？翻翻《数据结构》排序算法一大堆，用哪一个？你会很喜欢高级的排序算法，快排吧，qsort！不一定，要看要排多少结点，如果很少，简单排序法就很OK了。看具体情况了。

排序可能是对OPEN表整体进行排序，也可以是对后续展开的子结点排序，排序的目的就是要使程序有启发性，更快的搜出目标解。

如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*，举个问题例子，八数码问题，如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，具体A*以后再谈。

从A*的角度看前面的搜索方法，如果路径价值为0就是有序搜索，如果路径价值就用所在结点到起始结点的距离（深度）表示，而启发值为0，那就是BFS或者DFS，它们两刚好是个反的，BFS是从OPEN表中选一个深度最小的进行展开，而DFS是从OPEN表中选一个深度最大的进行展开，它们俩还真是亲兄弟啊！当然只有BFS算是特殊的A*，所以BFS可以求要求路径最短的问题，只是没有任何启发性。

评论