algorithm - 广度优先搜索: Knight cover

我正在尝试遵循USACO的算法培训类(class)(http://ace.delos.com/usacogate)-目前，我在介绍DFS，BFS等的页面上。我确实了解这些概念，但它们为BFS给出了示例问题-骑士保护套-让我感到困惑。这是问题陈述:



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

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

在此先感谢!

最佳答案

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

初始状态:未放置骑士

有效的行动:在任何空置的瓷砖上放置一个骑士

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

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

将初始状态推送到BFS队列。

队列中有内容时，

:

从队列中删除一个状态。

，用于每个未占用的图块:

创建当前状态的副本。

向该图块添加一个骑士。

(如果队列中不存在新状态):

如果新状态是目标状态，请完成。

else将其添加到队列中。

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

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

如果您不这样做，并且也保留重复检查，该算法仍会产生正确的结果，但是速度会慢得多。慢40000倍，大约是8骑士状态的重复次数(8!= 40320)。

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

计算未攻击和未占用的瓦片的数量

将计数除以九，四舍五入(一个骑士不能攻击八个以上的新方块或占据一个以上的方块)

距离(需要添加的骑士数)不超过此数字。

更好的启发法会注意到这样一个事实，即骑士只能攻击相同颜色的图块，并占据相反颜色的图块。这可能会稍微改善以前的启发式方法(但仍然有很大帮助)。

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

技术细节:

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

循环数组队列效率很高，并且扩展其容量并不难。如果必须实现自己的队列，请选择此队列。

关于algorithm - 广度优先搜索: Knight cover，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15038321/