人工智能/搜索/启发式搜索/A*搜索

人工智能中的搜索算法

搜索技术是通用的问题解决方法。当有一个公式化的搜索问题时，一组状态，一组操作，一个初始状态和一个目标准则，我们可以使用搜索技术来解决问题（Pearl & Korf，1987）。Cawsey（1998）用简单的话解释了搜索算法：假设你试图在一个有很多单行道的城镇中找到自己的路。从你的初始状态（A）到目标目的地（B）有许多路线，但你不知道要走哪一条。在现实生活中，你可以尝试你喜欢的任何路线，尽管这可能是一个困难的过程。在整个过程中，可能会有很多不便之处：一旦你通过了一条街道，你可能无法返回，因为它是一条单行道，或者你可能被困在一个公园里。这种简化的寻找地点的思路表明，我们实际上可以在这样的例子中映射出所有可能的路线；即使很累，你最终也会找到一条路。在上面介绍的小规模搜索问题中，简单的搜索技术足以进行系统搜索。但是，有时我们需要系统地搜索这样的路线，例如，在一个更复杂的图上。我们该怎么做？搜索算法很适合解决这类问题。问题可能是一个物理问题，例如从 A 步行或开车到 B；或者它可能是抽象的，例如定理中的一组步骤，这将允许我们从一组事实中证明。

A*搜索算法

启发式搜索利用了这样一个事实，即大多数问题空间提供了一些信息，可以区分不同状态，这些信息可以根据状态导致目标的可能性来区分它们。这种信息称为启发式评估函数（Pearl & Korf，1987）。换句话说，启发式搜索的目标是在寻找目标时减少搜索的节点数量（Kopec & Marsland，2001）。

最广泛使用的最佳优先搜索形式称为 A*，发音为 A 星。它是一种启发式搜索方法，用于最小化给定问题中的搜索成本（Bolc & Cytowski，1992）。它旨在找到从给定的初始节点到目标节点的最低成本路径。它是最佳优先搜索算法的扩展形式。最佳优先搜索算法也试图找到一种解决方案来最小化搜索路径的总成本。但是，与最佳优先搜索不同的是，A*还考虑了从开始点的成本，而不仅仅是先前访问节点的局部成本。最佳优先搜索在任何预先确定的问题空间中找到目标状态。但是，它不能保证它会选择通往目标的最佳路径（Pearl & Korf，1987）。例如，如果有两个选项可以选择，其中一个选项距离起点很远，但对到达目标的距离估计略短，而另一个选项非常靠近起点，但对到达目标的距离估计略长，最佳优先搜索将总是选择扩展下一个距离估计最短的状态。A*算法修正了最佳优先搜索的这个缺点（Pearl & Korf，1987）。

简而言之，A*算法搜索从起点到找到最短路径或最便宜成本到达目标的所有可能的路线。这里的最短路径、最便宜成本等术语指的是一个通用概念。它可能是根据问题而定的其他术语。例如，在地图问题中，成本被替换为距离（Cawsey，1998）。A*可以减少搜索空间中所有可能路径的必要性，并导致更快的解决方案。A*通过组合 g(n) 和 h(n) 来评估节点。在讨论 A* 时使用的标准术语中

f(n)= g(n)+h(n)

该方程的目的是在给定问题中获得最低的 f 分数。n 是直到最终节点遍历的节点数，

f(n) 是总搜索成本， g(n) 是从初始起点到节点 n 的路径的实际最低成本（最短距离）， h(n) 是从节点 n 到目标节点的最便宜成本（距离）的估计值。该方程的这一部分也称为启发式函数/估计。

在每个节点上，选择最低的 f 值作为要扩展的下一步，直到选择目标节点并将其用于扩展。（Pearl & Korf，1987）。只要启发式函数满足某些条件，A*搜索既是完整的又是最优的（Russell & Norvig，2003）。

A*搜索算法的特征

可接受性。保证找到最优解（如果有）的策略称为可接受的。为了使启发式方法可接受，需要满足几个条件。如果使用树搜索，A*的最优性分析起来很简单（Russell & Norvig，2003）。在这种情况下，如果 h(n) 是可接受的启发式方法，那么 A* 是最优的。

h*(n) = 从 n 到目标的实际最小成本。

如果对所有状态 n，h(n) ≤ h*(n)，则启发式方法 h 是可接受的。

收敛性。如果搜索策略承诺找到路径、解图或有关它们是否存在的信息，则该策略是收敛的（Bolc & Cytowski，1992）。如果有解，A* 将始终找到它。对于任何具有非负成本函数的网络（有限或无限），A* 搜索算法的收敛性属性都得到满足。对于具有非负成本函数的有限网络，如果 A* 在找到解后终止，或者如果不存在解，则它就是收敛的。循环路径中的路径数量是有限的。先前检查过的节点，例如 w，仅当搜索找到比先前更小的成本时才会被重新访问。成本函数是非负的；因此，一条边只能检查一次。因此，A* 是收敛的（Bolc & Cytowski，1992）。

A*搜索算法的问题

根据 Pearl & Korf（1987），A* 和任何最佳优先搜索的主要缺点是其内存需求。由于必须保存整个开放路径列表，因此 A* 在实践中是空间受限的，并且与广度优先搜索一样实用。对于大型搜索空间，A* 会耗尽内存。幸运的是，通过使用迭代加深 A*（IDA*）可以节省大量内存。

A*伪代码

（匿名，2006）

create the open list of nodes, initially containing only our starting node
create the closed list of nodes, initially empty

while (we have not reached our goal) 
{
	consider the best node in the open list (the node with the lowest f value)

	if (this node is the goal) 
        {
		then we're done
	}
	else 
        {
		move the current node to the closed list and consider all of its neighbors

		for (each neighbor) 
                {
			if (this neighbor is in the closed list and our current g value is lower) 
                        {
				update the neighbor with the new, lower, g value 
				change the neighbor's parent to our current node
			}
			else if (this neighbor is in the open list and our current g value is lower) 
                        {
				update the neighbor with the new, lower, g value 
				change the neighbor's parent to our current node
			}
			else this neighbor is not in either the open or closed list 
                        {
				add the neighbor to the open list and set its g value
			}
		}
	}
}

A*的实际应用

A* 是最流行的寻路选择，因为它相当灵活，可以在各种环境中使用，例如游戏（8 数码难题和寻路器）。

A* 的变体
双向搜索
迭代加深
束搜索
动态加权
带宽搜索
动态 A* 和终身规划 A*

一些在线资源

http://www.policyalmanac.org/games/aStarTutorial.htm
http://wiki.gamegardens.com/Path_Finding_Tutorial#A.2A_Examples
intelligence.worldofcomputing.net/ai-search/a-star-algorithm.html

参考资料

匿名，（2006）。寻路教程，（2008 年 10 月 14 日从 http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A 检索）
Bolc，L..，& Cytowski，J.，（1992）。人工智能的搜索方法。伦敦：学术出版社。
Cawsey，A.（1998）。人工智能的本质。新泽西州上鞍河：普伦蒂斯·霍尔
Kopec, D. & Marsland, T.A. (2001). 搜索。检索于 2008 年 10 月 10 日，来自 http://www.cs.ualberta.ca/~tony/RecentPapers/Draft.5.2.pdf
Pearl, J. & Korf, R. E.(1987). 搜索技术。计算机科学年度评论, 451-467.
Russell, S. J., & Norvig, P. (2003). 人工智能：现代方法。新泽西州上鞍河：普伦蒂斯·霍尔