A*搜索（A* search），理学-计算机科学技术-人工智能-机器学习-知识表示-案例推理，一种启发式搜索（heuristic search）算法，通过使用最佳优先搜索策略来选取每一步的搜索节点，从而找出一条从初始节点到目标节点的代价最小路径。最早由彼得·哈特（Peter Hart）、尼尔斯·尼尔森（Nils Nilsson）和贝特拉姆·拉斐尔（Bertram Raphael）三人于1968年正式提出，是Edsger Dijkstra算法的扩展版本。具体来说，A*算法维护了一个备选搜索节点集合，以表示当前所有可到达的未搜索节点。在每个搜索步中，算法从中找出代价最小的节点，对搜索范围进行扩展，直至搜索到目标节点或者搜索失败返回。该算法广泛应用于路径寻找和图遍历等问题。在搜索过程中，A*算法需要使用每个备选节点的代价来决定搜索方向。由于算法无法获取其真实的代价，A*算法使用了启发式的方法对搜索代价进行估计。具体地说，节点n的代价可以表示为f(n) =g(n) +h(n)，其中g(n)为起始节点到节点n的代价，h(n)为节点n到目标节点的代价。