在 Java 中使用启发式搜索更快地解决问题

Patagonia

　　
td{word-break: break-all; word-wrap:break-word;}
了解启发式搜索领域及其在人工智能上的应用。本文作者展示了他们如何成功用 Java 实现了最广为使用的启发式搜索算法。他们的解决方案利用一个替代的 Java 集合框架，并使用最佳实践来避免过多的垃圾收集。
通过搜寻可行解决方案空间来解决问题是人工智能中一项名为状态空间搜索 的基本技术。 启发式搜索 是状态空间搜索的一种形式，利用有关一个问题的知识来更高效地查找解决方案。启发式搜索在各个领域荣获众多殊荣。在本文中，我们将向您介绍启发式搜索领域，并展示如何利用 Java 编程语言实现 A*，即最广为使用的启发式搜索算法。启发式搜索算法对计算资源和内存提出了较高的要求。我们还将展示如何避免昂贵的垃圾收集，以及如何利用一个替代的高性能 Java 集合框架 (JCF)，通过这些改进 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 ← 0
            loop 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 列表）。不管操作成本是否统一（假设成本是非负值），它都确保可以找到最优解决方案。然而，它必须访问成本少于最优解决方案的所有节点，因此它被限制于解决较少的问题。下一节将描述一个能解决大量问题的算法，该算法能大幅减少查找最优解决方案所需访问的节点数量。

A* 搜索算法
A* 算法或其变体是最广为使用的启发式搜索算法之一。可以将 A* 看作是 Dijkstra 的算法的一个扩展，它利用与一个问题有关的知识来减少查找一个解决方案所需的计算数量，同时仍然保证最优的解决方案。A* 和 Dijkstra 的算法是最佳优先 图形遍历算法的典型示例。它们是最佳优先算法，是因为他们首先访问最佳的节点，即出现在通往目标的最短路径上的那些节点，直至找到一个解决方案。对于许多问题，找到最佳解决方案至关重要，这是让 A* 这样的算法如此重要的原因。
A* 与其他图形遍历算法的不同之处在于使用了启发式估值。启发式估值是有关一个问题的一些知识（ 经验法则），该知识能让您做出更好的决策。在搜索算法的上下文中，启发式估值 有具体的含义：估算从特定节点到一个目标的成本的一个函数。A* 可以利用启发式估值来决定哪些节点是最应该访问的，从而避免不必要的计算。A* 尝试避免访问图形中几乎不通向最优解决方案的节点，通常可用比非启发式算法更少的内存快速找到解决方案。
A* 确定最应该访问哪些节点的方式是为每个节点计算一个值（我们将其称为 f 值），并根据该值对 open 列表进行排序。f 值是使用另外两个值计算出来的，即节点的 g 值 和 h 值。一个节点的 g 值是从初始状态到达一个节点所需的所有操作的总成本。从节点到目标的估算成本是其 h 值。这一估算值是启发式搜索中的启发式估值。f 值最小的节点是最应该访问的节点。
图 2 展示该搜索过程：
图 2. 基于 f 值的 A* 搜索顺序

在 图 2 的示例中，前沿有三个节点。有两个节点的 f 值是 5，一个节点的 f 值是 3。接下来展开 f 值最小的节点，该节点直接通往一个目标。这样一来 A* 就无需访问其他两个节点下的任何子树，如图 3 所示。这使得 A* 比广度优先搜索等算法要高效得多。
图 3. A* 不必访问 f 值较高的节点下的子树

如果 A* 使用的启发式估值是可接受的，那么 A* 仅访问找到最优解决方案所需的节点。为此 A* 很受欢迎。没有其他算法能用可接受的启发式估值，通过访问比 A* 更少的节点保证找到一个最优解决方案。要让启发式估算成为可接受的，它必须是一个下限值：一个小于或等于到达目标的成本的值。如果启发满足另一个属性，即一致性，那么将首次通过最优路径生成每个状态，而且该算法可以更高效地处理重复节点。
与上一节的广度优先搜索一样，A* 维护两个数据结构。已生成但尚未访问的节点存储在一个 open 列表 中，而且访问的所有标准节点都存储在一个 closed 列表 中。这些数据结构的实现以及使用它们的方式对性能有很大的影响。我们将在后面的一节中对此进行详细探讨。清单 2 显示 textbook A* 搜索的完整伪代码。
清单 2. A* 搜索的伪代码
   
        
            
            
            function: A*-SEARCH(initial)
            open ← {initial}
            closed ← 0
            loop do:
            if EMPTY(open) then return failure
            node ← BEST(open)
            if GOAL(node) then return SOLUTION(node)
            closed ← ADD(closed, node)
            for each action in ACTIONS(node)
            successor ← APPLY(action, node)
            if successor in open or successor in closed
            IMPROVE(successor)
            else
            open ← INSERT(open, successor)
            
            
        
   
在 清单 2 中，A* 从 open 列表中的初始节点入手。在每次循环迭代中，open 列表上的最佳节点被删除。接下来，open 上最佳节点的所有适用操作被应用，生成所有可能的后继节点。对于每个后继节点，我们将通过检查确认它表示的状态是否已被访问。如果没有，则将其添加到 open 列表。如果它已经被访问，则需要通过一个更好的路径确定我们是否达到了这一状态。如果是，则需要将该节点放在 open 列表上，并删除次优的节点。
我们可以使用有关要解决的问题的两个假设简化这一段伪代码：我们假设所有操作有相同的成本，而且我们有可接受的、一致的启发式估值。因为启发式估值是一致的，且域中的所有操作具有相同的成本，那么我们永远无法通过一个更好的路径重访一个状态。结果还表明，对于一些域，在 open 列表中放置重复节点比每次生成新节点时检查是否有重复节点更高效。因此，我们可以通过将所有新后继节点附加到 open 列表来简化实现，不管它们是否已经被访问。我们通过将 清单 2 中的最后四行组合为一行来简化伪代码。我们仍然需要避免循环，因此在展开一个节点之前，必须检查是否有重复节点。我们可以省略掉 IMPROVE 函数的细节，因为在简化版本中不再需要它。清单 3 显示简化的伪代码：
清单 3. A* 搜索的简化伪代码
   
        
            
            
            function: A*-SEARCH(initial)
            open ← {initial}
            closed ← 0
            loop do:
            if EMPTY(open) then return failure
            node ← BEST(open)
            if node in closed continue
            if GOAL(node) then return SOLUTION(node)
            closed ← ADD(closed, node)
            for each action in ACTIONS(node)
            successor ← APPLY(action, node)
            open ← INSERT(open, successor)
            
            
        
   


A* 的 Java textbook 实现
本节我们将介绍如何基于 清单 3 中简化的伪代码完成 A* 的 Java textbook 实现。您会看到，这一实现无法解决 30GB 内存限制下的一个标准启发式搜索基准。
我们希望我们的实现尽量大众化，因此我们首先定义了一些接口来提取 A* 要解决的问题。我们想通过 A* 解决的任何问题都必须实现 Domain接口。Domain 接口提供具有以下用途的方法：

   
• 查询初始状态
• 查询一个状态的适用操作
• 计算一个状态的启发式估值
• 生成后继状态
  

清单 4 显示了 Domain 接口的完整代码：
清单 4. Domain 接口的 Java 源代码
   
        
            
            
            public interface Domain {
            public T initial();
            public int h(T state);
            public boolean isGoal(T state);
            public int numActions(T state);
            public int nthAction(T state, int nth);
            public Edge apply (T state, int op);
            public T copy(T state);
            }
            
            
        
   
A* 搜索为搜索树生成边缘和节点对象，因此我们需要 Edge 和 Node 类。每个节点包含 4 个字段：节点表示的状态、对父节点的引用，以及节点的 g 和 h 值。清单 5 显示 Node 类的完整代码：
清单 5. Node 类的 Java 源代码
   
        
            
            
            class Node {
            final int f, g, pop;
            final Node parent;
            final T state;
            private Node (T state, Node parent, int cost, int pop) {
            this.g = (parent != null) ? parent.g+cost : cost;
            this.f = g + domain.h(state);
            this.pop = pop;
            this.parent = parent;
            this.state = state;
            }
            }
            
            
        
   
每个边缘有三个字段：边缘的成本或权重、用于为边缘生成后继节点的操作，以及用于为边缘生成父节点的操作。清单 6 显示了 Edge 类的完整代码：
清单 6. Edge 类的 Java 源代码
   
        
            
            
            public class Edge {
            public int cost;
            public int action;
            public int parentAction;
            public Edge(int cost, int action, int parentAction) {
            this.cost = cost;
            this.action = action;
            this.parentAction = parentAction;
            }
            }
            
            
        
   
A* 算法本身会实现 SearchAlgorithm 接口，而且仅需要 Domain 和 Edge 接口。SearchAlgorithm 接口仅提供一个方法来执行具有指定初始状态的搜索。search() 方法返回 SearchResult 的一个实例。SearchResult 类提供搜索统计。SearchAlgorithm 接口的定义如清单 7 所示：
清单 7. SearchAlgorithm 接口的 Java 源代码
   
        
            
            
            public interface SearchAlgorithm {
            public SearchResult search(T state);
            }
            
            
        
   
用于 open 和 closed 列表的数据结构的选择是一个重要的实现细节。我们将使用 Java 的 PriorityQueue 实现 open 列表。PriorityQueue 是一个平衡的二进制堆的实现，包含用于元素入列和出列的 O(log n) 时间、用于测试一个元素是否在队列中的线性时间，以及用于访问队列头的约束时间。二进制堆是实现 open 列表的一个流行数据结构。稍后您会看到，对于一些域，可以使用一个名为桶优先级队列 的更高效的数据结构来实现 open 列表。
我们必须实现 Comparator 接口让 PriorityQueue 合理地对节点进行排序。对于 A* 算法，我们需要根据 f 值对每个节点排序。在许多节点的 f 值相同的域中，一个简单的优化是通过选择 g 值较高的节点来打破平局。试着花点时间说服自己为何以这种方式打破平局能提高 A* 的性能（提示：h 是一个估算值；而 g 不是）。清单 8 包含完整的 Comparator 实现代码：
清单 8. NodeComparator 类的 Java 源代码
   
        
            
            
            class NodeComparator implements Comparator {
            public int compare(Node a, Node b) {
            if (a.f == b.f) {
            return b.g - a.g;
            }
            else {
            return a.f - b.f;
            }
            }
            }


本文来自ChinaUnix新闻频道，如果查看原文请点：http://news.chinaunix.net/opensource/2013/0924/2951021.shtml

rover12421

真高级,表示有压力