algorithm - 巡回セールスマン (ノードのサブセットのみを訪問する必要があります): 盗聴

Question

巡回セールスマンの問題コードについて助けが必要です。盗聴されています...学校の課題であり、テストケースがあるため、私は知っています。それで、ここに行きます。

ノードのサブセットにアクセスする必要がある接続グラフが与えられました。最短経路を計算するにはどうすればよいですか?

ここに画像の説明を入力

例として、上の画像を参照してください。0 から開始し、一部またはすべてのノードにアクセスしてからゼロに戻る必要があります。その過程で、最短経路を計算する必要があります。

すべてのノードにアクセスする必要があるとします。 0 -> 1 -> 2 -> 3 -> 0=から移動し20 + 30 + 12 + 35 = 97ます。ここで、ノード 2 にアクセスするだけでよいと0 -> 3 -> 2 -> 3 -> 0します。最短パスが 94 であるため、そこから移動します (最短パスが得られる場合は、アクセスする必要のないノードにアクセスできます)。

基本的に、私はしました：

必要なノードの任意の 2 ペアとソース (0) の間の最短パスを計算します。これにより、次のような最短パスの2Dテーブルが得られます（ダイクストラを使用しました）：
```
  |  0  1  2  3
--+--------------
0 | 
1 |
2 | 
3 |
```

ここで、このテーブルを使用するようにショッピングセールスマンアルゴリズム (別名、Floyd Warshall または APSP) を変更します。現在の Java ソース (TSP およびダイクストラ) は次のようになります。

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>>、1 番目のハッシュマップのキーがソースノードで、2 番目のハッシュマップのキーが宛先ノードです。したがって、基本的には、ポイント 1 で見た 2D テーブルを表します。
memo訪問したビットマップを指定して、以前に計算したノードからの最短パスの「キャッシュ」として動的プログラミングで使用したものです。

完全なソース: http://pastie.org/5171509

合格するテストケース:

1行目はテストケースの数です。3 行目 ( 3 3)。13番目はノードの数、2 番目の 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です...申し訳ありませんが、これはデバッグが難しいことを知っています...私は同じ問題を抱えています.テストケースが大きすぎます...少なくとも人間にとって...テストするテストケースですが、合格しているようです...

score 2 · Accepted Answer

おそらく完全な答えではありませんが、少なくとも正しい方向を指していると思います.コードは、パス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))すでに node にアクセスしたかどうかを確認する行がありますitem。ただし、訪問済みはによって構築されvisit(visited, v)、vはへのインデックスshoppinglistです。item =shoppinglist[v]ただし、訪問したベクトルをシフトする場合は、同じものを使用する必要があります。

if (!hasVisited(visited, v))代わりに使用する必要がありますif (!hasVisited(visited, item))

関係のない話ですが、最短経路を見つける最初のステップが必要なのか、それとも結果に影響を与える可能性があるのかはわかりません. A から B への直接リンクが他のノード (C など) を経由するよりも長い場合、距離テーブルで置き換えられます。最終的なソリューションでそのリンクを使用して A から B に移動する場合、実際には C を経由することになり、C は既にパスに含まれています (そのパスは完全な TSP ソリューションであるため)。ノードに 1 回しかアクセスできない場合、これは問題である可能性があります。

algorithm - 巡回セールスマン (ノードのサブセットのみを訪問する必要があります): 盗聴

1 に答える 1

Related

Reference