正交表是一类非常重要的数组结构，它在正交实验设计、编码理论、计算机安全等领域有着广泛的应用。人们对正交表的构造大都是纯数学方法。本文应用拟物拟人方法来求解若干正交表的构造问题。拟物拟人方法是一种求解诸如NP问题和其它困难数学问题的方法。所谓 拟物就是主动地向自然界学习解决问题的方法，它是寻找到与原始数学问题等 价的物理世界并观察这个世界中物质运动的生动形象，然后从中得出启发并逐 步形式化为算法以求解问题。拟人方法则是向人，向人类的各种社会经验学习 解决问题的策略。拟物方法将原始问题落实为优化问题，而用数学方法在求解 优化问题时，常常会碰到计算落入目标函数的局部极小值陷阶的困境，如何从 这种困境中逃逸出来，使得计算奔向前景更好的区域，拟物方法则无能为力， 而应用拟人方法则可以设计出好的“跳出陷阱”策略。 本学位论文围绕求解正交表问题的拟物拟人方法做了以下工作： 第一，阐述了拟物拟人方法的涵义，通过对一些具体问题应用拟物拟人方 法的心得和体会，总结出应用该方法求解问题的基本技术路线。 第二，对于求解SAT问题的拟物拟人方法中所依赖的物理模型做了进一 步分析，针对此模型的一个物理猜想，构造出反例，证明了这个物理猜想不成 立。但是，考虑到拟物拟人算法吸引区的存在，此反例并不降低该物理模型的现实效果。这就从侧面反映出拟人方法是保证算法高效的必不可少的环节，从而加深了对拟物拟人方法的感性认识。 第三，应用拟物拟人方法求解正交表的构造问题。我们首次建立了求解饱 和正交表问题的物理模型，并从理论上证明了该模型的正确性。在此基础上， 应用拟人方法设计出拟人化的“跳出局部极小值陷阶”的策略，从而得到了求 解饱和正交表问题的拟物拟人算法。实验表明，其效果明显地高于基于纯数学 的冲突数目标函数模型。应用此算法，我们成功地计算出难的三水平正交表 本课题为国家重点基础研究发展“九七三”规划，国家“八六三”高技术发展计划，高等学校博士学 位点专项科研基金及中国科学院软件研究所计算机科学开放研究实验室课题基金资助项目 1 g 一 g S 第四，应用拟物拟人方法尝试求解古老而重要的拉丁方、正交拉丁方（它 们事实上是正交表）问题。我们结合这些问题的特性，建立了新的物理模型， 从理论上证明了这些物理模型的正确性，并设计出拟人化的“跳出局部极小值 陷饼”的策略，得到了求解拉丁方、正交拉丁方的拟物拟人算法。实验表明，” 对某些问题算法有好的效果。虽然对于著名的求解两个10阶正交拉丁方问题 Q 没有成功，但按该拟物拟人算法搜寻的结果已非常接近其解。 【 g