大话搜索 之 最难的搜索问题

不论是只进不退的搜索还是启发式搜索，如果我们拥有足够长的时间，并且将自己的选择付诸行动，理论上，除了“你爸是李刚”之外，其他目标最终你都可以达成。当然，就像电脑中的搜索一样，时间和空间总是有限的，所以现实情况下，我们一般只能得到一个不算太好但也不算太坏的结果。

好了，上面胡扯了这么多，其实就是想引出一个话题，即：到底什么是搜索？

 “什么是搜索”这个问题好像没什么意义，因为搜索就是“找”啊！其实，我们真正想弄明白的是：搜索的目的是什么，即“找什么”。

找什么呢？再回到“人生就是一次搜索”这个话题上，我们之所以要在每一个重要抉择节点上，费尽心思，慎重选择（比如你报高考志愿、比如你选择对象、甚至买卖股票等等），那是因为我们每个人都希望得到一个最优组合， 一个所有选择步骤的最优组合。

如果你的人生，迄今为止每一个选择步骤都是最优的，那你一定是人中龙凤；如果你的大部分选择虽然不是最优，但是由于某些因素，组合的总体却是比较优先的，比如“你爸是李刚”，那么你的人生也会不错。具体到我们每一个人，就像前面说的，虽然都有一个选择步骤组合，但是不是最优却不一定了。

说到这，我们能不能得出这样一个结论：即搜索就是寻找一个排列组合，一个由许多步骤组成的排列组合。

比如有一个迷宫或者地图，我们想在其中的两点间找一条通路。 我们知道，从一点到另一点，中间一定要经过许多步骤。

其中任何一步，我们可能都面临好几种选择。其中的任何一次选择，都会影响到这次选择之后所经历的步骤和我们最终能不能到达目的地。

我们想找一条通路，其实就是在找这么一个步骤的组合，如果这个组合存在，那么这两点间的通路就存在，否则通路就不存在。

有些情况下，两点间的通路可能有很多条，即有很多种组合， 你可能想找最短的一条路，其实就是找步骤最少的那个组合。

还有些情况下，从一点到达另一点是需要付出代价的，每一步都要付出代价，如果你在意这种代价，那你寻找的可能就是总代价最小的那个组合。

另外还有一些问题，比如邮递员问题，组合已经给定，就是 N 个城市，每个城市都要去一次， 但是他却有 N! 种排列顺序，我们需要寻找其中的一个最优排列顺序，所谓搜索仍然是个排列组合问题。

前面说过，很多搜索在每一次面临方向选择的时候，总能找到一些东西来作为启发，但是还有相当一部分搜索问题无法找到有效的启发思路。

找不到启发的原因并不是说当面临选择时没有什么因素需要考虑，而是说需要考虑的因素太多太多，他们之间的关系又非常复杂。

怎么个复杂法呢？比如说，某个因素从一个角度来说越多越好，从另外一个角度来说，它又是越少越好，而两个角度又必须都得考虑，如果不考虑，只能得出错误的结论。这种情况下你怎么选择呢？

你可能会说，对问题的全局做详尽的分析，只要我们信息足够多，那个角度更重要一点，甚至更重要百分之几，总能找到一个定性、定量的分析。这样做能成功吗？

暂且不论我们我们是否能得到足够的信息，首先，这个假设中只考虑了两个角度，如果需要考虑的是20个、200个、甚至2000个角度，还能分析的清楚吗？另外，一旦你引入新的参考信息，会不会对原有参考信息之间的关系产生影响呢？你原有的评判标准是否又要修改呢？

这就是我们常说的复杂性或者非线性，对于这种问题，大自然给了我们很多解决方法，比如说蚂蚁找食、比如说金属退火、比如说生物进化等等。 他们利用巨大的数量，随机的尝试各种排列组合，然后再利用统计学规律从总体上寻找一个方向，最终发现最优排列组合。

当然，这种方法也需要有一个评估函数，但是这个评估函数相对来说更简单一些，更直接一些，可能就是一些自然规律或者客观法则，避免了考虑那些相互影响又乱成一团麻的复杂关系。

上面扯了那么多，搜索到底是什么，可能你仍然很迷惑，这也很正常。毕竟通篇都没讲到数据结构、没有讲队列、栈、排序等等。其实，有些问题的考虑， 避开细节反而能看清楚问题的本质，纠缠细节有可能让你陷入泥潭，这也是大话搜索的目的。

如果有时间可能还会有下一篇：简单与暴力：盲目式搜索 。敬请关注～～～～

//==========================================

本文转自左洸博客园博客，原文链接：http://www.cnblogs.com/myqiao/archive/2010/12/07/1898769.html，如需转载请自行联系原作者