通过搜寻可行解决方案空间来">解决问题是人工智能中一项名为状态空间搜索 的基本技术。 启发式搜索 是状态空间搜索的一种形式，利用有关一个问题的知识来更高效地查找解决方案。启发式搜索在各个领域荣获众多殊荣。在本文中，我们将向您介绍启发式搜索领域，并展示如何利用 Java 编程语言实现 A*，即最广为使用的启发式搜索算法。启发式搜索算法对计算资源和内存提出了较高的要求。我们还将展示如何避免昂贵的垃圾收集，以及如何利用一个替代的高性能 Java 集合框架 (JC++F)，通过这些改进 Java 实现。
启发式搜索
计算机科学中的许多问题可用一个图形数据结构表示，其中图形中的路径表示潜在的解决方案。查找最优解决方案需要找到一个最短路径。例如，以自主视频游戏角色为例。角色做出的每个动作都与图形中的一个边缘相对应，而且角色的目标是找到最短路径，与对手角色交手。
深度优先 搜索和广度优先 搜索等算法是流行的图形遍历算法。但它们被视为非启发式 算法，而且常常受到它们可以解决的问题规模的严格限制。此外，不能保证深度优先搜索能找到最优解决方案（或某些情况下的任何解决方案），可以保证广度优先搜索仅能在特殊情况下找到最优解决方案。相比之下，启发式搜索是一种提示性 搜索，利用有关一个问题的知识，以启发式 方式进行编码，从而更高效地解决问题。启发式搜索可以解决非启发式算法无法解决的很多难题。
视频游戏寻路是启发式搜索的一个受欢迎的领域，它还可以解决更复杂的问题。2007 年举行的无人驾驶汽车比赛 “DARPA 城市挑战赛” 的优胜者就利用了启发式搜索来规划平坦的、直接的可行使路线。启发式搜索在自然语言处理中也有成功应用，它被用于语音识别中的文本和堆栈解码句法解析。它在机器人学和生物信息学领域也有应用。与传统的动态编程方法相比较，使用启发式搜索可以使用更少的内存更快地解决多序列比对 (Multiple Sequence Alignment, MSA)，这是一个经过深入研究的信息学问题。
通过 Java 实现启发式搜索
Java 编程语言不是实现启发式搜索的一种受欢迎的选择，因为它对内存和计算资源的要求很高。出于性能原因，C/C++ 通常是首选语言。我们将证明 Java 是实现启发式搜索的一种合适的编程语言。我们首先表明，在解决受欢迎的基准问题集时，A* 的 textbook 实现确实很缓慢，并且会耗尽可用内存。我们通过重访一些关键实现细节和利用替代的 JCF 来解决这些性能问题。
很多这方面的工作都是本文作者合著的一篇学术论文中发表的作品的一个扩展。尽管原作专注于 C/C++ 编程，但在这里，我们展示了适用于 Java 的许多同样的概念。
广度优先搜索
熟悉广度优先搜索（一个共享许多相同概念和术语的更简单的算法）的实现，将帮助您理解实现启发式搜索的细节。我们将使用广度优先搜索的一个以代理为中心 的视图。在一个以代理为中心的视图中，代理据说处于某种状态，并且可从该状态获取一组适用的操作。应用操作可将代理从其当前状态转换到一个新的后继 状态。该视图适用于多种类型的问题。
广度优先搜索的目标是设计一系列操作，将代理从其初始状态引导至一个目标状态。从初始状态开始，广度优先搜索首先访问最近生成的状态。所有适用的操作在每个访问状态都可以得到应用，生成新的状态，然后该状态被添加到未访问状态列表（也称为搜索的前沿）。访问状态并生成所有后继状态的过程被称为扩展 该状态。
您可以将该搜索过程看作是生成了一个树：树的根节点表示初始状态，子节点由边缘连接，该边缘表示用于生成它们的操作。图 1 显示该搜索树的一个图解。白圈表示搜索前沿的节点。灰圈表示已展开的节点。
图 1. 二叉树上的广度优先搜索顺序
搜索树中的每一个节点表示某种状态，但两个独特的节点可表示同一状态。例如，搜索树中处于不同深度的一个节点可以与树中较高层的另一个节点具有同样的状态。这些重复 节点表示在搜索问题中达到同一状态的两种不同方式。重复节点可能存在问题，因此必须记住所有受访节点。
清单 1 显示广度优先搜索的伪代码：
清单 1. 广度优先搜索的伪代码
function: BREADTH-FIRST-SEARCH(initial)open ← {initial}closed ← 0loop do: if EMPTY(open) then return failure node ← SHALLOWEST(open) closed ← ADD(closed, node) for each action in ACTIONS(node) successor ← APPLY(action, node) if successor in closed then continue if GOAL(successor) then return SOLUTION(node) open ← INSERT(open, successor)
在 清单 1 中，我们将搜索前沿保留在一个 open 列表（第 2 行）中。将访问过的节点保留在 closed 列表（第 3 行）中。closed 列表有助于确保我们不会多次重访任何节点，从而不会重复搜索工作。仅当一个节点不在 closed 列表中时才能将其添加到前沿。搜索循环持续至 open 列表为空或找到目标为止。
在 图 1 中，您可能已经注意到，在移至下一层之前，广度优先搜索会访问搜索树的每个深度层的所有节点。在所有操作具有相同成本的问题中，搜素树中的所有边缘具有相同的权重，这样可保证广度优先搜索能找到最优解决方案。也就是说，生成的第一个目标在从初始状态开始的最短路径上。
在某些域中，每个操作有不同的成本。对于这些域，搜索树中的边缘具有不统一的权重。在这种情况下，一个解决方案的成本是从根到目标的路径上所有边缘权重的总和。对于这些域，无法保证广度优先搜索能找到最优解决方案。此外，广度优先搜索必须展开树的每个深度层的所有节点，直至生成目标。存储这些深度层所需的内存可能会快速超过最现代的计算机上的可用内存。这将广度优先搜索限制于很窄的几个小问题。
Dijkstra 的算法是广度优先搜索的一个扩展，它根据从初始状态到达节点的成本对搜索前沿上的节点进行排序（排列 open 列表）。不管操作成本是否统一（假设成本是非负值），它都确保可以找到最优解决方案。然而，它必须访问成本少于最优解决方案的所有节点，因此它被限制于解决较少的问题。下一节将描述一个能解决大量问题的算法，该算法能大幅减少查找最优解决方案所需访问的节点数量。