0

このサイトで指定されているように、バックトラッキングを使用してナイト ツアーの問題を解決しようとしています。

サイトで提供されている実装には、 ideone で約 0.49 秒かかります。 

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N],
                int yMove[N])
{
   int k, next_x, next_y;
   if (movei == N*N)
       return true;

   /* Try all next moves from the current coordinate x, y */
   for (k = 0; k < 8; k++)
   {
       next_x = x + xMove[k];
       next_y = y + yMove[k];
       if (isSafe(next_x, next_y, sol))
       {
         sol[next_x][next_y] = movei;
         if (solveKTUtil(next_x, next_y, movei+1, sol, xMove, yMove) == true)
             return true;
         else
             sol[next_x][next_y] = -1;// backtracking
       }
   }

   return false;
}

ほぼ同じ私が実装したものは、 ideone で制限時間を超えた（5秒以上）ことを示しています。

int generateMoves(int x, int y, int moveNum, int soln[][N], int xMoves[], int yMoves[])//making move number 'moveNum' from x and y.
{
        if(moveNum == N*N){
                return 1;
        }
        else{
                int i, nextX, nextY;
                for(i=0; i<8; ++i){
                        nextX = x + xMoves[i];
                        nextY = y + yMoves[i];

                        if(isSafe(nextX, nextY, soln)){
                                soln[nextX][nextY] = moveNum;
                                if( generateMoves(nextX, nextY, moveNum+1, soln, xMoves, yMoves) ){
                                        return 1;
                                }
                                else{
                                        soln[nextX][nextY] = -1;
                                }
                        }
                }
                return 0;
        }
}

コードで長時間実行されているのは何ですか?

4

2 に答える 2

6

xMoves/yMoves を変更するとうまくいくようです: ideone。検索順序が原因で、解決策が早く見つかる可能性があります。

63、62、61 などの長さのツアーが多すぎて、最後の残りの正方形に到達できません。最悪の場合、ブルート フォース検索ではそれらすべてを調べなければなりません。うまくいったアルゴリズムは、解決につながる一連の動きを試すことで運が良かっただけです。

于 2012-07-28T14:01:14.813 に答える
1

あなたの投稿はあなたのコードと元のコードの違いを示していません。
実際、コードを注意深く見ると、自分のコードと正しいコードの間にあるのは次のようなものだけです。 

int xMoves[] = {  2, 1, -1, -2, -2, -1,  1,  2 };//{2, 2,  1,  1, -1, -1, -2, -2};  
int yMoves[] = {  1, 2,  2,  1, -1, -2, -2, -1 };//{1, -1, -2, 2, -2, 2, -1,  1};

順序が異なります。あなたは紙に可能な動きを描きます、そしてあなたはあなたが完全に無秩序である間、あなたは正しいものが反時計回りの順序を持​​っているのを見つけることができます。
それがあなたの問題を引き起こした理由であるに違いありません。

于 2012-07-28T16:30:42.830 に答える