广度优先搜索: 骑士覆盖问题

Question

我想要跟随算法的USACO培训课程(http://ace.delos.com/usacogate)，目前我正在学习描述DFS、BFS等内容的页面。我确实理解这些概念，但是他们给出的BFS示例问题——骑士覆盖——让我感到困惑。以下是问题陈述：

在一个n x n的棋盘上放置尽可能少的骑士，使得每个方格都被攻击。不考虑骑士所在的方格。

页面说这是BFS，因为它在尝试n+1个骑士之前会先尝试n个骑士，这很清楚。

然而，仅凭这些信息我不知道如何构建解决方案。有人能帮我写一下伪代码吗？

非常感谢！

- ragebiswas

Answer 1

这是BFS算法，但你不搜索棋盘，而是搜索放置空间：

初始状态：没有骑士被放置

有效移动：将骑士放到任何未占用的方块上

目标状态：所有方块都被占用或受到攻击

基本算法（状态空间的BFS）：

- 将初始状态推入BFS队列。 - 当队列中有内容时： - 从队列中删除一个状态。 - 对于每个未占用的方块： - 创建当前状态的副本。 - 在该方块上添加一个骑士。 - 如果新状态不存在于队列中： - 如果新状态是目标状态，则完成。 - 否则将其添加到队列中。

请注意，我假设到达状态的所有路径长度相同。这在通过此方法寻找一组放置时是正确的，但一般情况下并不正确。在这种情况下，您应存储所有已访问节点的集合，以避免重新探索已经探索过的状态。

您可能需要按从左到右、从上到下的顺序添加骑士。然后您就不需要在队列中检查重复项。此外，如果您知道不能攻击未攻击的方块而不违反插入顺序，则可以尽早丢弃状态。

如果您不这样做并保留重复项检查，那么算法仍将产生正确的结果，但速度会慢得多。大约慢40,000倍（8！= 40,320是8个骑士状态的重复次数）。

如果您想要更快的算法，请看一看A*。这里，一种可能的启发式方法是：

- 计算未攻击和未占用方块的数量 - 将计数除以九并向上取整（一个骑士不能攻击超过八个新方块或占用超过一个方块） - 所需添加的骑士数量不超过此数字。

更好的启发式方法应该注意到一个骑士只能攻击相同颜色的方块，并占据相反颜色的方块。这可能会稍微改进先前的启发式方法（但仍然有可能大有帮助）。

更好的启发式方法应该能够利用骑士最多可以覆盖一个5x5的空间这一事实。启发式方法应该计算快速，但在需要覆盖较少的区域时可能会有所帮助。

技术细节：

您可以将每个状态表示为64位位掩码。虽然这需要一些按位操作，但它确实有助于内存，并且64位数字的相等性检查非常快。如果您不能拥有64位数字，请使用两个32位数字 - 这些应该是可用的。

循环数组队列非常高效，并且扩展容量也不是很困难。如果您必须实现自己的队列，请选择这个。

- John Dvorak

---

非常感谢你详细的回答，Jan。我会仔细阅读并尝试提出一个简单的实现。可能需要一些时间，因为我是新手 :) - ragebiswas

你是否有此的实现？我发现你的伪代码很难理解。 - Pavel

你的意思是“对于每个未被占用的方格”，我猜你只是把骑士放在棋盘的每个方格上，现在棋盘上到处都是骑士了...当然，现在每个方格都被占据或攻击了。 - Pavel

请注意，此时我们正在克隆棋盘，并将骑士添加到该副本中。每个副本只有一个骑士，原始棋盘被丢弃。如果您选择使用IDDFS而不是BFS，则这些副本可能不同时存在，但这只是一种实现细节。 - John Dvorak

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

- Aditya