1

再帰的なバックトラッキング/動的プログラミングとビットマスキングを使用して、UVA ジャッジ(以下のコードを参照)の問題を部分的に解決しました。

これにより、含まれているテスト ケースに対する正しい最終的な答えが得られますが、再帰ルーチンで保存する方法がわからない最適なパス ルートも出力する必要があります。

問題は巡回セールスマンの問題で、基本的には次のような問題です。

座標nを指定して、これらすべての座標間の最短経路を見つけます。

#include<iostream>
#include<cmath>
#include<climits>
#include<cstdio>
using namespace std;

#define MAX_N 10

struct Computer{
  double x;
  double y;
};

Computer computers[MAX_N];
double dist[MAX_N][MAX_N];
double DP[MAX_N][1 << MAX_N];

size_t n; 

double d(Computer a, Computer b) {
  return sqrt(pow((a.x - b.x), 2.0) + pow((a.y - b.y), 2.0)) + 16.0;
}

double recurse(int i, int switched)
{
  if(switched == (1 << n) - 1) return 0;
  if(DP[i][switched] != 0) return DP[i][switched];

  double local_min = INT_MAX;
  for(int j = 0; j < n; j++)
    if(i != j && !(switched & (1 << j)))
      local_min = min(dist[i][j] + recurse(j, switched | (1 << j)), local_min);

  return DP[i][switched] = local_min;
}

int main()
{
  for(unsigned int p = 1; cin >> n; p++) {
    if(n == 0) return 0;
    memset(DP, 0, sizeof DP);

    for(size_t i = 0; i < n; ++i) {
      Computer c; cin >> c.x >> c.y;
      computers[i] = c;
    }

    for(size_t i = 0; i < n; ++i) for(size_t j = 0; j < n; ++j)
      dist[i][j] = d(computers[i], computers[j]);

    printf("%d: %.2f\n", p, recurse(0, 1));
  }
}
4

2 に答える 2

1

1 人用パズルで最適なパスを収集することは、チェスなどの 2 人用ゲームで主要なバリエーションを保存するのと同様の問題です。実装方法については、このリンクを参照してください。

アイデアは、ステップのベクトル/配列 (チェスでの動き) へのポインターを格納し、バックトラッキング アルゴリズムがこれまでの最短経路で改善を見つけるたびにその配列を更新することです。

于 2012-09-11T11:37:34.670 に答える
1

パスを保存する一般的な方法は、パスファインダーが現在のポイントに到達するために使用したノードを保存する追加のマップを追跡することです。終了ノードへの最適なルートを見つけたら、開始ノードに戻るまでこのマップを照会できます。

于 2012-09-11T11:37:26.083 に答える