algorithm - 旅行商(只需要访问节点的子集): Bugged

Question

我需要有关旅行推销员问题代码的帮助。它被窃听了......我知道，因为它是一项学校作业并且有测试用例。所以就这样了。

给定一个连通图，我需要访问其中的一个节点子集。如何计算最短路径？

例如，请引用上图。我需要从 0 开始并访问一些/所有节点然后返回到零。在此过程中，我需要计算最短路径。

假设我需要访问所有节点，我将从0 -> 1 -> 2 -> 3 -> 0开始= 20 + 30 + 12 + 35 = 97 .假设现在我只需要访问节点2，我会从0 -> 3 -> 2 -> 3 -> 0因为它给出了 94 的最短路径(如果它可以给出最短路径，我可以访问我不必访问的节点)。

基本上，我做了:

1. 计算任意两对所需节点与源 (0) 之间的最短路径。这给了我一个最短路径 2D 表，例如(我使用了 dijkstra 的):

     |  0  1  2  3
   --+--------------
   0 | 
   1 |
   2 | 
   3 |
   

2. 现在，我修改购物销售员算法(又名 Floyd Warshall 或 APSP)以使用此表。当前的 Java 源代码(TSP 和 dijkstra 的)看起来像:

   int TSP(int source, int visited) {
      if (visited == (int)(Math.pow(2, K)-1)) { // all required visited
       return sssp.get(source).get(0); // return to source (0)
     } else if (memo.containsKey(source) && memo.get(source).containsKey(visited)) {
       return memo.get(source).get(visited);
     } else {
       int item;
       if (!memo.containsKey(source)) {
         memo.put(source, new HashMap<Integer, Integer>());
       }
       memo.get(source).put(visited, 1000000);
       for (int v = 0; v < K; v++) {
         item = shoppingList[v];
         if (!hasVisited(visited, item)) {
           memo.get(source).put(visited, Math.min(
             memo.get(source).get(visited),
             sssp.get(source).get(item) + TSP(item, visit(visited, v))
           ));
         }
       }
       return memo.get(source).get(visited);
     }
   }
   
   int dijkstra(int src, int dest) {
     PriorityQueue<IntegerPair> PQ = new PriorityQueue<IntegerPair>();
     HashMap<Integer, Integer> dist = new HashMap<Integer, Integer>(); // shortest known dist from {src} to {node}
     // init shortest known distance
     for (int i = 0; i < N+1; i++) {
       if (i != src) {
         dist.put(i, Integer.MAX_VALUE); // dist to any {i} is big(unknown) by default
       } else {
         dist.put(src, 0); // dist to {src} is always 0
       }
     }
     IntegerPair node;
     int nodeDist;
     int nodeIndex;
   
     PQ.offer(new IntegerPair(0, src)); 
     while (PQ.size() > 0) {
       node = PQ.poll();
       nodeDist = node.first();
       nodeIndex = node.second();
   
       if (nodeDist == dist.get(nodeIndex)) {
         // process out going edges
         for (int v = 0; v < N+1; v++) { // since its a complete graph, process all edges
           if (v != nodeIndex) { // except curr node
             if (dist.get(v) > dist.get(nodeIndex) + T[nodeIndex][v]) { // relax if possible
               dist.put(v, dist.get(nodeIndex) + T[nodeIndex][v]);
               PQ.offer(new IntegerPair(dist.get(v), v));
             }
           }
         }
       }
     }
     return dist.get(dest);
   }
   

   1. visited用作位掩码以指示是否已访问节点
   2. sssp是 HashMap<Integer, HashMap<Integer, Integer>>其中第一个 HashMap 的键是源节点，第二个 HashMap 的键是目的地。所以它基本上代表了您在第 1 点中看到的二维表格。
   3. memo正是我在动态规划中使用的，作为先前从节点计算的最短路径的“缓存”，给定一个已访问的位图。

完整来源: http://pastie.org/5171509

通过的测试用例:

1

3 3
1 2 3
0 20 51 35
20 0 30 34
51 30 0 12  
35 34 12 0 

其中第一行是测试用例的数量。第三行(3 3)。第一期3是节点数，2nd 3是需要的节点数。第四行是所需节点的列表。然后剩下的就是边权表了。

失败的测试用例是:

9 9
1 2 3 4 5 6 7 8 9
0 42 360 335 188 170 725 479 359 206
42 0 402 377 146 212 767 521 401 248
360 402 0 573 548 190 392 488 490 154
335 377 573 0 293 383 422 717 683 419
188 146 548 293 0 358 715 667 539 394
170 212 190 383 358 0 582 370 300 36
725 767 392 422 715 582 0 880 704 546
479 521 488 717 667 370 880 0 323 334
359 401 490 683 539 300 704 323 0 336
206 248 154 419 394 36 546 334 336 0

我得到了 3995 但答案是 2537...抱歉我知道这很难调试...我遇到了同样的问题，测试用例太大...至少对人类来说...所以我我正在创建较小的测试用例进行测试，但它们似乎通过了……

Answer 1

也许不是一个完整的答案，但我认为它至少指向了正确的方向:您的代码似乎给出了遵循路径 0->1->2->...->N->0 的结果。似乎没有真正的优化发生。

我稍微修改了你的代码以获得一个小的失败测试用例:

int[][]mat=new int[N+1][N+1];
//original
//mat[0]=new int[]{0,20,51,35};
//mat[1]=new int[]{20,0,30,34};
//mat[2]=new int[]{51,30,0,12};
//mat[3]=new int[]{35,34,12,0};
//switched order of nodes, node 2 is now node 1
mat[0]=new int[]{0,51,20,35};
mat[1]=new int[]{51,0,30,12};
mat[2]=new int[]{20,30,0,34};
mat[3]=new int[]{35,12,34,0};

这会产生 146 作为最佳路径，表明它遵循路径 0->1->2->3->0(47+30+34+35，47 是使用节点 4 从 0 到 1 的最短路径)(所有节点号都用我的命令开关)。

编辑:我又快速看了一眼，找到了罪魁祸首。您有 if (!hasVisited(visited, item)) 行来检查您是否已经访问了节点 item。但是，visited 是由 visit(visited, v) 构建的，其中 v 是 shoppinglist 的索引。 item =shoppinglist[v] 但如果您要移动访问向量，则应使用相同的方法。

您应该使用 if (!hasVisited(visited, v)) 而不是 if (!hasVisited(visited, item))

顺便说一句，我不确定寻找最短路径的第一步是否必要或是否会影响您的结果。如果从 A 到 B 的直接链接比通过其他节点(比如 C)的路径长，则它会在距离表中被替换。如果您随后在最终解决方案中使用该链接从 A 到 B，那么您实际上将通过 C，它已经在您的路径中(因为该路径是完整的 TSP 解决方案)。如果一个节点只能被访问一次，那么这可能是一个问题。