[科普中国]-无信息搜索

无信息搜索也被称为盲目搜索，该术语（无信息、盲目的）意味着该搜索策略没有超出问题定义提供的状态之外的附加信息。所有能做的就是生成后继节点，并且区分一个目标状态或一个非目标状态。所有的搜索策略是由节点扩展的顺序加以区分。

策略搜索策略是：宽度优先、深度优先、以及一致代价搜索。

无信息搜索策略可按照如下特性来评价：
1、 Completeness（完备性）：是否总能找到一个存在的解。
2、 Time complexity（时间复杂性）：花费多长时间找到这个解。
3、 Space complexity（空间复杂性）：需要多少内存。
4、 Optimality（最优性）：是否总能找到最优的解。1

宽度优先搜索Search Strategy （搜索策略）：扩展最浅的未扩展节点。
Implementation（实现方法）：使用FIFO队列，即新的后继节点放在后面。

Breadth-first Search Algoruthm on a Graph （图的宽度优先搜索算法）。

深度受限搜索若状态空间无限，深度优先搜索就会发生失败。这个问题可以用一个预定的深度限制l得到解决，即：深度l以外的节点被视为没有后继节点。

缺点：

如果我们选择ld，深度受限搜索也将是非最优的。

它将深度优先和宽度优先的优势相结合，逐步增加深度限制反复运行直到找到目标。它以深度优先搜索相同的顺序访问搜索树的节点，但先访问节点的累积顺序实际是宽度优先。2

本词条内容贡献者为:

李斌 - 副教授 - 西南大学