1

NQueen 問題はバックトラッキングの有名な例です。ソースから読んだ後、以下のコードスニペットを試しました。

int isSafe(int k,int i,int *x)
{
    int j;
    for(j=0;j<k;j++)
    {
              //old queen is placed at jth row of x[j] column
              //new queen to be placed at kth row of ith column
            if(i==x[j] || abs(k-j)==abs(i-x[j]))
                    return 0;
    }
    return 1;
}

int Nqueen(int k, int* sol, int N)
{
    int col;
    if( k == N )
    {
            printSol(sol,N);
            return 1;
    }
    else
    {
            for(col = 1;col <= N; col++)  //determines appropriate column number of the kth queen to be placed
            {
                    if( isSafe(k,col,sol) )
                    {
                            sol[k] = col;
                            if( Nqueen(k+1, sol, N) )
                                    return 1;
                            sol[k] = 0; // backtrack
                    }
            }
            return 0; // solution not possible
    }
}

私は次のように出力を得ています： 

1 5 8 6 3 7 2 4

ただし、バックトラックするステートメントにコメントすると、問題なく同じ出力が得られます。

int Nqueen(int k, int* sol, int N)
{
    int col;
    if( k == N )
    {
            printSol(sol,N);
            return 1;
    }
    else
    {
            for(col = 1;col <= N; col++)  //determines appropriate column number of the kth queen to be placed
            {
                    if( isSafe(k,col,sol) )
                    {
                            sol[k] = col;
                            if( Nqueen(k+1, sol, N) )
                                    return 1;
                            // sol[k] = 0; <-------------- Notice this change
                    }
            }
            return 0;
    }
}

NQueenの問題、バックトラッキングの問題を引き起こしたのは正確には何ですか?

単純な再帰的アプローチではありませんか？

4

3 に答える 3

6

はsol[k] = 0後戻り部分ではありません。バックトラッキングは再帰呼び出しで行われます: if( Nqueen(k+1, sol, N) ).

バックトラックの考え方は、徹底的な検索です。1 つが見つかるまで、すべての可能性を検索しようとします。ここでは、ボード内のクイーンのすべての可能な割り当てを試しており、それでも安全な場合は「続行」します。安全でないことがわかった場合は、失敗して再帰から戻り、次のオプションを試します。

コメントアウトされた行は、解決策が見つからない場合、結果の配列が[0,...,0]であり、意味のない配列ではないことを確認するだけだと思います。

于 2012-08-22T10:06:44.360 に答える
1

バックトラッキング問題は、考えられるすべての組み合わせを試すプログラミング パラダイムです。次に、すべての組み合わせについて、これまでの組み合わせが正しいかどうかを確認します。以下は、N (または 8) クイーン問題のいくつかの手順です。

  1. 行 0 から開始し、最初のクイーンを列 0 に配置します。
  2. 行 1 と列 0 に 2 番目のクイーンを配置します。
  3. 位置が安全かどうかを確認する
  4. 安全でない場合は、2 番目のクイーンを行 1、列 1 に配置します。
  5. 安全ではありません。2 番目のクイーンを行 1、列 2 に配置します。

それぞれの可能なすべての列にクイーンを配置し、それが安全かどうかを確認することにより、このように進めます。2 つのクイーンを同じ列に配置しないなどの明らかな偽の条件を省略できます。以下は、8 クイーン問題のコードで、考えられるすべての解決策を出力しています。

#include<stdio.h>


int abs(int a){
        return a>0? a : -a;
}

int isSafe(int col[],int row){
        int row2,col2,i,yDiff,xDiff;
                if(row == 0) return 1;


    for(row2=0;row2<row;row2++){
                    if(col[row2] == col[row])
                            return 0;

                    xDiff = col[row2] - col[row];
                    xDiff = abs(xDiff);
                    yDiff = row - row2;
                    if(xDiff == yDiff)
                                    return 0;
            }

    return 1;

}

int Nqueen(int col[],int n, int row){
        int i;
        if(row==n){
                printf("\n");
                for(i=0;i<n;i++)
                        printf("%d ",col[i]+1);

        }else{
                for(i=0;i<n;i++){
                    col[row] = i;
                    if(isSafe(col,row)){
                            queen(col,n,row+1);
                    }

            }
    }

}

int main(){
        int col[8];
        queen(col,8,0);

}
于 2012-08-24T07:12:14.373 に答える
0

まず、アルゴリズムを本当に理解する必要があります (これにより、コメントアウトしても問題ないことがわかります)。お気づきのように、このアルゴリズムは再帰的です。あなたのせいで後戻りしている

  • k 番目のクイーンを位置に設定する
  • クイーン k+1、k+2、... の可能な配置を調べます。
  • 次に、k 番目のクイーンに戻り、別の場所に配置し、繰り返します。

ステップ 3 で、k 番目のクイーンに「戻ります」。これが、バックトラッキングと呼ばれる理由を説明する方法です。

于 2012-08-22T10:09:09.047 に答える