广度优先搜索：骑士覆盖

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; 
}