知情搜索算法

到目前为止，我们已经讨论了无信息搜索算法，这些算法在没有任何关于搜索空间的额外知识的情况下，通过搜索空间寻找问题的所有可能解决方案。但是知情搜索算法包含一系列知识，例如我们离目标有多远、路径成本、如何到达目标节点等。这些知识有助于代理更少地探索搜索空间并更有效地找到目标节点。

知情搜索算法对于大搜索空间更有用。知情搜索算法使用启发式的思想，所以也称为启发式搜索。

启发式函数：启发式是用于 Informed Search 的函数，它可以找到最有希望的路径。它将代理的当前状态作为其输入，并产生代理与目标的接近程度的估计。然而，启发式方法可能并不总是给出最好的解决方案，但它保证在合理的时间内找到一个好的解决方案。启发式函数估计状态与目标的接近程度。它由 h(n) 表示，它计算这对状态之间的最优路径的成本。启发式函数的值始终为正。

启发式函数的可接受性为：

h(n) <= h*(n)

这里 h(n) 是启发式成本，而 h*(n) 是估计成本。因此启发式成本应该小于或等于估计成本。

纯启发式搜索：

纯启发式搜索是启发式搜索算法的最简单形式。它根据启发式值 h(n) 扩展节点。它维护着两个列表，OPEN 和 CLOSED 列表。在 CLOSED 列表中，它放置那些已经扩展的节点，在 OPEN 列表中，它放置尚未扩展的节点。

在每次迭代中，具有最低启发式值的每个节点 n 被扩展并生成其所有后继节点，并将 n 放置到封闭列表中。该算法继续单元找到目标状态。

在知情搜索中，我们将讨论下面给出的两种主要算法：

• 最佳优先搜索算法（贪心搜索）

• A* 搜索算法

1.) 最佳优先搜索算法（贪婪搜索）：

贪婪的最佳优先搜索算法总是选择在那个时刻出现最好的路径。它是深度优先搜索和广度优先搜索算法的结合。它使用启发式函数和搜索。最佳优先搜索使我们能够利用这两种算法的优势。在最佳优先搜索的帮助下，在每一步，我们都可以选择最有希望的节点。在最佳优先搜索算法中，我们扩展离目标节点最近的节点，并通过启发式函数估计最近的成本，即

f(n)=g(n)。

其中，h(n)= 从节点 n 到目标的估计成本。

贪心最佳优先算法由优先队列实现。

最佳优先搜索算法：

• 步骤 1：将起始节点放入 OPEN 列表。

• 第二步：如果OPEN列表为空，则停止并返回失败。

• 步骤3：从OPEN列表中移除h(n)值最低的节点n，并将其放入CLOSED列表中。

• Step 4：展开节点n，生成节点n的后继节点。

• Step 5：检查节点n的每个后继节点，看是否有一个节点是目标节点。如果任何后继节点是目标节点，则返回成功并终止搜索，否则继续步骤 6。

• 步骤 6：对于每个后继节点，算法检查评估函数 f(n)，然后检查该节点是否已在 OPEN 或 CLOSED 列表中。如果该节点未在两个列表中，则将其添加到 OPEN 列表中。

• 第 7 步：返回第 2 步。

好处：

• 最佳优先搜索可以通过获得两种算法的优点在 BFS 和 DFS 之间切换。

• 该算法比 BFS 和 DFS 算法更有效。

缺点：

• 在最坏的情况下，它可以表现为无引导的深度优先搜索。

• 它可能会像 DFS 一样陷入循环中。

• 这个算法不是最优的。

例子：

考虑下面的搜索问题，我们将使用贪婪的最佳优先搜索来遍历它。在每次迭代中，使用评估函数 f(n)=h(n) 扩展每个节点，如下表所示。

在这个搜索示例中，我们使用了两个列表，即OPEN和CLOSED列表。以下是遍历上述示例的迭代。

展开 S 的节点并放入 CLOSED 列表

初始化：打开[A, B]，关闭[S]

迭代 1：打开 [A]，关闭 [S, B]

迭代 2:打开 [E, F, A], 关闭 [S, B]
                  : 打开 [E, A], 关闭 [S, B, F]

迭代3：打开[I，G，E，A]，关闭[S，B，F]
                  ：打开[I，E，A]，关闭[S，B，F，G]

因此最终的解决方案路径将是：S----> B----->F----> G

时间复杂度： Greedy 最佳优先搜索的最坏情况时间复杂度为 O(b ^m )。

空间复杂度： Greedy 最佳优先搜索的最坏情况空间复杂度为 O(b ^m )。其中，m 是搜索空间的最大深度。

完全：即使给定的状态空间是有限的，贪婪的最佳优先搜索也是不完全的。

最优：贪心最佳优先搜索算法不是最优的。

2.) A* 搜索算法：

A* 搜索是最广为人知的最佳优先搜索形式。它使用启发式函数 h(n) 和从起始状态 g(n) 到达节点 n 的成本。它结合了UCS和贪婪最佳优先搜索的特点，有效地解决了问题。A* 搜索算法使用启发式函数查找通过搜索空间的最短路径。这种搜索算法扩展较少的搜索树并更快地提供最佳结果。A* 算法与 UCS 类似，只是它使用 g(n)+h(n) 而不是 g(n)。

在 A* 搜索算法中，我们使用搜索启发式以及到达节点的成本。因此，我们可以将两个成本组合如下，这个总和称为适应度数。

在搜索空间中的每个点，只扩展那些具有最低 f(n) 值的节点，当找到目标节点时，算法终止。

A*搜索算法：

Step1：将起始节点放入OPEN列表。

步骤2：检查OPEN列表是否为空，如果列表为空则返回失败并停止。

Step 3：从OPEN表中选择评价函数(g+h)最小的节点，如果节点n是目标节点则返回成功并停止，否则返回

Step 4：展开节点n并生成其所有的后继节点，将n放入闭链表中。对于每个后继 n'，检查 n' 是否已经在 OPEN 或 CLOSED 列表中，如果没有，则计算 n' 的评估函数并将其放入 Open 列表中。

步骤 5：否则，如果节点 n' 已经处于 OPEN 和 CLOSED 状态，那么它应该附加到反映最低 g(n') 值的后向指针。

第 6 步：返回第 2 步。

好处：

• A* 搜索算法是比其他搜索算法最好的算法。

• A* 搜索算法是最优且完整的。

• 这个算法可以解决非常复杂的问题。

缺点：

• 它并不总是产生最短路径，因为它主要基于启发式和近似。

• A* 搜索算法有一些复杂性问题。

• A* 的主要缺点是内存要求，因为它将所有生成的节点保留在内存中，因此对于各种大规模问题不切实际。

例子：

在这个例子中，我们将使用 A* 算法遍历给定的图。下表给出了所有状态的启发式值，因此我们将使用公式 f(n)= g(n) + h(n) 计算每个状态的 f(n)，其中 g(n) 是成本从开始状态到达任何节点。

这里我们将使用 OPEN 和 CLOSED 列表。

解决方案：

初始化： {(S, 5)}

迭代1： {(S--> A, 4), (S-->G, 10)}

迭代2： {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}

迭代3： {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A--> B, 7), (S-->G, 10)}

迭代 4将给出最终结果，因为S--->A--->C--->G它提供了成本为 6 的最佳路径。

要记住的要点：

• A* 算法返回最先出现的路径，并且不会搜索所有剩余的路径。

• A*算法的效率取决于启发式的质量。

• A*算法扩展所有满足条件f(n)的节点<c*, where="" c*="" is="" the="" cost="" of="" optimal="" solution="" path.=""

  <="" li="">

完整： A* 算法是完整的，只要：

• 分支因子是有限的。

• 每个动作的成本是固定的。

最优： A* 搜索算法在满足以下两个条件时是最优的：

• 可接受：优化的第一个条件是 h(n) 应该是 A* 树搜索的可接受启发式。可接受的启发式方法本质上是乐观的。

• 一致性：第二个必要条件是只有 A* 图形搜索的一致性。

如果启发式函数是可接受的，那么 A* 树搜索将始终找到成本最低的路径。

时间复杂度： A*搜索算法的时间复杂度取决于启发式函数，扩展的节点数与解d的深度呈指数关系。所以时间复杂度是 O(b^d)，其中 b 是分支因子。

空间复杂度： A*搜索算法的空间复杂度为O(b^d)