《足彩聪明组合指南》从柯克曼女生问题,到”13 保 10 全部矩阵”
第三章”初识旋转矩阵”,是全书最”数学”的一章。它把这套方法的来龙去脉交代得很清楚。
一道 1847 年的题
在数学界,有一个非常著名的柯克曼女生问题(Kirkman’s Schoolgirl Problem),是 1847 年由英国数学家柯克曼提出的:某学生宿舍共有十五名女生,她们每天 3 人一组出去散步,为了增进相互之间的友谊,希望每位女生每星期都正好有机会与其他每一位女生在同一组中散步一次,问应该怎样安排。
这道看似简单的数学题在提出后的一百多年里竟无人能解,成了国际数学界公认的难题之一,直到 20 世纪 60 年代才有所突破。我国数学家陆家羲对此曾做出过重要的贡献,并以”关于不相交 STEINER 三元系大集的研究”成果,获得了 1987 年的国家自然科学奖一等奖。
柯克曼女生问题是一个典型的组合设计问题,其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。
他还补了一句荣誉:”为纪念这位已故的著名组合学家,国际组合学协会还专门设立了柯克曼奖。”
组合设计能干什么
组合设计问题往往来源于纯粹的数学游戏,但是随着研究的不断深入,人们逐渐发现了它在其他一些领域的用武之地,包括军事战略设计、医药及农业试验、质量控制、芯片设计、彩票投注等。
注意这个列表:彩票投注排在最后一位,和芯片设计并列——它本来就不是”彩票行业的发明”。
彩票用到的,是更难的”组合覆盖设计”
同柯克曼女生问题相比,彩票投注中的旋转矩阵则涉及到另一种更加复杂、参数更多的组合设计,即组合覆盖设计。
以足彩 13 保 12 旋转矩阵为例,就是在 13 场比赛全部猜中的前提下,如何用最少的注数去覆盖二等奖。
要得到一个可以覆盖的投注子集并不困难,难的是如何求解或证明一个最优化的覆盖,即用最少的组合来实现覆盖。
为什么难?作者给了一个很实在的理由:
我们很容易会想到,可以利用计算机,通过穷举所有的可能性来求得最优解。当复式组合较小的时候,这种方案是可行的,但是随着组合的增大,求解所需要的时间会呈几何级增长,即使用最先进的大型计算机,所耗用的时间都会是一个天文数字。
然后是全章最该记住的一句:
实际上,所有的旋转矩阵都是组合数学家们经过多年的精心研究和计算机的大量运算得出的,而不是彩票专家们发明出来的。
四个做出贡献的数学家
1. Patric Ostergard
芬兰赫尔辛基理工大学计算科学与工程系教授,《组合设计杂志》编辑,1996 年的柯克曼奖获得者。他在组合覆盖设计方面的主要贡献是运用全新的模拟冷却算法解决了旋转矩阵的构造问题……在目前广泛使用的 TOTO 矩阵中,有许多是 Ostergard 教授贡献的,包括全部的 13 保 10 矩阵。
2. Alex Sidorenko
基于他所研究的图灵理论(Turán Theory),贡献了许多旋转矩阵和产生旋转矩阵的一般方法。
3. Greg Kuperberg
美国加州大学数学系的副教授。他注意到线性的 [V, T] 编码的补集可以给出可变区块长度的 (v, *, t) 一覆盖,从而可以产生对现有旋转矩阵的一系列改进。
4. Dan Gordon
圣地亚哥通讯研究中心的研究员,著名的覆盖设计研究者和”旋转矩阵发烧友”。他不仅与人合作了多篇经典论文,还总结和搜集了迄今为止最全面、最权威的旋转矩阵。
以及一段历史:
在 TOTO 矩阵方面,国外从 20 世纪 40 年代就开始了相关的研究工作,并于 1946 年由 Anonimo 发布了最早的研究成果。在这以后的几十年中,TOTO 旋转矩阵的优化记录又不断地被刷新,直至新世纪的到来。在这一领域成就卓越的数学家或爱好者还包括:Di Nasso R.、Fagioli C.、D’Agostino F.、Cavallaro C.、Cirabisi F.、Basile G. 等。
三个主要算法
1. 贪心算法(Greedy Method)
它采用逐步构造最优解的方法,在每个阶段都作出一个看上去最优的决策,决策一旦作出,就不再更改。贪心算法曾用来产生过大量的旋转矩阵。虽然当参数很大时,它产生的矩阵离最优解还有较大的差距,但通过其他算法的进一步优化处理,仍然可以产生较好的旋转矩阵。
2. 诱致算法
由美国 Greg Kuperberg 教授创立并倡导的一种比较复杂的算法。这种算法可用来产生优化程度比较高的矩阵,是迄今最好的算法之一。
3. 模拟冷却算法(Simulated Annealing)
由芬兰 Patric Ostergard 教授创造的这种全新的模拟算法,可以提高求解覆盖设计的速度,并且具有很强的通用性,是近年来最好的算法之一。模拟冷却算法是一种随机搜索方法,它的主要特点是不用穷遍集合中每一种可能性,就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却系统来做到这一点的。
这一章的实际意义
它解释了三个”为什么”:
- 为什么旋转矩阵”不是随便排的”——它是有最优性证明的组合覆盖设计;
- 为什么不同书的矩阵注数不一样——因为求解算法不同(贪心 vs 诱致 vs 模拟冷却),优劣相差很大;
- 为什么”13 保 10″的矩阵都是 Ostergard 的——他一个人把这一类算完了。
这也顺带解释了这本书后面那 5 页索引表的价值:它列出的是”当时能达到的最优注数”。
本文依据《足彩聪明组合指南》第三章(原书第 13—16 页)改写;柯克曼女生问题(1847 年、15 名女生、每组 3 人、一周内两两同组一次)、百年未解与 1960 年代突破、陆家羲与 1987 年国家自然科学奖一等奖、柯克曼奖、组合设计在军事/医药农业/质量控制/芯片/彩票的应用、组合覆盖设计与”13 保 12 即用最少注数覆盖二等奖”、穷举的几何级增长、四个数学家(Ostergard 与全部 13 保 10 矩阵、Sidorenko 与图灵理论、Kuperberg 与 [V,T] 编码、Gordon 的最全面矩阵库)、1946 年 Anonimo 最早成果与六位历史人物、三种算法(贪心/诱致/模拟冷却)的特征均按原书核对。
