人工智能的无信息搜索

在人工智能中，当你面对一些问题不知道怎么解决的时候，有一类常用的解决问题的方法，叫做搜索。就好像你在一片迷雾的森林里，不知道怎么办时，走一步算一步，走起来再说。 搜索的话，分为两种类型，一种是无关问题背景信息的搜索，如广度优先搜索、深度优先搜索，另一种是结合问题的背景信息的搜索，如A*搜索，最小代价优先搜索。 每种搜索实现的形式有两种分类，根据展开节点是否曾经被展开过来区分为按树搜索还是按图搜索。按树搜索时，你展开的节点可以包括你已经搜过的节点。而按图搜索，只展开你还没搜过的节点。 接下来了解两种重要的无背景信息的搜索： 一、广度优先搜索：

优先展开同一层级的节点，实现时用的是一个先进先出的队列来保存节点，每次都取出最早加入的节点展开，保证了同一层级依次展开的顺序。

优点：

只要你的问题的代价随着搜索层级的深度递增的就能保证找到最优解。 缺点：

展开的越深，节点以指数级增长，内存容易爆掉。

所以，问题较小时，用广度优先搜索能比较直观的解决问题。 二、深度优先搜索：

只要下一层的节点还能展开，则优先展开它。实现时用的时一个后进先出的队列来保存节点，最后展开的节点加入了队列，只要它还能展开，就继续取出它展开，保证了不断深入的而顺序。

优点：

展开的节点增长是多项式级的，内存消耗小。 缺点：

难以保证能找到最优解，因为当你不确定问题的情况时，搜索就可能无限深入下去而不回头了。

所以需要改进它的缺点。

改进的方式是迭代逐次加深的深度优先搜索。

每次设定一个深度，搜索完以后如果没找到结果，则加深一个深度，再从头到尾搜一遍，不断递增深度，直到找到最优解为止。

这样的搜索方法，即利用了深度优先的内存优势，也因为类似深度优先搜索的逐层递增方式，保证了找到最优解。