旋转矩阵是一个看似简单实际却异常复杂的问题，尽管有许许多多的人对它非常感兴趣，然而真正在这个领域内做出了开创性贡献的人却不是很多。要想在此领域有所作为，不仅要对组合设计的经典理论和常用方法有深入的了解，还要在此基础上有所创新。有许多国外的所谓彩票专家（比如美国的盖尔。霍华德女士）声称旋转矩阵是由她首先提出来的。实际上，所有的旋转矩阵都是组合数学家们经过多年的精心研究得出的，而不是霍华德这样的彩票专家所研究出来的。
在此领域内做出的突出贡献的主要组合数学家有以下几位：
1． patric ostergard
他的主要贡献是用了全新的模拟冷却算法解决了旋转矩阵的构造问题，运用他的模拟冷却程序，可以很迅速的产生许许多多的旋转矩阵。
2． alex sidorenko
他研究出了许多旋转矩阵和几种产生旋转矩阵的基于图灵理论的一般方法。
3． greg kuperberg
他注意到线性的[v,t]编码的补集可以给出区组长度不定的覆盖设计，而这可以产生对现有的旋转矩阵的一系列改进。.
4． dan gordon
他不仅是覆盖设计领域内多篇经典论文的合作者，而且总结了所有的旋转矩阵的成果，并且时时关注着该领域的最新进展。他收集的旋转矩阵是迄今为止最全面、最权威的。而这一切全凭他个人的兴趣，没有任何经费的支持。
1．simulated annealing模拟冷却算法
模拟冷却算法是一种随机搜索方法，它的主要特点是不用穷遍集合中每一种可能性就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却系统来做到这一点的。在每一种状态，它随机地选择了一种相邻的状态，如这种相邻的状态有一个更低的成本，系统将会转移到该状态。如果这种相邻的状态有一个更高的成本，系统将可能会转移到该状态，也可能不会转移到该状态。转移的概率依赖于现在的状态的温度参数（该值越高，转移的概率越大）和两个状态之间的成本的差异（差异越大，转移的概率越大）。温度将会渐渐低下来，最终会达到均衡。模拟冷却算法常常用来尝试发现离散数学中一些问题的几乎最优的解。
模拟算法的一般步骤如下：
a．给定一个初始状态和初始温度
b．外部循环
1. 内部循环
1. 随机选择一个相邻状态若相邻状态的成本更低，转移
2. 若相邻状态的成本更高，转移的概率为exp{-成本差异/温度}
2. 降低温度
c．返回所遇到的最优状态
模拟冷却算法的设计者需要选择以下6个参数：
初始温度和初始状态
· 一种状态的成本函数
· 一种状态的相邻函数
· 冷却程序
· 内部循环方法
· 外部循环方法.
初始状态和初始温度实际上对算法影响不大，成本函数一般来说也比较容易定义，尤其是对覆盖设计来说，成本可以定义成重复数字的总个数。相邻函数也可以随机挑选一个向量来解决。而有效的冷却程序一般用t’=rt，这里t指原来的温度，t’是新的温度，r是常数，也叫冷却因子。
patric ostergard的关于覆盖设计的经典论文基本上就是如此定义模拟算法的参数的。
运用该算法，可以很容易算出一般的旋转矩阵。
除了模拟冷却算法之外，还有另外三种构造旋转矩阵的常用方法：
1． 非连通的集合来结合覆盖设计
如果对某个v=v1+v2和所有的t1+t2=t,都有大小为n1的覆盖设计（v1,k1,t1）和大小为n2的覆盖设计(v2,k2,t2)存在，那么将有大小为n=n1*n2的覆盖设计存在。然而，可以用这种方法产生的旋转矩阵数量很少，而且构造的过程也很复杂。很少的旋转矩阵是用这种方法产生的。
2．贪婪算法。这种算法产生了许多许多的旋转矩阵。这种算法的核心思想是：每个区组都尽可能少重复前面区组的数字，一直重复下去，直到你得到一个覆盖设计。你可以用顺序、逆序或灰色、随机的顺序来重复这个过程。或者可以用你所喜欢的设计。事实上，笔者起初的时候正是用这个方法来产生一些比较简单的矩阵，但是这种算法看起来容易，实际上却十分繁琐，如果不用计算机，即使是很简单的矩阵，也要耗费无数的精力。而且，这种算法只能保证可以产生旋转矩阵，却无法保证产生的旋转矩阵一定是最优的。当参数很大时，用它产生的矩阵离最优的矩阵还差的很远。
但是，可以用这种方法产生旋转矩阵，然后利用其他的优化算法对它再进一步优化，这样可以产生比较优良的旋转矩阵。
3．用诱致算法。greg kuperberg是这种算法的主要创立者和提倡者。
先利用一个巨大的参数为(v,k,t) 的旋转矩阵 ，从v个点中按照某种顺序或完全随机的选出v个点，然后将他们用原来的长度为 k的区组隔断，得到了每个区组个数不定的一个覆盖。最后，将这个覆盖进行如下的修补即可：对每一个长度为l的区组，将该区组替换成一个（l,k,t）的覆盖设计。这是一种比较复杂的算法，然而，确是迄今最好的算法之一。
运用他可以产生优化程度比较高的矩阵。然而，运用这种算法的一个很大的限制是，必须要有一个参数很大的旋转矩阵和许许多多的参数比它小的矩阵。
这样的条件比较苛刻，所以它的运用不是十分广泛
( 南王 2006-9-2 9:35:27 ) |
