我需要帮助我的旅行推销员问题代码。它的窃听器…我知道,因为这是学校布置的作业,还有测试案例。就这样。
给出了一个连接图,在这里我需要访问节点的子集。如何计算最短路径?
作为一个例子,请参考上面的图片我需要从0开始,访问一些/所有节点,然后返回到0。在这个过程中,我需要计算最短路径。
假设我需要访问所有节点,我将从0 -> 1 -> 2 -> 3 -> 0=20 + 30 + 12 + 35 = 97开始。假设现在我只需要访问节点2,我将从0 -> 3 -> 2 -> 3 -> 0开始,因为这给出了最短路径94(如果它能给出最短路径,我可以访问不需要访问的节点)。
基本上,我做到了:
计算任意2对所需节点与源(0)之间的最短路径。这给了我一个最短路径2d表(我用dijkstra的):

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

现在,我修改了Shopping Sales Man算法(又名。使用此表当前的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);
}

visited用作位掩码,指示是否访问了节点
sssp是一个HashMap<Integer, HashMap<Integer, Integer>>,其中第一个hashmap的键是源节点,第二个hashmap的键是目标节点所以它基本上代表了点1中的二维表。
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

其中第1行是测试用例的数量第三行(3 3)。第一个3是节点数,第二个3是所需节点数。第4行是所需节点的列表。剩下的是边权重表。
失败的测试用例是:
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抱歉,我知道这很难调试…我也有同样的问题,测试用例太大了至少对人类来说所以我正在创建更小的测试用例来测试,但它们似乎通过了…

最佳答案

也许不是一个完整的答案,但我认为它至少指向了正确的方向:您的代码似乎给出了遵循路径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))来检查您是否已经访问了nodeitem然而,visited是由visit(visited, v)建立的,其中vshoppinglist的索引。item =shoppinglist[v]但如果要移动已访问的向量,则应该使用相同的方法。
您应该使用if (!hasVisited(visited, v))而不是if (!hasVisited(visited, item))
另一方面,我不确定寻找最短路径的第一步是必要的还是会影响你的结果。如果从a到B的直接链路比通过其他节点(例如C)的链路长,则在距离表中替换它如果您在最终的解决方案中使用该链接从A转到B,那么实际上您将通过C,它已经在您的路径中(因为该路径是一个完整的TSP解决方案)如果一个节点只能访问一次,那么这可能是一个问题。

10-06 05:14
查看更多