无信息搜索算法

无信息搜索是一类以蛮力方式运行的通用搜索算法。无信息搜索算法除了如何遍历树之外没有关于状态或搜索空间的额外信息，因此也称为盲搜索。

以下是各种类型的无信息搜索算法：

1. 广度优先搜索

2. 深度优先搜索

3. 深度限制搜索

4. 迭代深化深度优先搜索

5. 统一成本搜索

6. 双向搜索

1. 广度优先搜索：

• 广度优先搜索是遍历树或图最常见的搜索策略。该算法在树或图中进行广度搜索，因此称为广度优先搜索。

• BFS 算法从树的根节点开始搜索，并在移动到下一层节点之前扩展当前级别的所有后继节点。

• 广度优先搜索算法是通用图搜索算法的一个例子。

• 使用 FIFO 队列数据结构实现的广度优先搜索。

好处：

• 如果存在任何解决方案，BFS 将提供解决方案。

• 如果给定问题有多个解决方案，那么 BFS 将提供需要最少步骤的最小解决方案。

缺点：

• 它需要大量内存，因为树的每一层都必须保存到内存中才能扩展下一层。

• 如果解离根节点很远，BFS 需要很多时间。

例子：

在下面的树结构中，我们展示了使用 BFS 算法从根节点 S 到目标节点 K 的树的遍历。遍历的路径将是：

S---> A--->B---->C--->D---->G--->H--->E---->F---->I ---->K

时间复杂度： BFS算法的时间复杂度可以通过在BFS中遍历到最浅节点的节点数来获得。其中 d = 最浅解的深度，b 是每个状态的节点。

T (b) = 1+b ² +b ³ +.......+ b ^d = O (b ^d )

空间复杂度： BFS 算法的空间复杂度由边界的内存大小给出，即 O(b ^d )。

完整性： BFS 是完整的，这意味着如果最浅的目标节点在某个有限深度，那么 BFS 会找到解决方案。

最优性：如果路径成本是节点深度的非递减函数，则 BFS 是最优的。

2. 深度优先搜索

• 深度优先搜索是一种用于遍历树或图数据结构的递归算法。

• 之所以称为深度优先搜索，是因为它从根节点开始，沿着每条路径到达其最大深度节点，然后再移动到下一条路径。

• DFS 使用堆栈数据结构来实现。

• DFS算法的过程类似于BFS算法。

注意：回溯是一种使用递归查找所有可能解决方案的算法技术。

优势：

• DFS 需要非常少的内存，因为它只需要存储从根节点到当前节点的路径上的节点堆栈。

• 到达目标节点的时间比 BFS 算法少（如果它在正确的路径上遍历）。

坏处：

• 许多状态有可能不断重复发生，并且无法保证找到解决方案。

• DFS 算法用于深入搜索，有时可能会进入无限循环。

例子：

在下面的搜索树中，我们展示了深度优先搜索的流程，它将遵循以下顺序：

根节点--->左节点---->右节点。

它将从根节点 S 开始搜索，然后遍历 A，然后是 B，然后是 D 和 E，在遍历 E 之后，它将回溯树，因为 E 没有其他后继节点并且仍然没有找到目标节点。回溯后，它将遍历节点 C，然后是 G，这里它将在找到目标节点时终止。

完整性： DFS 搜索算法在有限状态空间内是完整的，因为它将扩展有限搜索树内的每个节点。

时间复杂度： DFS 的时间复杂度将等价于算法遍历的节点。它由以下给出：

T(n)= 1+ n ² + n ³ +.........+ n ^m =O(n ^m )

其中，m = 任何节点的最大深度，这可以远大于 d（最浅解深度）

空间复杂度： DFS 算法只需要存储从根节点开始的单条路径，因此 DFS 的空间复杂度相当于边缘集的大小，即O(bm)。

最优： DFS 搜索算法是非最优的，因为它可能会产生大量步骤或高成本到达目标节点。

3. 深度有限搜索算法：

深度限制搜索算法类似于具有预定限制的深度优先搜索。深度限制搜索可以解决深度优先搜索中无限路径的弊端。在该算法中，深度限制处的节点将视为没有后续节点。

深度受限搜索可以在两种失败条件下终止：

• 标准故障值：表示问题没有任何解决方案。

• 截止失败值：它定义了给定深度限制内问题的无解。

好处：

深度限制搜索是内存高效的。

缺点：

• 深度受限搜索也有不完备性的缺点。

• 如果问题有多个解决方案，则可能不是最优的。

例子：

完整性：如果解决方案在深度限制之上，则 DLS 搜索算法是完整的。

时间复杂度： DLS 算法的时间复杂度为O(b ^ℓ )。

空间复杂度： DLS 算法的空间复杂度为 O (b×ℓ)。

最优：深度限制搜索可以看作是 DFS 的一个特例，即使 ℓ>d 也不是最优的。

4. 统一成本搜索算法：

均匀成本搜索是一种用于遍历加权树或图的搜索算法。当每个边都有不同的成本时，这个算法就会发挥作用。统一成本搜索的主要目标是找到一条到达目标节点的路径，该路径具有最低的累积成本。统一成本搜索根据节点的路径成本从根节点扩展节点。它可用于解决任何需要最优成本的图/树。优先级队列实现了统一成本搜索算法。它给予最低的累积成本最大的优先权。如果所有边的路径成本相同，则统一成本搜索等效于 BFS 算法。

好处：

• 统一成本搜索是最优的，因为在每个状态下都会选择成本最低的路径。

缺点：

• 它不关心搜索涉及的步骤数，只关心路径成本。因此，该算法可能陷入无限循环。

例子：

完整性：

Uniform-cost 搜索完成，如若有解，UCS 会找到。

时间复杂度：

设 C*为最优解的成本，ε为每一步接近目标节点。那么步数为 = C*/ε+1。这里我们取了 +1，因为我们从状态 0 开始到 C*/ε 结束。

因此，统一成本搜索的最坏情况时间复杂度为O(b ^{1 + [C*/ε]} )/。

空间复杂度：

空间复杂度的逻辑相同，因此，统一成本搜索的最坏情况空间复杂度为O(b ^{1 + [C*/ε]} )。

最佳：

统一成本搜索总是最优的，因为它只选择路径成本最低的路径。

5.迭代深化depth-first Search：

迭代深化算法是DFS和BFS算法的结合。该搜索算法找出最佳深度限制，并通过逐渐增加限制直到找到目标来实现。

该算法执行深度优先搜索直到某个“深度限制”，并在每次迭代后不断增加深度限制，直到找到目标节点。

这种搜索算法结合了广度优先搜索的快速搜索和深度优先搜索的内存效率的优点。

当搜索空间很大，目标节点的深度未知时，迭代搜索算法是有用的无信息搜索。

好处：

• 它结合了 BFS 和 DFS 搜索算法在快速搜索和内存效率方面的优势。

缺点：

• IDDFS 的主要缺点是它重复了前一阶段的所有工作。

例子：

以下树结构显示了迭代深化深度优先搜索。IDDFS 算法执行各种迭代，直到找不到目标节点。算法执行的迭代如下：

第一次迭代-----> A 第二次
迭代----> A、B、C
第三次迭代------> A、B、D、E、C、F、G
4 'th Iteration------>A, B, D, H, I, E, C, F, K, G
在第四次迭代中，算法会找到目标节点。

完整性：

如果分支因子是有限的，则该算法是完整的。

时间复杂度：

让我们假设 b 是分支因子，深度是 d，那么最坏情况的时间复杂度是O(b ^d )。

空间复杂度：

IDDFS 的空间复杂度为O(bd)。

最佳：

如果路径成本是节点深度的非递减函数，则 IDDFS 算法是最优的。

6. 双向搜索算法：

双向搜索算法同时运行两次搜索，一种形成初始状态称为前向搜索，另一种从目标节点开始称为反向搜索，以找到目标节点。双向搜索用两个小的子图代替一个单一的搜索图，其中一个从初始顶点开始搜索，另一个从目标顶点开始。当这两个图形彼此相交时，搜索停止。

双向搜索可以使用 BFS、DFS、DLS 等搜索技术。

好处：

• 双向搜索速度很快。

• 双向搜索需要更少的内存

缺点：

• 双向搜索树的实现是困难的。

• 在双向搜索中，应该提前知道目标状态。

例子：

在下面的搜索树中，应用了双向搜索算法。该算法将一个图/树分成两个子图。它从节点 1 开始向前遍历，从目标节点 16 开始向后遍历。

该算法在两个搜索相遇的节点 9 处终止。

完整性：如果我们在两个搜索中都使用 BFS，则双向搜索是完整的。

时间复杂度：使用 BFS 进行双向搜索的时间复杂度为O(b ^d )。

空间复杂度：双向搜索的空间复杂度为O(b ^d )。

最优：双向搜索是最优的。