首页 文章

使用Java进行统一成本搜索的图形游览

提问于
浏览 次
2

我是这个网站的新手，所以希望你们不介意帮忙 .

无论如何，我被要求编写代码来查找特定图表上图表浏览的最短成本，其详细信息从文件中读取 . 图表如下所示：

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

这是一个人工智能课程，所以我希望使用足够好的搜索方法（允许暴力，但不是满分） .

我一直在阅读，我认为我正在寻找的是一个具有恒定启发 Value 的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对象内访问过其他顶点 .

非常感谢帮助！玩笑

EDIT: I should mention that paths previously visited may be visited again. In the case I provided this isn't beneficial, but there may be a case where visiting a node previously visited to get to another node would lead to a shorter path (I think). So I can't just do it based on nodes already visited (this was my first thought too)

java search graph artificial-intelligence

1 回答

  • 1

    两条评论：

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

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

    我希望这有帮助...

    回复于

相关问题