L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
在一个NxN的棋盘上放N个皇后，使其不能互相攻击这种老套的题目咱不出，咱出个新的。
在一个NxN的棋盘上最少放几个皇后，才能控制整个棋盘。N可能很大很大。
在一个NxN的棋盘上最少放几个皇后，才能控制整个棋盘。N可能很大很大。
您正在使用一款已经过时的浏览器！部分功能不能正常使用。
请尝试升级或使用 其他浏览器。
请尝试升级或使用 其他浏览器。
L
lhlh_0_0
Unregistered / Unconfirmed
GUEST, unregistred user!
把题目说的再明确一点，什么是能控制。
L
leilu
Unregistered / Unconfirmed
GUEST, unregistred user!
说的 具体些！
D
DouZheng
Unregistered / Unconfirmed
GUEST, unregistred user!
3*3 1个皇后
_______
|_|_|_|
|_|=|_|
|_|_|_|
4*4 2个皇后
_________
|_|_|_|_|
|_|=|_|_|
|_|_|_|_|
|_|_|_|=|
太难了。
_______
|_|_|_|
|_|=|_|
|_|_|_|
4*4 2个皇后
_________
|_|_|_|_|
|_|=|_|_|
|_|_|_|_|
|_|_|_|=|
太难了。
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
能控制意味着对于棋盘上任意一格，要么被一个皇后占者，要么可以被一个或多个皇后攻击到。
L
lichdr
Unregistered / Unconfirmed
GUEST, unregistred user!
好象在１/２左右，
３－－１
４－－２
５－－３
６－－３
７－－４
８－－５
９－－５
１０－－５
１１－－５
１２－－６
１３－－７
只到这里了。１４实在没耐心运行了。
随Ｎ的增长，其运算量是飞速的上升。
我现在的程序还没加外套（Ｎ与Ｍ我现在是直接用ＣＯＮＳＴ定死的，然后手动调Ｍ的值）
我现在用一个longword来表示棋盘的每一行（现在很多高位都没用到，我是直接填１的）
一种摆法实际上就是一个组合（在Ｎ＊Ｎ里选Ｍ的组合）
刚开始时我是扫描全组合的，只能到１０。１１的话就要超过１分钟才能出来（ＣＩＩ９００,２４６Ｍ）。
因为一行内不可能出现两个皇后，所以我把那些密的组合排除掉。而且第一个后也不太可能出现在第３行（出现在第２行也只是在Ｎ＝１１的时候，大多时候在第１行就会出现后，要么就无解）。最后一行也没有出现后。经过这些调整也只是到１３
很多的后都是要隔一行才会出现的，这里应该也能排除掉一些。它们列之间的情况还没有去深入的研究过。
现在还是有很大的一个问题，整个的运算都是在这里。我现在每一种组合出来，每一个后都去杀棋盘上的点，然后判断是否所有的点都已被杀。所以Ｎ，Ｍ一大就算得特别慢。
看来要另辟奚径。
３－－１
４－－２
５－－３
６－－３
７－－４
８－－５
９－－５
１０－－５
１１－－５
１２－－６
１３－－７
只到这里了。１４实在没耐心运行了。
随Ｎ的增长，其运算量是飞速的上升。
我现在的程序还没加外套（Ｎ与Ｍ我现在是直接用ＣＯＮＳＴ定死的，然后手动调Ｍ的值）
我现在用一个longword来表示棋盘的每一行（现在很多高位都没用到，我是直接填１的）
一种摆法实际上就是一个组合（在Ｎ＊Ｎ里选Ｍ的组合）
刚开始时我是扫描全组合的，只能到１０。１１的话就要超过１分钟才能出来（ＣＩＩ９００,２４６Ｍ）。
因为一行内不可能出现两个皇后，所以我把那些密的组合排除掉。而且第一个后也不太可能出现在第３行（出现在第２行也只是在Ｎ＝１１的时候，大多时候在第１行就会出现后，要么就无解）。最后一行也没有出现后。经过这些调整也只是到１３
很多的后都是要隔一行才会出现的，这里应该也能排除掉一些。它们列之间的情况还没有去深入的研究过。
现在还是有很大的一个问题，整个的运算都是在这里。我现在每一种组合出来，每一个后都去杀棋盘上的点，然后判断是否所有的点都已被杀。所以Ｎ，Ｍ一大就算得特别慢。
看来要另辟奚径。
C
chnplzh
Unregistered / Unconfirmed
GUEST, unregistred user!
不会吧，老大也开始研究这样的算法题目，难道要参加什么考试？？？？？
B
beta
Unregistered / Unconfirmed
GUEST, unregistred user!
这问题 creation-zy 兄肯定有兴趣研究：）
L
lichdr
Unregistered / Unconfirmed
GUEST, unregistred user!
什么呀
老大是散分来的。不过他出的题目都有点难。要不是这几天没什么事。还真不会去动它。
老大是散分来的。不过他出的题目都有点难。要不是这几天没什么事。还真不会去动它。
5
52free
Unregistered / Unconfirmed
GUEST, unregistred user!
这个很难
我搞了快二个小时了
没搞出来
看起来好像是N皇后的逆推,就是找到放置皇后最小的不能构建完N+1层状态树的叶子结点
但它又可以从第二行开始建树,真头疼
看看高手来解决,我来等......
leechange老兄,你这不是折磨人吗???55555
我搞了快二个小时了
没搞出来
看起来好像是N皇后的逆推,就是找到放置皇后最小的不能构建完N+1层状态树的叶子结点
但它又可以从第二行开始建树,真头疼
看看高手来解决,我来等......
leechange老兄,你这不是折磨人吗???55555
A
AI_Player
Unregistered / Unconfirmed
GUEST, unregistred user!
只能剪枝搜索
L
lichdr
Unregistered / Unconfirmed
GUEST, unregistred user!
根據棋盤的對稱性，既然沒有同行的，就沒有同列的
我把同列的排除掉，速度方面沒有什麼改善，組合還是相當的多。
同樣根據對稱性，第一個棋子在棋盤的右半部也可以不用搜了。
所以第一個棋子在前兩行的左部會出現，如果沒出現的話就無解了。
第二個，第三個。。。。，有待研究。
棋盤的對稱：轉90,180,270。還有手性對稱(上下向與左右向)
我把同列的排除掉，速度方面沒有什麼改善，組合還是相當的多。
同樣根據對稱性，第一個棋子在棋盤的右半部也可以不用搜了。
所以第一個棋子在前兩行的左部會出現，如果沒出現的話就無解了。
第二個，第三個。。。。，有待研究。
棋盤的對稱：轉90,180,270。還有手性對稱(上下向與左右向)
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
呵呵，剪枝搜索当然是可以的，但效率成问题。
给个提示吧：这题的数学原型叫最小支配集。（N皇后问题叫最大独立集）
给个提示吧：这题的数学原型叫最小支配集。（N皇后问题叫最大独立集）
L
lichdr
Unregistered / Unconfirmed
GUEST, unregistred user!
查了一下：
顶点集D是图G=(V，E)的支配集当且仅当对任意u∈V-D存在v∈D使(u，v)∈E.最小支配集问题是对给定图G找出使|D|最小的支配集D.
又是圖論的問題。意思是懂了。但如何用程序實現，實在是所學有限。
這幾天比較忙，先撤了。
顶点集D是图G=(V，E)的支配集当且仅当对任意u∈V-D存在v∈D使(u，v)∈E.最小支配集问题是对给定图G找出使|D|最小的支配集D.
又是圖論的問題。意思是懂了。但如何用程序實現，實在是所學有限。
這幾天比較忙，先撤了。
大
大大翁
Unregistered / Unconfirmed
GUEST, unregistred user!
江山易改，本性难移！
呵呵，兄弟，你的老毛病又做怪了，
不过解这类题我有经验了，
一、找出内在的规律性，
二、运用数学理论
三、理论用程序实现
呵呵，兄弟，你的老毛病又做怪了，
不过解这类题我有经验了，
一、找出内在的规律性，
二、运用数学理论
三、理论用程序实现
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
其实，算法都是前人总结出来的，是死的，了解了就会编程序。关键是运用，要善于把实际问题同抽象的算法联系起来才行。
就拿这题来说吧，lichdr对最小支配集的定义是正确的，我现在把题目改一下，如何把原题的具体问题联系到最小支配集的定义上去。分值也是300。
就拿这题来说吧，lichdr对最小支配集的定义是正确的，我现在把题目改一下，如何把原题的具体问题联系到最小支配集的定义上去。分值也是300。
L
lichdr
Unregistered / Unconfirmed
GUEST, unregistred user!
本來不想進來了，不過老大既然要解釋一下那就解釋一下了。
這個棋盤就是一個圖，每個位置就是一個點，同行，同列，同斜線上的點之間有一條邊。
問題就是找出一個集合，集合外的任意一點都有一條邊通到這個集合中的某個點。
集合的元素最小的就是了。
主要是沒學過圖論，實在不知道這個支配集是如何求的。上面那個定義我也是翻箱倒櫃找出來的。
這個棋盤就是一個圖，每個位置就是一個點，同行，同列，同斜線上的點之間有一條邊。
問題就是找出一個集合，集合外的任意一點都有一條邊通到這個集合中的某個點。
集合的元素最小的就是了。
主要是沒學過圖論，實在不知道這個支配集是如何求的。上面那個定義我也是翻箱倒櫃找出來的。
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
lichdr的分析是对的，分析到这一步这题就差不多做完了，真正求一个图的最小支配集是有死公式的，时间复杂度大约是O(n^2)，所以n比较大也吓唬不了人。
M
minkerui
Unregistered / Unconfirmed
GUEST, unregistred user!
图的最小支配集O(N^2)，不可能吧，有不是特殊图（二部图）。
LRJ说的一个方法N＝50就差不多了
LRJ说的一个方法N＝50就差不多了
Q
QSmile
Unregistered / Unconfirmed
GUEST, unregistred user!
看看
Similar threads
- 回复
- 4
- 查看
- 4K