回溯優化

Question

最近我試圖解決着名的little bishops算法問題。在我閱讀的其中一個網站中，我應該將棋盤分成黑白部分以優化執行。之後，我應該使用回溯來統計可能的方法，以便將主教分成黑色方塊和白色方塊。

在下面的代碼中，我嘗試將6個主教放在8乘8棋盤的白色方塊上。我這樣做只是爲了驗證技術是否真的有效。

//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秒計數可能的方式把所有的主教只白色方塊數。你能幫我嗎？我究竟做錯了什麼？

Answer 1

這裏有幾個方法來改善您的搜索。

（1）您可以考慮有限域搜索，而不是生成和測試，其中每個主教都有可能位置的「域」。每當你放置一位主教時，你就會修剪剩餘主教的領域。如果主教的域名變空了，你必須回溯。 （2）作爲一種改進，如果你有n個主教可以放置，並且還有其他個地方，你必須回溯。 （3）使用動態編程/記憶，其中存儲1主教，2主教，...的解決方案，並計算n組主體解決方案中n + 1主教解決方案的集合。

（4）利用對稱來減少您的搜索空間。在這種情況下，（至少）有黑/白對稱性和旋轉/反射對稱性。

（5）試着找到一個更好的表示。例如，位模式。 （6）如果使用不同的表示法，請使用「trail」（比較Prolog）來跟蹤在回溯時需要撤銷的操作。

乾杯！