廣度優先搜索：騎士覆蓋

Question

我試圖按照USACO算法培訓課程（http://ace.delos.com/usacogate） - 我目前在描述DFS，BFS等的頁面。我理解這些概念，但他們的示例問題他們給了BFS - 騎士封面 - 讓我感到困惑。以下是問題陳述：

在n×n棋盤上放置儘可能少的騎士，以便每個方格都受到攻擊。騎士不被視爲攻擊它所在的廣場。

這是BFS，頁面上顯示，因爲它試圖看看是否有與n騎士的解決方案試圖n+1騎士面前 - 這是相當清楚的。

但是，我不明白如何從這個單獨制定解決方案。有人可以幫我用這個僞代碼嗎？

非常感謝！

Answer 1

這是BFS，但你不搜索棋盤;搜索展示位置的空間：

初始狀態：沒有騎士被放置

有效舉措：發生在任何空閒的瓷磚騎士

目標狀態：所有的瓦片被佔據或攻擊

基本算法（BFS狀態空間）：

• 將初始狀態推送到BFS隊列。
• 雖然隊列中有東西：
  • 從隊列中移除一個狀態。
  • 對於每個未佔用的圖塊：
    • 創建當前狀態的副本。
    • 將一個騎士添加到該瓷磚。
    • 如果新狀態不存在於隊列中：
      • 如果新狀態是目標狀態，則結束。
      • 否則將其添加到隊列中。

請注意，我假設一個國家的所有路徑的長度是相同的。以這種方式查找一組展示位置時，情況確實如此，但通常情況並非如此。在情況不是這樣的情況下，您應該存儲所有訪問節點的集合，以避免重新訪問已探索的狀態。

---

您可能需要從左到右，從上到下添加騎士。那麼你不需要檢查隊列中的重複項。此外，如果您知道在不違反插入順序的情況下無法攻擊未貼磚，您可能會提前丟棄該狀態。

如果你不這樣做，並保留重複檢查，算法仍然會產生正確的結果，但它會做得慢得多。約40 000倍，大約（8！= 40 320是8騎士狀態的重複次數）。

---

如果您想要更快的算法，請查看A *。在這裏，一個可能的啓發是：

• 數unattacked和無人居住的瓷磚數量
• 除以計九，圍捕（騎士無法攻擊超過八個新磚或佔據不止一個）
• 距離（需要添加騎士的數量）不超過這個數字。

更好的啓發式會注意到騎士只能攻擊相同顏色的瓷磚並佔據相反顏色的瓷磚。這可能會稍微改善以前的啓發式（但仍可能有很大幫助）。

一個更好的啓發式應該能夠利用這樣的事實，騎士可以覆蓋不超過5x5平方的自由點。啓發式算法應該快速計算，但這可能有助於在有少量點覆蓋的情況下。

---

技術細節：

您可以表示每個國家作爲一個64位的位掩碼。雖然這需要一些按位操作，但確實有助於內存，並且64位數字的相等性檢查是快速。如果您無法使用64位數字，請使用兩個32位數字 - 這些數字應該可用。

圓陣列隊列效率很高，並且它不是那很難擴展其容量。如果你必須實現你自己的隊列，選擇這個。

Answer 2

這是C++中的一個實現。

它只是使用基本的蠻力，所以它只有直到n = 5。

#include <iostream> 
#include <vector> 
#include <queue> 

using namespace std; 

bool isFinal(vector<vector<bool> >& board, int n) 
{ 
    for(int i = 0; i < n; ++i) 
    { 
     for(int j = 0; j < n; ++j) 
     { 
      if(!board[i][j]) 
       return false; 
     } 
    } 
    return true; 
} 

void printBoard(vector<pair<int,int> > vec, int n) 
{ 
    vector<string> printIt(n); 
    for(int i = 0; i < n; ++i) 
    { 
     string s = ""; 
     for(int j = 0; j < n; ++j) 
     { 
      s += "."; 
     } 
     printIt[i] = s; 
    } 

    int m = vec.size(); 

    for(int i = 0; i < m; ++i) 
    { 
     printIt[vec[i].first][vec[i].second] = 'x'; 
    } 

    for(int i = 0; i < n; ++i) 
    { 
     cout << printIt[i] << endl; 
    } 
    cout << endl; 
} 

void updateBoard(vector<vector<bool> >& board, int i, int j, int n) 
{ 
    board[i][j] = true; 

    if(i-2 >= 0 && j+1 < n) 
     board[i-2][j+1] = true; 

    if(i-1 >= 0 && j+2 < n) 
     board[i-1][j+2] = true; 

    if(i+1 < n && j+2 < n) 
     board[i+1][j+2] = true; 

    if(i+2 < n && j+1 < n) 
     board[i+2][j+1] = true; 

    if(i-2 >= 0 && j-1 >= 0) 
     board[i-2][j-1] = true; 

    if(i-1 >= 0 && j-2 >= 0) 
     board[i-1][j-2] = true; 

    if(i+1 < n && j-2 >= 0) 
     board[i+1][j-2] = true; 

    if(i+2 < n && j-1 >= 0) 
     board[i+2][j-1] = true; 
} 

bool isThere(vector<pair<int,int> >& vec, vector<vector<pair<int,int> > >& setOfBoards, int len) 
{ 
    for(int i = 0; i < len; ++i) 
    { 
     if(setOfBoards[i] == vec) 
      return true; 
    } 
    return false; 
} 

int main() 
{ 
    int n; 
    cin >> n; 

    vector<vector<pair<int,int> > > setOfBoards; 
    int len = 0; 

    vector<vector<bool> > startingBoard(n); 
    for(int i = 0; i < n; ++i) 
    { 
     vector<bool> vec(n,0); 
     startingBoard[i] = vec; 
    } 

    vector<pair<int,int> > startingVec; 

    vector<vector<vector<vector<bool> > > > q1; 

    vector<vector<vector<pair<int,int> > > > q2; 

    vector<vector<vector<bool> > > sLayer1; 

    vector<vector<pair<int,int> > > sLayer2; 

    sLayer1.push_back(startingBoard); 

    sLayer2.push_back(startingVec); 

    q1.push_back(sLayer1); 

    q2.push_back(sLayer2); 

    int k = 0; 

    bool flag = false; 

    int count = 0; 

    while(!flag && !q1[k].empty()) 
    { 
     int m = q1[k].size(); 

     vector<vector<vector<bool> > > layer1; 

     vector<vector<pair<int,int> > > layer2; 

     q1.push_back(layer1); 

     q2.push_back(layer2); 

     for(int l = 0; l < m; ++l) 
     { 
      vector<vector<bool> > board = q1[k][l]; 

      vector<pair<int,int> > vec = q2[k][l]; 

      if(isFinal(board, n)) 
      { 
       while(l < m) 
       { 
        board = q1[k][l]; 
        vec = q2[k][l]; 

        if(isFinal(board, n)) 
        { 
         printBoard(vec, n); 

         ++count; 
        } 

        ++l; 
       } 

       flag = true; 
       break; 
      } 

      for(int i = 0; i < n; ++i) 
      { 
       for(int j = 0; j < n; ++j) 
       { 
        if(!board[i][j]) 
        { 
         pair<int,int> p; 
         p.first = i; 
         p.second = j; 

         vector<vector<bool> > newBoard = board; 

         vector<pair<int,int> > newVec = vec; 

         newVec.push_back(p); 

         updateBoard(newBoard, i, j, n); 

         sort(newVec.begin(), newVec.end()); 

         if(!isThere(newVec, setOfBoards, len)) 
         { 
          q1[k+1].push_back(newBoard); 
          q2[k+1].push_back(newVec); 

          setOfBoards.push_back(newVec); 
          ++len; 
         } 
        } 
       } 
      } 
     } 

     ++k; 
    } 

    cout << count << endl; 
}