AI 盲目搜索算法基础教程文档

收录于 2023-04-20 00:10:05 · بالعربية · English · Español · हिंदीName · 日本語 · Русский язык · 中文繁體

不知情的搜索是一类以暴力方式运行的通用搜索算法。除了如何遍历树外，不知情的搜索算法没有关于状态或搜索空间的其他信息，因此也称为盲搜索。
以下是各种类型的不知情的信息。搜索算法:
宽度优先搜索 深度优先搜索 深度受限搜索 迭代加深深度优先搜索 统一费用搜索 双向搜索

1、广度优先搜索:

宽度优先搜索是遍历树或图形的最常见搜索策略。该算法在树或图中进行宽度搜索，因此称为宽度优先搜索。 BFS算法从树的根节点开始搜索，并在移动到下一级别的节点之前扩展当前级别的所有后继节点。 广度优先搜索算法是通用图搜索算法的示例。 使用FIFO队列数据结构实现宽度优先搜索。
优点:
如果有解决方案，BFS将提供解决方案。 如果对于一个给定的问题有多个解决方案，那么BFS将提供最少的解决方案，所需的步骤最少。
缺点:
这需要大量的内存，因为必须将树的每个级别保存到内存中才能扩展下一个级别。 如果解决方案离根节点很远，BFS需要很多时间。

示例:

在下面的树结构中，我们显示了使用BFS算法从根节点S到目标节点K遍历树的过程。BFS搜索算法会逐层遍历，因此它将遵循虚线箭头所示的路径，遍历的路径为: 
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
未通知的搜索算法
时间复杂度: 可以获得BFS算法的时间复杂度直到最浅的节点为止在BFS中遍历的节点数。
T(b)= 1 + b 2 + b 3 +.......+ b d = O(b d )
空间复杂度: BFS算法的空间复杂度由边界的内存大小O(b d )给出。
完整性: 完成，这意味着如果最浅的目标节点处于某个有限深度，则BFS将找到解决方案。
最优性: 如果路径成本不变，则BFS是最优的

2、深度优先搜索

深度优先搜索是一种遍历树或图数据结构的递归算法。 之所以称为深度优先搜索，是因为它从根节点开始，沿着每个路径到达其最大深度节点，然后再移动到下一个路径。 DFS使用堆栈数据结构来实现。 DFS算法的过程类似于BFS算法。
注意: 回溯是一种使用递归查找所有可能解的算法技术。
优势:
DFS仅需要在从根节点到当前节点的路径上存储一堆节点，因此所需的内存非常少。 到达目标节点所需的时间少于BFS算法(如果在正确的路径中穿过)。
缺点:
许多州可能会不断发生，并且不能保证找到解决方案。 DFS算法用于深入搜索，有时可能会进入无限循环。

示例:

在下面的搜索树中，我们显示了深度优先搜索的流程，其顺序如下:
根节点--->左节点---->右节点。
它将在遍历E之后从根节点S开始搜索，先遍历A，然后遍历B，然后遍历D和E。 ，因为E没有其他后继者，但仍未找到目标节点，它将回溯树。回溯后，它将遍历节点C，然后遍历G，在此处它将终止，直到找到目标节点为止。
未通知搜索算法
完整性: : DFS搜索算法在有限的状态空间内是完整的，因为它将扩展有限搜索树中的每个节点。
时间复杂度: DFS的时间复杂度将等同于算法遍历的节点。给出如下:
T(n)= 1 + n 2 + n 3 + .. 。+ n m = O(n m )
其中，m =任何节点的最大深度，这可以比d(最浅的解决方案深度)大得多
空间复杂度: DFS算法只需要存储从根节点开始的单个路径，因此DFS的空间复杂度为等于边缘集的大小，为 O(bm)。
最佳: DFS搜索算法不是最佳算法，因为它可能生成大量步骤或花费高昂成本才能到达目标节点。

3、深度限制搜索算法:

深度限制搜索算法类似于具有预定限制的深度优先搜索。深度限制搜索可以解决深度优先搜索中无限路径的缺点。在该算法中，深度限制的节点将被视为不再有后续节点。
深度受限的搜索可以通过两个失败条件终止:
标准失败值: 表明问题没有任何解决方法。 切断失败值: 在给定的深度限制内，该问题未定义任何解决方案。
优点:
深度受限搜索可提高内存效率。
缺点:
深度受限搜索还具有不完整的缺点。 如果问题有多个解决方案，那可能不是最佳选择。

示例:

未通知的搜索算法
完整性: 如果解超出了深度限制，则DLS搜索算法完成。
时间复杂度: DLS算法的时间复杂度为 O(b ℓ)。
空间复杂度: DLS算法的空间复杂度为O (b×ℓ)。
最佳: 深度限制搜索可以视为DFS的一种特殊情况，即使ℓ> d，也不是最佳选择。

4、均匀成本搜索算法:

均匀成本搜索是一种用于遍历加权树或图形的搜索算法。当每个边缘的可用成本不同时，该算法就会发挥作用。统一成本搜索的主要目标是找到通往目标节点的路径，该路径具有最低的累积成本。均匀成本搜索根据节点的路径成本从根节点扩展节点。它可以用于求解需要最佳成本的任何图/树。优先级队列实现统一成本搜索算法。它为最低的累计成本提供了最高的优先级。如果所有边的路径成本相同，则均匀成本搜索等效于BFS算法。
优点:
统一成本搜索是最佳选择，因为在每个州都选择了成本最低的路径。
缺点:
它不关心搜索涉及的步骤数，仅关心路径成本。因此，该算法可能陷入无限循环。

示例:

未通知的搜索算法
完整性:
统一成本搜索已完成，例如，如果有解决方案，UCS会找到它。
时间复杂度:
让C * 是最佳解决方案的成本，而 ε是接近目标节点的每一步。那么步数为= C */ε+ 1、在这里，我们从状态0开始到C */ε取+1、
因此，均匀成本搜索的最坏情况时间复杂度是 O(b 1 + [C */ε] )/。
空间复杂度:
相同的逻辑适用于空间因此，均匀成本搜索的最坏情况下的空间复杂度为 O(b 1 + [C */ε] )。
最佳:
统一成本搜索始终是最佳选择，因为它只会选择路径成本最低的路径。

5、迭代加深深度优先搜索:

迭代加深算法是DFS和BFS算法的组合。这种搜索算法找出最佳的深度极限，并通过逐渐增加极限直到找到目标为止。
此算法hm进行深度优先搜索直到某个"深度极限"，并且在每次迭代后一直增加深度极限，直到找到目标节点为止。
此搜索算法结合了"宽度优先"搜索的优势快速搜索和深度优先搜索的存储效率。
当搜索空间较大且目标节点深度未知时，迭代搜索算法可用于无信息搜索。
优点:
它结合了BFS和DFS搜索算法在快速搜索和存储效率方面的优势。
缺点:
IDDFS的主要缺点是，它重复了上一阶段的所有工作。

示例:

以下树形结构显示了迭代加深深度优先搜索。 IDDFS算法执行各种迭代，直到找不到目标节点为止。该算法执行的迭代为:
未通知的搜索算法
st迭代-----> A
第2次迭代----> A，B，C
第3次迭代------> A，B，D，E，C，F ，G
第4次迭代------> 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 )。
最佳: 双向搜索是最佳的。