5

我正在尝试学习 USACO 算法培训课程（http://ace.delos.com/usacogate）——我目前在一个描述 DFS、BFS 等的页面上。我确实理解这些概念，但是示例问题他们为 BFS - 骑士封面 - 让我感到困惑。这是问题陈述：

在 nxn 棋盘上放置尽可能少的骑士，以便每个方格都受到攻击。骑士不被视为攻击它所在的方格。

n这是 BFS，页面说，因为它试图在尝试骑士之前查看骑士是否有解决方案n+1- 这很清楚。

但是，我不明白如何仅凭此制定解决方案。有人可以帮我用伪代码吗？

提前非常感谢！

4

2 回答 2

7

它是 BFS，但你不搜索棋盘；搜索展示位置空间：

初始状态：未放置骑士

有效移动：在任何未占用的瓷砖上放置一个骑士

目标状态：所有图块都被占领或被攻击

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

  • 将初始状态推送到 BFS 队列。
  • 当队列中有东西时：
    • 从队列中删除一个状态。
    • 对于每个未占用的瓷砖：
      • 创建当前状态的副本。
      • 将一名骑士添加到该图块。
      • 如果队列中不存在新状态：
        • 如果新状态是目标状态，则结束。
        • 否则将其添加到队列中。

请注意，我假设一个状态的所有路径都具有相同的长度。以这种方式查找一组展示位置时确实如此，但一般情况下并非如此。如果情况并非如此，您应该存储所有访问过的节点的集合以避免重新访问已经探索过的状态。

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

如果您不这样做并留下重复检查，算法仍然会产生正确的结果，但它会慢得多。大约慢 40 000 倍（8！=40 320 是 8 骑士状态的重复数）。

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

  • 计算未攻击和未占用的瓷砖数量
  • 将计数除以九，四舍五入（骑士不能攻击超过八个新瓷砖或占据超过一个）
  • 距离（需要添加的骑士数量）不超过这个数字。

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

更好的启发式应该能够利用骑士可以覆盖不超过 5x5 方格的空闲点这一事实。启发式算法应该计算得很快，但是当需要覆盖的地方很少时，这可能会有所帮助。

技术细节：

您可以将每个状态表示为 64 位位掩码。虽然这需要一些按位操作，但它确实有助于记忆，并且 64 位数字的相等检查速度很快。如果您没有 64 位数字，请使用两个 32 位数字 - 这些应该可用。

循环数组队列效率高，扩容也不难。如果您必须实现自己的队列，请选择这个。

于 2013-02-23T08:19:54.200 回答
1

这是 C++ 中的一个实现。

它只是使用基本的蛮力，所以它只适用于 until 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;
}
于 2014-05-27T16:52:20.737 回答