搜索策略：深度优先和启发式搜索的优化思考

在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先或深度优先。

广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。

深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接地跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法的一个优点是，网络蜘蛛在设计的时候比较容易。

这两种策略都是搜索策略。打个比方就是这样：一块地下面某一处藏着一箱金子，不知在地下多少米，也不知所处的方位。现在你很想把它挖出来，应该用什么方法呢？一般有两种方法，一种是在一个地方挖洞，一直挖下去，挖到底，如果没有就换个地方继续挖洞，挖到底，一步一步地往前挖，直到挖到宝藏为止。这就是深度优先策略。另一种方法是一层一层地挖，先把这块地整体铲平一米，看看有没有，没有就继续铲平，再整体向下推一米，直到挖到宝藏为止。

这两种策略各有优劣，策略的好坏是由结果来定的。

如果这宝藏埋得很深，使用广度优先策略，几乎要把所有的土地都挖光才能挖到它，而使用深度优先策略，可能一不小心就碰上了，只挖了几个坑就找到了宝藏。

如果这宝藏埋得很浅，但地点隐秘。使用深度优先策略，是难以发现它的，盲目性太大。而如果用了广度优先策略，把地皮向下铲一米，就找到了宝藏。(www.xing528.com)

由于我们事先并不知道宝藏在什么地方，所以不能说采用哪个策略更好。

综合两个策略，有这样一个概念被称为“启发式搜索”。这是什么意思呢？同样打个比方，现在你使用“挖洞”策略，已经挖了三个洞，忽然，从洞里跳出了土地佬，他告诉你“宝藏在东北方向的槐树下”，于是你得到了这个信息，立即赶到东北方的槐树下，挖了一个洞，把宝藏找出来了。或者，你现在使用“铲平”策略，把地皮铲去了一米，忽然发现了某处有一本藏宝图，恰恰写着宝藏的埋藏地点，于是你按照图找到了宝藏。

在启发式搜索中，强调了“启发”。这就是说，在搜索的过程中，要根据每个阶段搜索到的结果去做进一步的思考，从而使搜索的策略得到优化，以尽快得到搜索结果。

启发式搜索就是完美的吗？很遗憾，这只是概念，概念无所谓完美与不完美。启发式搜索能否加快搜索进程，关键在于是如何受到启发及受到启发之后是如何决定的。再举一例，一个盲人拄着拐棍下山，每走一步之前，都要用拐棍探测周围，寻找到最低点作为下一步的目的地。这样，他认为自己每一步都在向下走，自然可以走到山下。但是，如果他走进了山谷怎么办呢？在走进山谷之前，每一步都是向下走，但走进山谷之后，周围的地势都是高的，他就没有办法再走了。站在盲人的角度来看，事实就是这样。

世上没有必然的制胜之路，也没有绝对的失败。在通往成功的路上，人们不断地优化着算法，以为离成功越来越近了，也许真的是这样，也许正在远离成功的路上飞驰。

用“数学家”的语言来描述搜索，就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。至于如何从根节点找到目标叶节点，则有许多数学算法。