无信息搜索_计算机科学领域术语 - 威林百科weilinceramic.com

无信息搜索

计算机科学领域术语

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

策略

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

无信息搜索策略可按照如下特性来评价：

1、 Completeness（完备性）：是否总能找到一个存在的解。

2、 Time complexity（时间复杂性）：花费多长时间找到这个解。

3、 Space complexity（空间复杂性）：需要多少内存。

4、 Optimality（最优性）：是否总能找到最优的解。

宽度优先搜索

Search Strategy （搜索策略）：扩展最浅的未扩展节点。

Implementation（实现方法）：使用FIFO队列，即新的后继节点放在后面。

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

深度受限搜索

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

缺点：

如果我们选择l

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

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

参考资料

最新修订时间：2024-07-05 22:31

条目作者

概述

策略

宽度优先搜索

参考资料