文章/答案/技术大牛

发布

社区首页 >问答首页 >后跟踪皇后中的反射与对称性

问后跟踪皇后中的反射与对称性
EN

Stack Overflow用户

提问于 2014-11-24 08:04:32

回答 1查看 802关注 0票数 0

在介绍Anany Levition的算法设计和分析中，我阅读了有关回溯跟踪算法的文章。

以下是我所指的一页。

Yk&hl=en&sa=X&ei=OeNyVK-CE8fnuQTdnYCACw&ved=0CBwQ6AEwAA#v=onepage&q=there%20are%20several%20tricks%20that%20might%20reduce%20the%20size%20of%20state-space%20tree&f=false

在这里，作者已经提到如下。

有几个技巧可以帮助缩小状态空间树的大小。一种是利用组合问题中经常出现的对称性。例如，n皇后问题的板具有几个对称性，因此可以通过反射或旋转从另一些问题中得到一些解。这尤其意味着，我们不需要考虑第一皇后在最后一层(n/2)柱中的位置，因为第一皇后在正方形(1，i)、天花板(n/2)<=i <=n中的任何解都可以通过反射(哪一种？)第一皇后在正方形(1，n-i+1)中的解。这一观察使这棵树的大小减少了大约一半。

我对上述案文的问题如下：

作者利用组合问题中经常出现的对称性是什么意思？
作者在上述语境中的反思是什么意思？
在上面给出的例子中，作者的意思是：“我们不需要考虑在最后一层(n/2)列中放置第一皇后，因为第一皇后在平方(1，i)，上限(n/2)<=i <=n中的任何解，都可以通过与第一皇后在广场(1，n-i+1)中的解进行反射(哪种？)”？这里使用示例n=4请求。

n-queens

algorithm

backtracking

回答 1

Stack Overflow用户

发布于 2014-11-24 09:26:45

我将试着用一个简单的变体来回答这个问题，这是相同的皇后问题，但在4x4板上。

解决这个问题的一个可能办法是(1,2)，(2,4)，(3,1)，(4,3)

_  _  Q  _
Q  _  _  _ 
_  _  _  Q
_  Q  _  _

另一个解决办法是(2,1)，(4,2)，(1,3)，(4,3)：

_  Q  _  _
_  _  _  Q
Q  _  _  _
_  _  Q  _

然而，通过生成一个解决方案，我可以立即创建另一个，不需要继续搜索，只需遍历皇后的坐标。

同样的事情反过来又发生了。如果我发现没有以皇后(1,1), (2,1), (_,_), (_,_)开头的解决方案

Q  Q  _  _
_  _  _  _
_  _  _  _
_  _  _  _

我可以事先修剪所有从皇后(1,1),(1,2),(_,_),(_,_)开始的解决方案

Q  _  _  _
Q  _  _  _
_  _  _  _
_  _  _  _

使用这个问题的对称属性，每当我回溯和修剪一个不成功的分支时，我实际上也可以与他一起修剪其他的对称分支。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/27100286

复制

相似问题

问后跟踪皇后中的反射与对称性
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问后跟踪皇后中的反射与对称性EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问后跟踪皇后中的反射与对称性
EN