ZBLOG

旋转矩阵的算法

1．模拟退火Simulated Annealing算法

模拟冷却算法是一种随机搜索方法，它的主要特点是不用穷遍集合中每一种可能性就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却系统来做到这一点的。在每一种状态，它随机地选择了一种相邻的状态，如这种相邻的状态有一个更低的成本，系统将会转移到该状态。如果这种相邻的状态有一个更高的成本，系统将可能会转移到该状态，也可能不会转移到该状态。转移的概率依赖于现在的状态的温度参数（该值越高，转移的概率越大）和两个状态之间的成本的差异（差异越大，转移的概率越大）。温度将会渐渐低下来，最终会达到均衡。模拟冷却算法常常用来尝试发现离散数学中一些问题的几乎最优的解。

2． 非连通的集合算法来结合覆盖设计

如果对某个v=v1+v2和所有的t1+t2=t,都有大小为N1的覆盖设计（v1,k1,t1）和大小为N2的覆盖设计(v2,k2,t2)存在，那么将有大小为N=N1*N2的覆盖设计存在。然而，可以用这种方法产生的旋转矩阵数量很少，而且构造的过程也很复杂。很少的旋转矩阵是用这种方法产生的。

3．贪婪算法

这种算法产生了许多许多的旋转矩阵。这种算法的核心思想是：每个区组都尽可能少重复前面区组的数字，一直重复下去，直到你得到一个覆盖设计。你可以用顺序、逆序或灰色、随机的顺序来重复这个过程。或者可以用你所喜欢的设计。事实上，笔者起初的时候正是用这个方法来产生一些比较简单的矩阵，但是这种算法看起来容易，实际上却十分繁琐，如果不用计算机，即使是很简单的矩阵，也要耗费无数的精力。而且，这种算法只能保证可以产生旋转矩阵，却无法保证产生的旋转矩阵一定是最优的。当参数很大时，用它产生的矩阵离最优的矩阵还差的很远。

但是，可以用这种方法产生旋转矩阵，然后利用其他的优化算法对它再进一步优化，这样可以产生比较优良的旋转矩阵。

4．诱致算法

Greg Kuperberg是这种算法的主要创立者和提倡者。

先利用一个巨大的参数为(V,K,t) 的旋转矩阵 ，从V个点中按照某种顺序或完全随机的选出v个点，然后将他们用原来的长度为 K的区组隔断，得到了每个区组个数不定的一个覆盖。最后，将这个覆盖进行如下的修补即可：对每一个长度为l的区组，将该区组替换成一个（l,k,t）的覆盖设计。这是一种比较复杂的算法，然而，确是迄今最好的算法之一。

运用他可以产生优化程度比较高的矩阵。然而，运用这种算法的一个很大的限制是，必须要有一个参数很大的旋转矩阵和许许多多的参数比它小的矩阵。