Java中统一成本搜索的图形漫游

我是新来的,所以希望你们不介意帮忙。

不管怎样,我被要求编写代码来查找特定图上的最短图巡更成本,该图的详细信息是从文件中读取的。图表如下:

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中的第一个节点(下一个成本最低的路径)。

我的问题基本上是,如果队列中指定的路径处于目标状态,如何停止程序遵循该路径?队列当前存储顶点对象,但在我看来这是行不通的,因为我无法存储是否在顶点对象内部访问了其他顶点。

非常感谢您的帮助! 乔希

编辑:我应该提到以前访问过的路径可能会再次访问。在这种情况下,我提供了这是不有益的,但可能有一种情况,访问一个节点之前访问到另一个节点将导致一个较短的路径(我认为)。所以我不能仅仅基于已经访问过的节点(这也是我的第一个想法)