1

最近、有名な小さな司教のアルゴリズムの問​​題を解決しようとしていました。私が読んだ Web サイトの 1 つで、チェス盤を黒と白の部分に分割して実行を最適化する必要があると書かれていました。その後、バックトラックを使用して、ビショップを黒い正方形と白い正方形に別々に配置する方法の数をカウントする必要があります。

次のコードでは、8 x 8 のチェス盤の白いマス目にのみ 6 人のビショップを配置しようとしています。テクニックが実際に機能していることを確認するためだけに行います。

//inside main function
int k = 6; //number of bishops
int n = 8; //length of one side of chessboard
Integer[] positions = new Integer[k];

long result = backtrack(positions, 0, n);

//find how many times we double counting each possible combination of bishops
int factor = 1;
for(int i = k; i>0; i--) {
    factor = factor * i;
}
System.out.println("The result is " + result/factor);


//implementation of other functions
public long backtrack(Integer[] prevPositions, int k, int n) {

    if(k == 6) {
        return 1;
    }
    long sum = 0;

    Integer[] candidates = new Integer[n*n];
    int length = getCandidates(prevPositions, k, candidates,  n);

    for(int i=0 ; i<length ; i++) {            
        prevPositions[k] = candidates[i];
        sum += backtrack(prevPositions,k+1,n);
    }

    return sum;
}

public Integer getCandidates(Integer[] prevPositions, int k, Integer[] candidates, int n) {
    int length = 0;
    //only white squares are considered as candidates, hence i+=2
    for (int i = 0; i < n*n; i+=2) {
        boolean isGood = true;
        int iRow = i / n;
        int iCol = i % n;

        for (int j = 0; j < k; j++) {
            int prev = prevPositions[j];
            if (i == prev) {
                isGood = false;
                break;
            } else {
                int prevRow = prev / n;
                int prevCol = prev % n;
                if (Math.abs(iRow - prevRow) == Math.abs(iCol - prevCol)) {
                    isGood = false;
                    break;
                }
            }
        }

        if(isGood) {
            candidates[length] = new Integer(i);
            length++;
        }
    }
    return length;
}

チェス盤を白と黒の四角に分割することで問題が最適化される理由はわかりますが、すべてのビショップを白の四角にのみ配置する方法を数えるには、まだ約 11 秒かかります。助けてくれませんか？私は何を間違っていますか？

4

1 に答える 1

4

検索を改善する方法をいくつか紹介します。

(1) 生成とテストの代わりに、すべてのビショップが可能な場所の「ドメイン」を持つ有限ドメイン検索を検討できます。ビショップを配置するたびに、残りのビショップのドメインを刈り込みます。ビショップのドメインが空になった場合、バックトラックする必要があります。

(2) 改良点として、配置するビショップが n 個あり、残り m < n の場合、バックトラックする必要があります。

(3) 動的プログラミング/メモ化を使用して、1 ビショップ、2 ビショップ、... のソリューションを保存し、n ビショップ ソリューションのセットから n + 1 ビショップ ソリューションのセットを計算します。

(4) 対称性を利用して検索スペースを削減します。この場合、(少なくとも) 黒/白の対称性と回転/反射の対称性があります。

(5) より良い表現を見つけようとする。たとえば、ビット パターン。

(6) 別の表現を使用する場合は、「トレイル」(Prolog を参照) を使用して、バックトラックで元に戻す必要がある操作を追跡することを検討してください。

乾杯！

于 2013-06-03T00:00:49.057 に答える