《新编绝算双色球》第七章(九):矩阵是怎么算出来的——模拟冷却与四种算法
专题八回答”旋转矩阵从哪来”。结论有两层:它不是彩票专家发明的,而是组合数学”覆盖设计”的产物;具体构造靠算法,最著名的是 Ostergard 首创的模拟冷却算法——通过模拟分子降温,在不必穷举的前提下找到接近最优的矩阵。
1. 对旋转矩阵作出突出贡献的主要数学家
有许多国外的彩票专家,声称首次提出旋转矩阵。实际上,所有的旋转矩阵都是组合数学家们经过多年的精心研究得出的,而不是某一个彩票专家所能研究出来的。
| 数学家 | 主要贡献 |
|---|---|
| Patric Ostergard | 用全新的模拟冷却算法解决构造问题;程序 COVER 可迅速产生大量矩阵 |
| Alex Sidorenko | 研究出许多矩阵与几种基于图灵(Turan)定理的一般方法 |
| Greg Kuperberg | 注意到线性 [v,t] 编码的补集可给出区组长度不定的覆盖设计,能改进现有矩阵 |
| Dan Gordon | 总结所有矩阵成果、持续跟踪进展,收集的矩阵最全面最权威,全凭个人兴趣、无经费支持 |
Dan Gordon 是圣地亚哥的通讯研究中心的研究员,个人兴趣:计数理论、组合学、代数分析。Greg Kuperberg 是美国加州大学数学系的副教授,主要研究方向是复杂性分析和微积分。
Patric Ostergard 是芬兰赫尔辛基理工大学计算科学和工程系的教授……他擅长用计算机解决离散数学中的问题……他是 1996 寇克曼奖的得主,这个奖由国际组合学协会颁发,以已故著名组合学家寇克曼的名字命名……他还是组合设计杂志的编辑。他在覆盖设计的主要贡献是开创了用模拟冷却算法构造覆盖设计的先河。
2. 旋转矩阵的主要算法
旋转矩阵的定义是很容易明白的……然而,如何快速有效地构造旋转矩阵是数学家一直研究的问题。当然,这其中最关键的就是算法。近年来最好的算法是模拟冷却算法,它主要由 Patric Ostergard 首创,并且得到了许多后来者的发展。
(1)模拟冷却算法(Simulated Annealing)
模拟冷却算法是一种随机搜索方法,它的主要特点是不用穷遍集合中每一种可能性就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却过程来做到这一点的。在每一种状态,它随机地选择了一种相邻的状态:如这种相邻的状态有一个更低的成本,系统将会转移到该状态;如果这种相邻的状态有一个更高的成本,系统将可能会转移到该状态,也可能不会转移到该状态。转移的概率依赖于现在状态的温度参数(该值越高,转移的概率越大)和两个状态之间的成本差异(差异越大,转移的概率越大)。温度将会渐渐低下来,最终会达到均衡。
