1

この問題をどのように解決しますか::

ロボットは 4x4 グリッドの左上隅にあります。ロボットは上下左右に移動できますが、同じ場所を 2 回訪れることはできません。ロボットはグリッドの右下隅に到達しようとしています。

私のアイデア:

すべてのソリューションのツリーをたどり、ゴール セルに到達したら出力するバックトラッキング ソリューション。私はそれを実装しましたが、それが正しいか、理にかなっているのか、それとも正しいアプローチなのかはわかりません。ここにコードを投稿しましたが、何が問題なのか誰かが説明できれば幸いです。

開始セルから開始し、その隣接セルのそれぞれからゴール セルへのパスを再帰的に見つけ、基本ケースがゴール セルに到達する再帰的ソリューション。

質問:

1) これら 2 つの表現方法は同じ考えですか?

2) これらのアイデアは理にかなっていますか?

3) これらの各ソリューションの時間計算量はどれくらいですか? 2番目は4^nだと思いますか？

4) 私のバックトラッキング コードは意味がありますか?

5) これを行うためのもっと簡単な方法はありますか?

N = 4 の正しいパス数を出力するコードは次のとおりです。正しいですか?

#define N 4
int counter = 0;
bool legal_move(int x, int y, int array[N+2][N+2]){
  bool ret = (array[x][y] == 1);
  array[x][y] = 0;
  return ret;
}

/*
void print_array(int array[N+2][N+2]){
  for(int i = 0; i < N+2; i++){
    for(int j = 0; j < N+2; j++)
      cout << array[i][j] << " ";
    cout << endl;
  }
  cout << endl << endl;
}
*/

void print_paths(int x, int y, int n, int m, int array[N+2][N+2]){
  if(x == n && y == m){
    print_array(array);
    counter++;
  }
  else {
    int dx = 1;
    int dy = 0;
    for(int i = 0; i < 4; i++){
      if(legal_move(x + dx, y + dy, array)){
        print_paths(x + dx, y + dy, n, m, array);
        array[x+dx][y+dy] = 1;
      }
      swap(dx,dy);
      if(i == 1)
        dx = -dx;
    }
  }
}

int main(){

  int array[N+2][N+2];

  for(int i = 1; i < N+1; i++)
    for(int j = 1; j < N+1; j++)
      array[i][j] = 1;

  for(int i = 0; i < N+2; i++)
    array[0][i] = array[i][0] = array[N+1][i] = array[i][N+1] = 0;

//print_array(array);
  array[1][1] = 0;  //Set start cell to be seen.
  print_paths(1,1,N,N,array);
  cout << counter << endl;
}
4

2 に答える 2

1

同じ考えだと思います。

コードの問題は、「が、同じ場所を 2 回訪れることはできない」を正しく実装していないことです。

あなたのロボットが S から A に何らかの経路で移動したと仮定し、A に隣接する B に移動するかどうかを調べているとします。テストは、「ロボットは現在の経路で以前に B に行ったことがありますか」である必要があります。しかし、あなたが実装したのは、「ロボットが以前に任意のパスで B を訪れた」ということです。

つまり、現在のパスに追加のパラメーターを取得するように変更print_pathsし、それを使用してテストを正しく実装する必要があります。

于 2013-11-10T11:30:57.023 に答える