java - Java 旅行商

Question

我正在尝试为旅行商问题制作一个 Java 实现。我已经阅读了很多关于不同最优算法的文章，我发现 Held-Karp 算法是一个很好实现的算法。现在我的问题是，我正在尝试制作一个邻接矩阵来存储我的边值，然后使用这些值来实现算法，但我找不到制作邻接矩阵的良好逻辑。

我的代码从一个文件 (graphFile) 中读取，该文件具有边及其相关成本。文件如下:

A : B : 10
A : C : 3
A : D : 30
etc

现在我的代码读取文件，遍历每一行并将顶点(节点)以 [A, B, C, D, ...] 的形式存储在 SortedSet 中。同时，边以 {AB = 10, AC = 3, ...} 的形式连同它们的相关成本一起存储在 TreeMap 中。我使用我的顶点集来定义我的邻接矩阵的大小，这就是我被卡住的地方。

将边的关联值插入邻接矩阵的最佳方式是什么？这甚至是解决 TSP 的好方法，还是我走错了路？

static int[][] adjacencyMatrix;
static SortedSet<String> vertices  = new TreeSet<String>();
static TreeMap<String, Integer> edgeCost = new TreeMap<String, Integer>();

这是一个应该有帮助的代码片段。这段代码读取文件并将相应的值存储在 Map 和 Set 中:

while (graphFile.hasNextLine()) {
    line = graphFile.nextLine();
    tokenizer = line.split(" : "); 
    try {
        if (tokenizer.length != 3) {
            continue;
        }
        String source = tokenizer[0];
        String dest = tokenizer[1];
        String cost = tokenizer[2];
        addVertex(source, dest); //Add Vertex to set of vertices. Duplicates are removed.
        addEdge(source+dest, Integer.parseInt(cost)); //Add edges to an array then add array to list of edges.
    } catch (ArrayIndexOutOfBoundsException e) {
        System.err.println("Wrongly Formatted Line " + line);
    }
}

现在我有了计算邻接矩阵的代码。到目前为止，我设法只制作了矩阵的对角线部分(值 INF = 99999)。但是，我有一个逻辑问题，即如何将其余的 edgeCost 值存储在矩阵中。

private static void createAdjacencyMatrix() {

   for(int i=0; i<adjacencyMatrix.length; i++){
       for(int j=0; j<adjacencyMatrix.length; j++){
           if(i == j){
                adjacencyMatrix[i][j] = INF;
           }
       }
   }
   //Part where values of edgeCost should be added in matrix. Logic problem here.
}
}

现在我在想，我不做邻接矩阵，而是使用邻接表。对于使用 Held-Karp 算法的 TSP，哪个更好？

Answer 1

这是我在评论中建议的一个小例子。它不从文件中解析，但我认为你可以处理它:-)

public static void main(String[] args){
    TreeMap<String, Map<String, Integer>> routes = new TreeMap<String, Map<String, Integer>>();

    // create some input
    String[] routeStrings ={"a : b : 10", "a : c : 3", "a : d : 30", "d : a : 7", "d : b : 5"};

    // parse and populate map
    for (String route: routeStrings){
        String[] sourceDestinationCost = route.split(" : ");
        String source = sourceDestinationCost[0];
        String destination = sourceDestinationCost[1];
        Integer cost = Integer.parseInt(sourceDestinationCost[2]);

        // create entry for source if needed
        if (!routes.containsKey(source)){
            routes.put(source, new TreeMap<String, Integer>());
        }
        routes.get(source).put(destination, cost);
    }

    // see result
    System.out.println(routes.toString());

}

这会为每个来源创建一个到其目的地的映射，该目的地映射到成本。

简而言之， map 可以看作是形式为(源、目的地、成本)的元组列表。