java - Java旅行推销员

我正在尝试为旅行推销员问题制作一个java实现。我读了很多关于不同优化算法的文章，我发现hold-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>();

这是一段应该有用的代码片段这段代码读取文件并将相应的值存储在映射和集合中：

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.
}
}

现在我在想，我用一个邻接表，而不是做一个邻接矩阵。使用hold-karp算法对tsp来说哪个更好？

最佳答案

下面是我在评论中建议的一个小例子它不是从文件中解析的，但我认为您可以处理它：-）

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());

}

这将为每个源创建到其目标的映射，这些目标映射到成本。
简而言之，映射可以看作是表单元组的列表（源、目标、成本）。