AI 白盒搜索算法
到目前为止，我们已经讨论了不知情的搜索算法，该算法通过搜索空间寻找问题的所有可能解决方案，而无需任何其他有关搜索空间的知识。但是，明智的搜索算法包含一系列知识，例如我们距目标有多远，路径成本，如何到达目标节点等。此知识可帮助代理减少对搜索空间的探索，并更有效地找到目标节点。
明智的搜索算法对于较大的搜索空间更有用。白盒搜索算法采用启发式的思想，因此也称为启发式搜索。
启发式函数: 启发式是一种用于"知性搜索"的函数，它找到了最多的功能。有前途的道路。它以业务代表的当前状态作为其输入，并根据目标得出对业务代表的亲密程度的估计。但是，启发式方法可能并不总是提供最佳解决方案，但可以保证在合理的时间内找到一个好的解决方案。启发式函数估计状态与目标的接近程度。它由h(n)表示，并计算状态对之间最佳路径的成本。启发式函数的值始终为正。
启发式函数的可容许性为:
此处，h(n)是启发式成本，而h *(n)是估计成本。因此，启发式成本应小于或等于估计成本。
纯启发式搜索:
纯启发式搜索是启发式的最简单形式搜索算法。它根据节点的启发式值h(n)扩展节点。它维护两个列表，OPEN和CLOSED列表。在CLOSED列表中，它放置了已经扩展的节点，在OPEN列表中，它放置了尚未扩展的节点。
在每次迭代中，具有最低启发式值的每个节点n都会被扩展。并生成其所有后继，并且n放置在封闭列表中。该算法会在找到目标状态后继续执行。
在白盒搜索中，我们将讨论以下两个主要算法:
最佳优先搜索算法(贪婪搜索)
A *搜索算法
1、)最佳优先搜索算法(贪婪搜索):
贪婪的最佳优先搜索算法始终会选择此时出现的最佳路径。它是深度优先搜索和宽度优先搜索算法的结合。它使用启发式功能和搜索。最佳优先搜索使我们能够利用两种算法的优势。借助最佳优先搜索，我们可以在每个步骤中选择最有前途的节点。在最佳的优先搜索算法中，我们扩展最接近目标节点的节点，并通过启发函数估算最接近的成本，即
是，h(n)=从节点n到目标的估计成本。
贪婪的最佳优先算法是由优先级队列实现的。
最佳优先搜索算法:
步骤1: 。将起始节点放入"打开"列表中。
第2步: : 如果"打开"列表为空，则停止并返回失败。
第3步: : 从OPEN列表中删除具有最低h(n)值的节点n，并将其放在CLOSED列表中。
步骤4: 展开节点n，并生成节点n的后继者。
步骤5: : 检查节点n的每个后继节点，并确定是否有任何节点是目标节点。如果任何后续节点是目标节点，则返回成功并终止搜索，否则继续执行步骤6、
步骤6: : 对于每个后继节点，算法都会检查评估函数f(n)，然后检查该节点是否处于"打开"或"关闭"列表中。如果该节点不在两个列表中，则将其添加到"打开"列表中。
步骤7: 返回步骤2、
优势:
通过获得两种算法的优势，最佳优先搜索可以在BFS和DFS之间切换。
此算法比BFS和DFS算法更有效。
缺点:
在最坏的情况下，它可以充当无向导的深度优先搜索。
它可能像DFS一样陷入循环。
此算法不是最佳算法。
示例:
考虑以下搜索问题，我们将使用贪婪的最佳优先搜索遍历它。每次迭代时，使用下表中给出的评估函数f(n)= h(n)扩展每个节点。
在此搜索示例中，我们使用两个列表，
打开和
关闭列表。以下是遍历以上示例的迭代。
展开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
时间复杂度: 贪婪最佳优先搜索的最坏情况时间复杂度为O(b
m ) 。
空间复杂度: 贪婪最佳优先搜索的最坏情况是空间复杂度为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 *搜索的算法:
第一步: 将起始节点放在"打开"列表中。
步骤2: 检查OPEN列表是否为空，如果列表为空则返回失败并停止。
步骤3: OPEN列表中具有最小评估函数(g + h)值的节点，如果节点n是目标节点，则返回成功并停止，否则
步骤4: 节点n并生成其所有后继节点，并将n放入封闭列表中。对于每个后继n'，检查n'是否已在OPEN或CLOSED列表中，如果不是，则计算n'的评估函数，并放入Open列表中。 >否则，如果节点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)的所有节点。
完成: 只要满足以下条件，A *算法即可完成:
分支因子是有限的。
每项操作的费用是固定的。
最优: 如果满足以下两个条件，则A *搜索算法是最优的:
可允许的: 最优性的第一个条件是h(n)应该是A *树搜索的可允许启发式。可允许的启发式方法本质上是乐观的。
一致性: 第二个必要条件是仅A *图形搜索的一致性。
如果允许使用启发式函数，则A *树搜索将始终找到成本最小的路径。
时间复杂度: 搜索算法取决于启发式函数，并且扩展的节点数与解的深度d成指数关系。因此，时间复杂度为O(b ^ d)，其中b为分支因子。
空间复杂度: A *搜索算法的空间复杂度为
O( b ^ d)
