论文部分内容阅读
幻方问题是一个历史悠久的组合数学问题，也是一个典型的NP难问题。1890年法国数学家G.Pfeffermann发现了第一个多重幻方—8阶二重幻方，幻方专家们因此翻开了构造多重幻方的新篇章。 随着计算机飞速发展，其运算速度也急剧提高，人们逐渐将计算机引入到幻方的求解中。幻方问题的复杂性在于，搜索空间随阶数指数递增，但其解在搜索空间中所占的比例，随阶数指数递减。如果不利用幻方的一些特性来进行优化，只用穷举法，即使采用世界上运行速度最快的超级计算机来求解，也不能在可行时间内求出。需要选择合适的算法，仔细分析规律。 本文在比较了现有的构造多重幻方的方法后，采用回溯法来进行8N阶三重幻方的求解，并采用启发式的思想来设计算法。其难点在于如何减小搜索空间以及如何使初始矩阵尽量在最终解较密集的那块区域搜索，以达到减少回溯、缩短搜索时间的目的。 幻方的搜索空间大的超乎想象，没有合适的结构规律，即使采用回溯法，也很难求出。本文引入了两个重要的概念—奇偶偏补序列和互补序列。深入分析三重幻方的特征，发现奇偶各一半的三重序列所占的概率最大。这两种结构均是奇偶各一半的三重序列，本文采用其构造多重幻方，成功的概率也较大。提出了8N阶三重幻方的求解方法，详细分析了多重幻方的调整顺序以及程序设计流程，并用程序验证了该方法的正确性。该算法对于求解其他类型的多重幻方，有一定的参考意义。