无信息搜索算法

2025年8月20日 | 阅读14分钟

无信息搜索是指搜索系统不使用任何关于合适区域的线索，而是依赖于搜索的随机性。尽管如此，它们会同步开始探索搜索空间（所有可能的解决方案）。搜索操作从初始状态开始，并提供所有可能的下一步排列，直到达到目标。

这些通常是最简单的搜索策略，但它们可能不适用于涉及不相关甚至不重要组件的复杂路径。这些算法对于解决基本任务或在将数据传递给更高级的、包含优先信息（prioritized information）的搜索算法之前提供简单处理是必要的。

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

1. 广度优先搜索

广度优先搜索（Breadth-first Search）是遍历树或图最常用的搜索策略。该算法在树或图中进行广度搜索，因此称为广度优先搜索。
BFS算法从树的根节点开始搜索，在移动到下一级节点之前，会扩展当前级别的所有后继节点。
广度优先搜索算法是通用图搜索算法的一个示例。
广度优先搜索是使用FIFO队列数据结构实现的。

优点

如果存在任何解决方案，BFS将提供一个解决方案。
如果给定问题有多个解决方案，则BFS将提供需要最少步数的最小解决方案。
它还有助于找到目标状态的最短路径，因为它在移动到较低级别节点之前需要所有相同层级的节点。
它也非常容易理解。通过它，我们可以为路径类型分配更高的排名。

缺点

它需要大量内存，因为必须将树的每个级别保存在内存中才能扩展到下一级别。
如果解决方案远离根节点，BFS需要大量时间。
对于搜索深度分层的空间，这可能是一种非常低效的方法，因为它需要在移动到下一层之前彻底探索每个级别的所有节点。

示例

在下面的树结构中，我们展示了使用BFS算法从根节点S到目标节点K遍历树的过程。BFS搜索算法以层级遍历，因此它将遵循虚线箭头所示的路径，并且遍历路径将是

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算法的空间复杂度由前沿（frontier）的内存大小决定，为O(b^d)。

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

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

2. 深度优先搜索

深度优先搜索（Depth-first Search）是一种用于遍历树或图数据结构的递归算法。
它被称为深度优先搜索，因为它从根节点开始，沿着每条路径直到其最深的节点，然后才移动到下一条路径。
DFS在其实现中使用堆栈数据结构。
DFS算法的过程与BFS算法的过程相似。

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

优点

DFS占用的内存很少，因为它只需要存储从根节点到当前节点的路径上的节点堆栈。
（如果它走在正确的路径上）到达目标节点所需的时间比BFS算法少。
通过它，我们可以将正在跟踪的路线保存在内存中以节省时间，因为它一次只需要保留一条。

缺点

存在许多状态反复出现的可能性，并且不能保证找到解决方案。
DFS算法会进行深度搜索，有时可能会陷入无限循环。
深度优先搜索（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. 深度限制搜索算法

深度限制搜索算法（Depth-limited Search algorithm）类似于具有预定限制的深度优先搜索。深度限制搜索可以解决深度优先搜索中的无限路径问题。在此算法中，深度限制处的节点被视为没有进一步的后继节点。

深度限制搜索可以通过两种失败条件终止

标准失败值：表示问题没有任何解决方案。
截止失败值：表示在给定的深度限制内问题没有解决方案。

优点

深度限制搜索将限制树的搜索深度。因此，该算法将需要比直接BFS（广度优先搜索）和IDDFS（迭代加深深度优先搜索）更少的内存资源。毕竟，这意味着自动选择搜索空间的更多片段，并相应地消耗资源。由于深度限制，DLS避免了将整个搜索树保存在内存中的困境，这可以为解决特定类型的问题提供更内存高效的解决方案。

当叶子节点的深度等于允许的最高级别时，不要描述其子节点，然后将其从堆栈中删除。
深度限制搜索并未解决经典算法中当城市图存在环路时可能出现的无限循环问题。

缺点

深度限制搜索也存在不完整的缺点。
如果问题有多个解决方案，它可能不是最优的。
深度限制搜索（DLS）算法的有效性在很大程度上取决于指定的深度限制。如果深度限制设置得太低，算法可能根本找不到解决方案。

示例

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

时间复杂度：DLS算法的时间复杂度为O(b^ℓ)，其中b是搜索树的分支因子，l是深度限制。

空间复杂度：DLS算法的空间复杂度为O(b×ℓ)，其中b是搜索树的分支因子，l是深度限制。

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

4. 单成本搜索算法

单成本搜索（Uniform-cost Search）是一种用于遍历加权树或图的搜索算法。当存在不同的边成本时，使用此算法。单成本搜索的主要目标是找到一条通往目标节点的、累积成本最低的路径。单成本搜索根据节点与根节点的路径成本来扩展节点。

它可用于解决任何需要最优成本的图/树。优先队列实现了单成本搜索算法。它赋予最低累积成本最高优先级。如果所有边的路径成本都相同，则单成本搜索等同于BFS算法。

优点

单成本搜索是最优的，因为它在每个状态下都选择成本最低的路径。
当边权重较小时，它会很有效，因为它以确保尽早找到最短路径的顺序来探索路径。
它是一种基本搜索方法，不是过于复杂，因此许多用户都可以轻松使用。
它是一种全面的算法，如果存在解决方案，它将找到解决方案。这意味着该算法是完整的，并确保在有可用解决方案时能够找到它。该算法涵盖了达到解决方案所需的所有必要步骤。

缺点

它不关心搜索中涉及的步数，只关心路径成本。因此，此算法可能会陷入无限循环。
运行时，UCS需要知道所有的边权重才能开始搜索。
此搜索算法在优先队列中保留已发现节点的列表。如果图很大，这会是一个更重的事情。该算法通过存储优先级路径序列来分配内存，随着图的增大，这可能会占用大量内存。
利用单成本搜索，如果图中存在成本小于最短路径的边环，我们可以解决该问题。
单成本搜索将继续部署优先队列，以便可以存储探索过的路径，因为图的大小可能会更大，这最终可能导致使用过多内存。

示例

完整性

单成本搜索是完整的；如果存在解决方案，UCS将找到它。

时间复杂度

设 C* 为最佳解决方案的成本，ε 为使目标节点更近的每一步。那么步数 = C*/ε+1。这里我们加上+1，因为我们从状态0开始，结束于C*/ε。

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

空间复杂度

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

最优性

单成本搜索始终是最优的，因为它只选择成本最低的路径。

5. 迭代加深深度优先搜索 (IDDFS)

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

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

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

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

迭代加深深度优先搜索算法的步骤

将深度限制设置为0。
执行到深度限制的DFS。
如果找到目标状态，则返回。
如果未找到目标状态且未达到最大深度，则增加深度限制并重复步骤2-4。
如果未找到目标状态且已达到最大深度，则终止搜索并返回失败。

优点

它结合了BFS和DFS搜索算法在快速搜索和内存效率方面的优点。
它是一种易于实现的直接算法，因为它建立在传统的深度优先搜索算法之上。
它是一种搜索算法，只要搜索空间中每条边的成本都相同，它就能保证找到最优解。
它是一种完整的算法，其含义是如果存在解决方案，它将始终找到解决方案。
迭代加深深度优先搜索（IDDFS）算法与广度优先搜索（BFS）相比占用的内存更少，因为它只在内存中存储当前路径，而不是整个搜索树。

缺点

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

示例

下面的树结构显示了迭代加深深度优先搜索。IDDFS算法执行多次迭代，直到找不到目标节点。算法执行的迭代次数如下

第一次迭代-----> A

第二次迭代----> A, B, C

第三次迭代------>A, B, D, E, C, F, G

第四次迭代------>A, B, D, H, I, E, C, F, K, G

在第四次迭代中，算法将找到目标节点。

完整性

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

时间复杂度

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

空间复杂度

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

最优性

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

6. 双向搜索算法

双向搜索算法（Bidirectional search algorithm）同时运行两个搜索，一个从初始状态（称为前向搜索），另一个从目标节点（称为后向搜索），以找到目标节点。双向搜索用两个小的子图替换一个单一的搜索图，其中一个从初始顶点开始搜索，另一个从目标顶点开始搜索。当这两个图相交时，搜索停止。

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

优点

双向搜索速度很快。
双向搜索需要的内存更少。
当图非常大且无法缩小其规模时，它会非常有帮助。在这种情况下，使用此工具尤其有用。
在某些情况下，扩展节点的成本可能很高。在这种情况下，使用此方法可以帮助减少需要扩展的节点数量。

缺点

双向搜索树的实现很难。
在双向搜索中，应该提前知道目标状态。
找到一种有效的方法来检查搜索树之间是否存在匹配可能很棘手，这会增加完成任务所需的时间。

示例

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

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

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

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

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