algorithm - 广度优先搜索 : Knight cover

Question

我正在尝试学习 USACO 算法培训类(class) (http://ace.delos.com/usacogate) - 我目前正在访问一个描述 DFS、BFS 等的页面。我理解这些概念，但是他们给出的示例问题BFS - 骑士封面 - 让我感到困惑。这是问题陈述:

Place as few knights as possible on an n x n chess board so that every square is attacked. A knight is not considered to attack the square on which it sits.

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

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

提前致谢!

Answer 1

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

初始状态:没有放置骑士

有效的移动:在任何未被占据的方格上放置一个骑士

目标状态:所有方 block 要么被占领要么被攻击

基本算法(状态空间的BFS):

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

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

---

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

如果您不这样做并保留重复检查，该算法仍会产生正确的结果，但速度会慢很多。慢 40 000 倍，大约(8!=40 320 是 8 马状态的重复数)。

---

如果您想要更快的算法，请研究 A*。在这里，一种可能的启发式是:

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

更好的启发式会注意到一个事实，即马只能攻击相同颜色的方 block ，并占据相反颜色的方 block 。这可能会略微改进之前的启发式方法(但仍然可能有很大帮助)。

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

---

技术细节:

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

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