反思和对称性后面跟踪皇后 [英] reflection and symmetry in back tracking queens
问题描述
我读到早在介绍跟踪算法设计和算法分析Anany Levition。
I am reading about Back tracking algorithms in Introduction to design and analysis of algorithms by Anany Levition.
下面是我指的页面
<一个href="http://books.google.co.in/books?id=mXA_r6mb-s8C&pg=PA399&lpg=PA399&dq=there+are+several+tricks+that+might+reduce+the+size+of+state-space+tree&source=bl&ots=hMb30M4m_2&sig=2ZIT49KTcztgBAVizbssfjYH_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" rel="nofollow">http://books.google.co.in/books?id=mXA_r6mb-s8C&pg=PA399&lpg=PA399&dq=there+are+several+tricks+that+might+reduce+the+size+of+state-space+tree&source=bl&ots=hMb30M4m_2&sig=2ZIT49KTcztgBAVizbssfjYH_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
下面笔者提及如下图所示。
Here author has mentioned as below.
有一些技巧，可以帮助减少状态空间树的大小。一是利用对称性常常美元的组合问题p $ psent。例如，在n皇后问题的板具有几个对称性，使得一些soluctions可以从他人通过反射或旋转来获得。这意味着，特别是，我们不需要考虑的第一个皇后的安置在顶楼（N / 2）列，因为在广场第一皇后（1，I），天顶（N / 2） - 的任何解决方案; = I＆其中; = n时，也可以从与正方形的第女王的溶液反射（？其中）获得（1，正 - I + 1）。这一观察切割树的大小约一半。
There are several tricks that might help reduce the size of a state-space tree. One is to exploit the symmetry often present in combinational problems. For example, the board of the n-queens problem has several symmetries so that some soluctions can be obtained from others by reflection or rotation. This implies, in particular, that we need not consider placements of the first queen in the last floor(n/2) columns, because any solution with the first queen in square (1,i), celing(n/2)<= i <=n, can be obtained by reflection (which?) from a solution with the first queen in square(1, n-i+1). This observation cuts the size of the tree by about half.
我在上面的文字问题是
-
什么是笔者所说的利用对称性常常present的组合问题？
What does author mean by exploit the symmetry often present in combinational problems?
什么是笔者通过反射在上述背景下是什么意思？
What does author mean by reflection in above context?
3.In上面的例子是什么笔者通过下面的语句的意思是我们不需要考虑的第一个女王在顶楼（N / 2）列配股，鉴于因与方第一皇后（1任何解决方案，我），天顶（N / 2）＆其中; = I＆其中; = n时，可通过反射而获得（该）从用方（1第一女王的溶液中，n-i + 1的）？ 在这里，请求与例如N = 4。
3.In example given above what does author mean by following statement "we need not consider placements of the first queen in the last floor(n/2) columns, because any solution with the first queen in square (1,i), celing(n/2)<= i <=n, can be obtained by reflection (which?) from a solution with the first queen in square(1, n-i+1)" ? Here request with example n=4.
感谢您的时间和帮助。
推荐答案
我会尝试的例子对这个问题的简单变化来回答，这是相同的皇后问题，但在4×4板。
I will try to answer by example on a simplified variation of the problem, it's the same queens problem but on 4x4 board.
一种可能的解决问题的方法是（1,2），（2,4），（3,1），（4,3）
One possible solution to the problem is (1,2), (2,4), (3,1),(4,3)
_ _ Q _
Q _ _ _
_ _ _ Q
_ Q _ _
另一种解决方案是（2,1），（4,2），（1,3），（4,3）：
Another solution is (2,1), (4,2), (1,3), (4,3):
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
不过，通过产生一个解决方案，我可以立即创建其他的，没有必要继续在搜索，通过简单地穿越女王的坐标。
However, by generating one solution, I could immediately create the other, no need to keep on searching, by simply traversing the coordinates of queen.
同样的事情会发生在其他方式来。如果我发现有任何解决方案，与皇后（1,1）开始，（2,1），（_，_）（_，_）
The same thing goes the other way around to. If I found that there is no solution that starts with the queens (1,1), (2,1), (_,_), (_,_)
Q Q _ _
_ _ _ _
_ _ _ _
_ _ _ _
我可以修剪事先也都启动与皇后（1,1）的解决方案，（1,2），（_，_）（_，_）：
Q _ _ _
Q _ _ _
_ _ _ _
_ _ _ _
使用此问题的对称特征，每当我走回头路，修剪不成功的分支，其实我可以修剪等对称的分支与他。
Using symetrical attributes of this problem, whenever I backtrack and trim an unsuccesful branch, I can actually trim other symetrical branches with him as well.
这篇关于反思和对称性后面跟踪皇后的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
