学海网

课程设计 平方数幻方问题及算法设计(附答辨课件,正文共38页,19078字)
摘要
幻方问题是具有悠久历史的复杂排列组合问题。从十七世纪开始，人们对幻方的构造与性质展开比较严肃的数学思考。十九世纪晚期以后，数学家将幻方用于概率论及数学分析。现代计算机的高速发展，成了幻方研究的有力工具。但是，幻方问题是一个典型的NP难题，由于问题的复杂性，至今仍有很多未解决的难题和不解之谜。
本文介绍用组合数的方法来搜索求解平方数幻方的过程。把n阶平方数幻方的构造过程看成是对n2个连续自然数的可能排列空间的一个搜索过程。为提高算法的效率，我们对构造平方数幻方问题的搜索次序进行了研究，采用按行、对角及列分步演化的混合算法，使行、对角线及列的幻和与平方幻和快速得到满足，该算法的效率明显优于行、列及对角线同步的演化算法和先行列后对角线的演化算法。
穷举法和贪婪法等传统的算法只能解决阶数较小计算量较少的小规模问题，而对于计算量较大的问题往往不能在有限的时间内获得满意的结果。本文提供了一种计算机搜索算法，该算法能够在比较短的时间内获得阶数较大的平方数幻方。
关键词：幻方；平方数幻方；幻和；组合数
目录
摘要 I
ABSTRACT II
目录 III
1 绪论 1
1.1 研究内容与研究方法 1
1.2 研究目的与意义 1
1.3 国内外研究现状 2
1.4 本文结构 5
2 幻方介绍 6
2.1 幻方的定义 6
2.2 幻方理论发展概况 7
2.3 幻方的应用 7
2.3.1 缺陷幻方填充问题 7
2.3.2 幻方模和问题 8
2.3.3 完美置换问题 8
2.3.4 幻方洗牌原理 9
2.3.5 互补缺陷矩阵洗牌与恢复 10
2.4 本章小结 11
3 幻方的构造 11
3.1 幻方构造问题分析 12
3.2 幻方的系统性 12
3.2.1 系统的多元性 12
3.2.2 系统的相关性 12
3.2.3 系统的整体性 13
3.3 构造幻方的计算复杂性 13
3.4 常见的幻方构造方法 14
3.4.1 穿心对调法 14
3.4.2 马步法 14
3.4.3 递归构造n阶幻方(n≥5) 15
3.4.4 n阶幻方构造mn阶幻方 16
3.4.5 偶数阶幻方构造法 16
3.5 本章小结 17
4 构造平方数幻方 18
4.1 行、列及对角线同时搜索与演化算法 18
4.1.1 编码表示 18
4.1.2 目标函数 18
4.1.3 变异操作 19
4.1.4 算法基本步骤 19
4.2 先行列后对角线搜索与演化算法 19
4.2.1 编码表示 19
4.2.2 目标函数 19
4.2.3 变异操作 20
4.2.4 算法基本步骤 20
4.3 改进后的算法 21
4.3.1 采用按行、对角线、列分步搜索的办法 21
4.3.2 算法要点 28
4.3.3 算法步骤 28
4.4 构造一个17阶平方数幻方 28
4.5 本章小结 31
5 结论与展望 32
5.1 全文工作总结 32
5.2 工作展望 32
致谢 33
参考文献 34