人工智能的智能搜索算法

本文概述

  • 纯启发式搜索
到目前为止,我们已经讨论了不知情的搜索算法,该算法通过搜索空间寻找问题的所有可能解决方案,而无需任何其他有关搜索空间的知识。但是,明智的搜索算法包含一系列知识,例如我们距目标有多远,路径成本,如何到达目标节点等。这些知识可帮助代理减少对搜索空间的探索,并更有效地找到目标节点。
信息搜索算法对于较大的搜索空间更有用。知情搜索算法使用启发式的思想,因此也称为启发式搜索。
启发式功能:启发式功能是在知情搜索中使用的功能,它找到了最有前途的路径。它以业务代表的当前状态作为其输入,并根据目标得出对业务代表的亲密程度的估计。但是,启发式方法可能并不总是提供最佳解决方案,但可以保证在合理的时间内找到一个好的解决方案。启发式函数估计状态与目标的接近程度。它由h(n)表示,并计算状态对之间最佳路径的成本。启发式函数的值始终为正。
启发式函数的可容许性为:
h(n) < = h*(n)

此处,h(n)是启发式成本,而h *(n)是估计成本。因此,启发式成本应小于或等于估计成本。
纯启发式搜索【人工智能的智能搜索算法】纯粹的启发式搜索是启发式搜索算法的最简单形式。它根据节点的启发式值h(n)扩展节点。它维护两个列表,OPEN和CLOSED列表。在“已关闭”列表中,它将放置已扩展的节点,在“打开”列表中,将放置尚未扩展的节点。
在每次迭代中,具有最低启发式值的每个节点n都会展开并生成其所有后继节点,并且n会放置在封闭列表中。该算法继续以找到目标状态为单位。
在知情的搜索中,我们将讨论以下两种主要算法:
  • 最佳优先搜索算法(贪婪搜索)
  • A *搜索算法
1.)最佳优先搜索算法(贪婪搜索):
贪婪的最佳优先搜索算法始终会选择此时出现的最佳路径。它是深度优先搜索算法和广度优先搜索算法的结合。它使用启发式功能和搜索。最佳优先搜索使我们能够利用两种算法的优势。借助最佳优先搜索,我们可以在每个步骤中选择最有前途的节点。在最好的优先搜索算法中,我们扩展最接近目标节点的节点,并通过启发式函数(即启发式函数)估算最近的成本。
f(n)= g(n).

h(n)=从节点n到目标的估计成本。
贪婪的最佳第一算法是由优先级队列实现的。
最佳优先搜索算法:
  • 步骤1:将起始节点放入OPEN列表中。
  • 步骤2:如果“打开”列表为空,则停止并返回失败。
  • 步骤3:从OPEN列表中删除具有最低h(n)值的节点n,并将其放在CLOSED列表中。
  • 步骤4:展开节点n,并生成节点n的后继者。
  • 步骤5:检查节点n的每个后继节点,并确定是否有任何节点是目标节点。如果任何后继节点是目标节点,则返回成功并终止搜索,否则继续执行步骤6。
  • 步骤6:对于每个后继节点,算法将检查评估函数f(n),然后检查该节点是否处于“打开”或“关闭”列表中。如果该节点不在两个列表中,则将其添加到OPEN列表中。
  • 步骤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(bm)。
空间复杂度:贪婪最佳优先搜索的最坏情况下的空间复杂度是O(bm)。其中,m是搜索空间的最大深度。
完全:即使给定的状态空间是有限的,贪婪的最佳第一搜索也是不完整的。
最佳:贪婪的最佳优先搜索算法不是最佳的。
2.)A *搜索算法:
A *搜索是最佳优先搜索的最普遍形式。它使用启发式函数h(n)和从起始状态g(n)到达节点n的成本。它结合了UCS和贪婪的最佳优先搜索功能,可以有效地解决问题。 A *搜索算法使用启发式函数查找通过搜索空间的最短路径。该搜索算法扩展了较少的搜索树,并更快地提供了最佳结果。 A *算法与UCS类似,不同之处在于它使用g(n)h(n)代替g(n)。
在A *搜索算法中,我们使用搜索启发式方法以及到达节点的成本。因此,我们可以将以下两种成本进行合并,该总和称为适应度数。
人工智能的智能搜索算法

文章图片
在搜索空间的每个点上,只有那些具有最低f(n)值的节点才会展开,并且算法在找到目标节点时终止。
A *搜索算法:
步骤1:将起始节点放在OPEN列表中。
步骤2:检查OPEN列表是否为空,如果列表为空,则返回失败并停止。
步骤3:从OPEN列表中选择评估函数值最小的节点(g h),如果节点n是目标节点,则返回成功并停止,否则
步骤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)是到达任意节点的起始状态的代价。
这里我们将使用开列表和闭列表。
人工智能的智能搜索算法

文章图片
解:
人工智能的智能搜索算法

文章图片
初始化:{(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 *树搜索将始终找到成本最低的路径。
时间复杂度:A *搜索算法的时间复杂度取决于启发式函数,并且扩展的节点数与解的深度d成指数关系。因此,时间复杂度为O(b ^ d),其中b是分支因子。
空间复杂度:A *搜索算法的空间复杂度为O(b ^ d)

    推荐阅读