标题: 跳马遍历问题 [打印本页]
作者:
天痕 时间: 2005-1-12 08:52
不论先后：
做出1得300
做出2得1000
1：跳马问题
国际象棋盘上某点上有一马，让马遍历整个棋盘没有重复。
输入：马的位置（I，J）（1〈=I〈=8；1〈=J〈=8）
输出：跳法（给棋盘标号）
2：还是跳马问题
在1的基础上按跳的顺序给棋盘上的点编号，最后要求跳出个8阶幻方来
输入：马的位置（I，J）（1〈=I〈=8；1〈=J〈=8）
输出：跳法（给棋盘标号）
时限：20s
参加者以附件形式提交程序
谨以第二题纪念逝者~~
作者:
loranrowe 时间: 2005-1-12 09:30
原帖由天痕于2005-01-12, 8:52:06发表
不论先后：
做出1得500
做出2得1000
1：跳马问题
国际象棋盘上某点上有一马，让马遍历整个棋盘没有重复。
输入：马的位置（I，J）（1〈=I〈=8；1〈=J〈=8）
输出：跳法（给棋盘标号）
2：还是跳马问题
在1的基础上按跳的顺序给棋盘上的点编号，最后要求跳出个8阶幻方来
输入：马的位置（I，J）（1〈=I〈=8；1〈=J〈=8）
输出：跳法（给棋盘标号）
时限：20s
谨以第二题纪念逝者~~
第一个的代码等一下贴
幻方是指横竖斜的和都相等？
斜仅指主对角线吧？
作者:
天痕 时间: 2005-1-12 09:33
幻方是指横竖斜的和都相等？
斜仅指主对角线吧？
是的
第一个纯粹送钱，第二个有时间限制的才有意义。
第一题奖金改少了，不过既然你先发帖了你的就不变吧~~
作者:
天痕 时间: 2005-1-12 09:41
我先去睡觉
6小时后回来查收
本题1截止于北京时间1月15日零点
题2不设截止时间
作者:
loranrowe 时间: 2005-1-12 09:50
现已证明：互不同构的八阶幻方至少存在12 631 127 040组。（这个数字我没考证过）
这版程序每秒只能搜索400k步左右，显然构造所有幻方的想法是不成立了
只能通过检验knight tour的solution来解决了
假设solution的平均搜索步数为40k，20s只能有200个可行解
考虑java的效率问题，改编为c++，最多也只有2000个可行解
看来还得优化程序啊
附件:
knighttour.rar (2005-1-12 09:50, 2.94 K) / 该附件被下载次数 228
http://xycq.org.cn/forum/attachment.php?aid=3396
作者:
天宫公主 时间: 2005-1-12 10:04
题目和我上大一时的一个家庭作业一样，我用的是C＋＋，最后算了一夜才出来的。就说当时的电脑还都是奔3一类的，可20秒也忒短的点吧？
作者:
kulaog 时间: 2005-1-12 14:46
先算出第一题。
第二题只要判断是不是八阶幻方就可以拉，还需要知道“互不同构的八阶幻方至少存在12 631 127 040组”有什么用啊。
现在手懒，做不动，提个小建议。
作者:
loranrowe 时间: 2005-1-12 14:58
原帖由kulaog于2005-01-12, 14:46:56发表
先算出第一题。
第二题只要判断是不是八阶幻方就可以拉，还需要知道“互不同构的八阶幻方至少存在12 631 127 040组”有什么用啊。
现在手懒，做不动，提个小建议。
单纯优化跳马问题，可以将解决时间降到毫秒级
可是想要单纯搜索某点所有跳马问题的解，找出其中八阶幻方的解
或者搜索所有某点为1的不同构的八阶幻方，从中找出跳马问题的解
估计时间在小时级
除非找到一个好的解发生算法，能够兼顾两个问题的求解
作者:
kulaog 时间: 2005-1-12 15:05
先算出第一题，放到内存里面，数量就是有限的，然后判断每一种跳法是不是八阶幻方就可以啦，事情就是一步一步做的啊。为什么要一口吃成胖子啊。
8+8+2=18，只要12次加法就可以算出这种跳发是不是八阶幻方，12*n步，也不多阿。应该比第一个还快啊。
作者:
kulaog 时间: 2005-1-12 16:28
只要检验结果是不是八阶幻方，谁要你算出八阶幻方又多少可能啦。
就好像给你10组数字，每组2个数字，问你那组数字加起来等于0。
而你却要求出所有加起来等于0的2个数字，这个也没有解啊。
关键在于是检验不是求解。
作者:
天痕 时间: 2005-1-13 04:27
loranrowe第一题正确！
loranrowe 2005-01-13 ￥ 500 轩辕通宝
不过建议用C++来，JAVA的速度实在不敢恭惟啊~~
loranrowe能不能把“改进的启发式算法求得可行解的平均步数为73”说详细一点？这个我好像不知道
作者:
loranrowe 时间: 2005-1-13 09:19
原帖由天痕于2005-01-13, 4:27:55发表
“改进的启发式算法求得可行解的平均步数为73”
其实就是用了la Warnsdorff矩阵，这个矩阵记录了棋盘各点的度数
这个是初始矩阵
2,3,4,4,4,4,3,2
3,4,6,6,6,6,4,3
4,6,8,8,8,8,6,4
4,6,8,8,8,8,6,4
4,6,8,8,8,8,6,4
4,6,8,8,8,8,6,4
3,4,6,6,6,6,4,3
2,3,4,4,4,4,3,2
每走一步，将相关点的度数减1
每步尽量先走度数小的点
度数相等的点边角优先
还有其他一些规则
据Dr. Gerald Wildenberg的文章说
在这种原则下，以棋盘上的各点为起始点，求得第一个解的平均搜索步数为73
不过我很怀疑他提供的数据，因为他竟然有两个点fail了，就是在10M步中没有找到解
ps：
第一个题用java语言是因为那是以前做的作业题...
从硬盘上翻出来就提交了
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |