rag*_*was 5 algorithm breadth-first-search
我正在尝试关注USACO算法培训课程(http://ace.delos.com/usacogate) - 我目前正处于描述DFS,BFS等的页面.我确实理解这些概念,但样本问题他们给了BFS - 骑士封面 - 让我感到困惑.这是问题陈述:
在nxn棋盘上放置尽可能少的骑士,以便每个方格都受到攻击.骑士不被认为攻击它所在的广场.
该页面说,这是BFS,因为它试图n在尝试n+1骑士之前看看是否有骑士的解决方案- 这很清楚.
但是,我不明白如何单独制定解决方案.有人可以用这个伪代码帮我吗？
非常感谢!
它是BFS,但你不搜索棋盘; 搜索展示位置的空间:
初始状态:没有骑士
有效移动:将骑士放在任何未占用的牌上
目标状态:所有瓷砖都被占用或受到攻击
基本算法(状态空间的BFS):
请注意,我假设状态的所有路径长度相同.在以这种方式查找一组展示位置时,情况确实如此,但一般情况下并非如此.如果不是这样,您应该存储所有访问过的节点集,以避免重新访问已经探索过的状态.
您可能需要从左到右,从上到下添加骑士.然后,您不需要检查队列中的重复项.此外,如果您知道在不违反插入顺序的情况下无法攻击未攻击的磁贴,您可以提前放弃状态.
如果你不这样做并保留重复检查,算法仍然会产生正确的结果,但它会慢得多.大约慢40 000倍(8!= 40 320是8骑士状态的副本数量).
如果您想要更快的算法,请查看A*.在这里,一种可能的启发式方法是:
一个更好的启发式方法会注意到一个骑士只能攻击相同颜色的瓷砖并占据相反颜色的瓷砖这一事实.这可能会稍微改善先前的启发式(但仍然可能有很大帮助).
一个更好的启发式应该能够利用骑士可以覆盖不超过5x5平方的自由点的事实.启发式算法应该计算速度很快,但这可能有助于覆盖很少的点.
技术细节:
您可以将每个状态表示为64位位掩码.虽然这需要一些按位操作,但它确实有助于内存,并且64位数字的相等检查很快.如果您不能使用64位数字,请使用两个32位数字 - 这些数字应该可用.
圆阵队列是有效的,这不是说很难扩大产能.如果您必须实现自己的队列,请选择此队列.