我是这个网站的新手，希望各位不介意帮助一下菜鸟。

是这样的，我被要求编写代码，找到一个特定图上的最短图遍历成本，图的详细信息从文件中读取。图如下所示：

http://img339.imageshack.us/img339/8907/graphr.jpg

这是人工智能课程的作业，所以我需要使用一种足够好的搜索方法（暴力搜索是可以的，但不会得到满分）。

我一直在阅读相关资料，我认为我需要的是具有恒定启发式值的 A* 搜索，我相信它就是一致代价搜索。但我不太清楚如何在 Java 中应用它。

基本上，我目前有这些：

顶点类 –

ArrayList<Edge> adjacencies;String name;int costToThis;

边类 –

final Vertex target;public final int weight;

现在，我正在努力弄清楚如何将一致代价的概念应用于我期望的目标路径。 基本上，我必须从一个特定的节点开始，访问所有其他节点，然后以最低的成本回到同一个节点。

据我所知，我可以使用 PriorityQueue 来存储我所有遍历过的路径，但我无法理解如何将目标状态表示为已访问所有其他节点的起始节点。

这是我目前的代码，离目标还很远：

public static void visitNode(Vertex vertex) {      ArrayList<Edge> firstEdges = vertex.getAdjacencies();      for(Edge e : firstEdges) {         e.target.costToThis = e.weight + vertex.costToThis;         queue.add(e.target);      }      Vertex next = queue.remove();      visitNode(next);   }

最初，这会获取起始节点，然后递归访问 PriorityQueue 中的第一个节点（成本最低的路径）。

我的问题主要是，如果队列中指定的路径是目标状态，我该如何阻止我的程序继续沿着该路径走？ 队列当前存储的是 Vertex 对象，但在我看来这行不通，因为我无法在 Vertex 对象中存储其他顶点是否已被访问的信息。

非常感谢大家的帮助！@人名

编辑：我应该提到的是，之前访问过的路径可能会再次被访问。 在我提供的示例中，这没有好处，但在某些情况下，访问先前访问过的节点以到达另一个节点可能会导致更短的路径（我认为）。 所以我不能仅仅基于已经访问过的节点来做判断（这也是我的第一想法）

回答：

两条评论：

1) 当你设置顶点的 costToThis 时，你会覆盖现有值，这会影响队列中的所有路径，因为该顶点被许多路径共享。 我不会将 costToThis 存储为 Vertex 的一部分。 相反，我会定义一个 Path 类，其中包含路径的总成本以及组成它的节点列表。

2) 我不确定我是否正确理解了你关于目标状态的问题。 但是，我将部分路径添加到队列的方式如下：如果路径的长度 < N-1，则返回到任何已访问的节点都是非法的。 当 length=N-1 时，唯一的选择是返回到起始节点。 你可以将 visitedSet 添加到你的 Path 类（作为 HashSet），这样你就可以有效地检查给定的节点是否已被访问。

我希望这有帮助…