旋转矩阵最优覆盖的数学原理

旋转矩阵涉及到的是一种组合设计：覆盖设计。而覆盖设计，填装设计，斯坦纳系，t-设计都是离散数学中组合优化问题。它们解决的是如何组合集合中的元素以达到某种特定的要求。

    为了使读者更容易明白这些问题，下面先从一道相当古老的数学名题讲起。

    （一）寇克曼女生问题  

    某教员打算这样安排她班上的十五名女生散步：散步时三名女生为一组，共五组。问能否在一周内每日安排一次散步，使得每两名女生在这周内一道散步恰好一次？   看起来题目似乎很简单，然而它的彻底解决并不容易。事实上，寇克曼于1847年提出了该问题，过了100多年后，对于一般形式的寇克曼问题的存在性才彻底解决。   用1-15这15个数字分别代表这15个女生，下面给出一组符合要求的分组方法：    星期日：（1，2，3），（4，8，12），（5，10，15），（6，11，13），（7，9，14）
    星期一：（1，4，5），（2，8，10），（3，13，14），（6，9，15），（7，11，12）
    星期二：（1，6，7），（2，9，11），（3，12，15），（4，10，14），（5，8，13）
    星期三：（1，8，9），（2，12，14），（3，5，6），（4，11，15），（7，10，13）
    星期四：（1，10，11），（2，13，15），（3，4，7），（5，9，12），（6，8，14）
    星期五：（1，12，13），（2，4，6），（3，9，10），（5，11，14），（7，8，15）

    星期六：（1，14，15），（2，5，7），（3，8，11），（4，9，13），（6，10，12）  

该问题就是最典型的组合设计问题。其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上看起来，寇克曼女生问题是纯粹的数学游戏，然而它的解却在医药试验设计上有很广泛的运用。   寇克曼女生问题是t-设计中很特殊的一类——可分解斯坦纳设计。下面我会详细解释这几个名词的含义。

    （二）几种组合设计的含义    所谓t-设计是“策略组态，Tactical Configuration”的简称。
    不妨用数学语言来定义t-设计：
    S={S1，S2，……SV}是一个包含有v个元素的集合；
    B1，B2，……，Bb是S的b个子集，而它们包含的元素个数和都是k个；
    B={B1，B2，……Bb}是由这b个子集组成的集合（子集系），
    对于固定整数t，和S的任意一个t元子集（t≥1），如果包含该子集的B中子集的个数都是同一个常数λt，则称B={B1,B2,……，Bb}是集合S上的一个t-(v,k,λt)设计，简称t-设计。
    如果t-(v,k,λt)设计中，t=2,λ=1,则称为斯坦纳系（Steiner)。在该领域，我国已故的数学家陆家羲作出的巨大的贡献，如今每一本讲组合设计的书讲到这个问题，就不能不提到他的大名和以他的名字命名的定理。至今为止，斯坦纳系仍然存在着许多未解决的问题，至今还没有人证明S（17，5，4=476）和S（18，6，5=1428）的存在或不存在。虽然它的参数显得很小。   而旋转矩阵涉及的则是另一种更加复杂、参数更多的组合设计——覆盖设计。
    覆盖设计是一种经过精心设计的b个区组组成的子集系，其中每个区组都有k个元素组成。它可以确保如果选出k个元素，有m个在其中，至少有λ个区组中的元素有t个元素符合。区组中元素的顺序与区组的排列顺序不影响覆盖设计本身。
    （c:v,k,t,m,λ=b)
    可以用数学语言来定义比较简单的覆盖设计：
    S={S1，S2，……SV）是一个包含有v个元素的集合；
    B1，B2，……，Bb是S的b个子集，而它们包含的元素个数都是k个；
    B={B1，B2，……Bb}是由这b个子集组成的集合（子集系）。   
   对于固定整数t，和S的任意一个t元子集（t≥1），如果该子集至少包含在B的λ个区组中，则称B={B1,B2，……，Bb}是集合S上的一个c-(v,k,λt）设计，简称覆盖设计。   填装设计是与覆盖设计相反的设计：
    S={S1，S2，……SV）是一个包含有v个元素的集合；
    B1，B2，……，Bb是S的b个子集，而它们包含的元素个数都是k个； 
   B={B1，B2，……Bb}是由这b个子集组成的集合（子集系）。 
   对于固定整数t，和S的任意一个t元子集（t≥1），如果该子集至多包含在B的λ个区组中，则称B={B1,B2，……，Bb}是集合S上的一个p-(v,k,λt）设计，简称填装设计。   t-设计又叫恰好覆盖与恰好填装。t-设计不一定存在，而覆盖设计一定存在。t-设计中，λ=1，而覆盖设计一般λ>1。此外，t-设计中m=t，所以t-设计只是覆盖设计中比较特殊的一种。   只要b足够大，显然覆盖设计一定存在。而有意义的是找到b的最小值，并找出在上最小值下的覆盖设计，此时的覆盖设计叫做最小覆盖。寻找最小覆盖的问题是组合优化问题的一类，被称为集合覆盖问题（SCP，Set covering problem)，与著名的推销员旅行问题或成本最小化、利润最大化问题，都是优化问题的一种。   但是集合覆盖问题往往经这些问题更加困难。因为其它问题往往已经有比较成熟的、固定的方法。而覆盖设计并没有通用的公式，所以大部分的设计即使用如克雷般超级电脑也很难求出，全盘搜索的算法耗用时间将会是一个天文数字。   这方面，算法就显得相当重要。Oester Grad教授创造出一种全新的模拟算法，它大大提高了求解覆盖设计的速度，但它不能保证找到的覆盖设计一定是最小覆盖设计。它具有很强的通用性。而之前的其他算法往往只能解决固定某些参数的特定问题，解决的往往只是一类问题。   对覆盖设计的研究始于19世纪，1835年J·Plue Cker和W.S.B.Wool House(1844)开始研究此类问题。
    到了1969年，人们发现它对军队中布阵与战略设计以及计算机芯片设计都大有用途，因此得到了迅速发展。在统计上，医药设计，农业试验，核研究，质量控制甚至在彩票中都大有用途。   组合设计问题往往来自于智力游戏，对它们的研究也是纯数学的。但是当研究逐渐深入时，人们逐渐地在生产与其他学科中发现了它的用武之地。这样对它的研究就有了更强大的动力，吸引了更多人的注意，成果也就更加丰富。   在选7的彩票涉及的旋转矩阵中，所有的（6，六）型和（5，五）型旋转矩阵都是t-设计。而一般的旋转矩阵都是覆盖设计。由于数学上对t-研究的比较多，所以有时候我们可以利用t-设计生成一些覆盖设计。   如以下的设计即为一个t-(10,3,3)设计，它在有限射影几何中有很广泛的运用。
    B：（2，3，4）  （1，5，10）  （1，6，9）
      （1，7，8）  （2，9，10）  （3，8，10）

      （4，8，9）  （4，6，7）  （3，5，7）  （2，5，6）   即1-10每个数字都出现了3次，而且每两个数字恰好一起出现1次。从它可以生成10注10个号（7，六）型矩阵（它相当对称，平衡但不是最优的），具体生成方法很简单，取每一组的剩余的7个数就可以生成对应的一组。    

    （三）组合设计的研究内容    1.存在性问题
    若给出要求，研究符合要求的组合设计是否存在，以及存在的条件问题。比如，彩票中的覆盖设计问题，它的存在性就不是问题，因为只要注数足够多，总是可以覆盖的（它的上限为复式投注即完全组合，有意义的是它的下限）。而t-设计又叫恰好覆盖，它的存在性就是一个很值得研究的问题，也就是说，参数要符合什么条件，才会存在恰好覆盖一次的设计。
    对存在性的研究更多的是从理论上。然而，对于一般情形的t-设计是否存在的问题，还远远没有解决。
    2.构造问题
    如果已知某种组合设计存在时，如何把它们构造出来？这是与实际应用联系最紧的问题。实际上，最终无论在彩票中，还是新药设计中，人们关心的是构造出的组合设计。经过数学家上百年的努力，现在已经有一些构造方法。如利用有限的射影几何，关联矩阵，数论中的差集等构造出大量的设计。用组合论自身也能解决一些构造问题。然而，对于一般情形的组合设计的构造性问题离解决还相当遥远。比如彩票中覆盖设计问题（即旋转矩阵）当参数变大时，设计的难度是几何级数上升。   对于一般的最小覆盖问题，仍然没有通用的构造方法。也就是说，目前市场上出现的许许多号码比较多的旋转矩阵，都很难保证是最小覆盖设计，也就是无法保证它是最优的。很多旋转矩阵不断地有人刷新它的下限纪录，也就是越来越接近最小覆盖设计。然而，要证明一个旋转矩阵是否已经是最小覆盖设计，是极其困难的，如果号码很少，还可以通过计算机编程用穷举的方式来解决，而号码稍微多一点，用穷举法超级电脑运算所耗用的时间也将是天文数字。   3.组合设计之间的关系
    例如：一个组合设计是否与另外一个组合设计本质上一样的（同构）。比如把组合中某两个数字互换，这两个设计应该算同一种设计。每一种设计的同构设计是非常多的。有些同构是很难直接看出的，所以就需要研究同构的设计有什么特点，如何准确快速的判断和产生同构设计。   组合设计还研究如何由一个组合设计构造出另外一个。
    比如旋转矩阵中存在着这样的问题，比如10个号码01-10，开始我先选定3注：
    01，02，03，04，05，06，07，
    01，03，05，07，08，09，10，
    02，04，06，07，08，09，10
    问如何添上尽可能少的注数，使它成为（7，六）型平衡式矩阵。
    又如一个旋转矩阵与另外一个旋转矩阵是否同构。即使两个旋转矩阵所有参数都相同，也不一定同构。然而，在实际运用中，人们并不关心同构问题。因为只要能用就行了。
    又如10个号码（7，六）型的有8注，比如是01-10这10个号码，问能否在这基础上添上尽可能少的注数，使得它成为11个号码的（7，六）型的旋转矩阵（01-11）。   4.计数问题
    如果已知某类组合设计存在，自然希望知道这类设计的个数。也就是说互不同构的设计的个数。然而，这个问题是一个极其艰难的问题，现在还很少人去研究它。
    比如很简单的10个号码的（7，六）型矩阵，共有多少种。号码一多，这将是一个很困难的问题。   5.最优设计
    在诸多的满足要求的组合设计中，找到一个最优的设计，这是它研究的内容。比如覆盖设计很多，如何找出最小覆盖设计就是一具艰难的问题。旋转矩阵中需要用到组合优化的算法与组合构造算法。二、旋转矩阵的主要算法
 （一）对旋转矩阵做出突出贡献的主要数学家
    旋转矩阵是一个看似简单实际却异常复杂的问题，尽管有许许多多的人对它非常感兴趣，然而真正在这个领域内做出了开创性贡献的人却不是很多。要想在此领域有所作为，不仅要对组合设计的经典理论和常用方法有深入的了解，还要在此基础上有所创新。有许多国外的彩票专家，比如美国的盖尔·霍华德女士，声称旋转矩阵是由她首先提出来的。实际上，所有的旋转矩阵都是组合数学家们经过多年的精心研究得出的，而不是霍华德这样的彩票专家所能研究出来的。
    在此领域内做出了突出贡献的主要组合数学家有以下几位：
    1.Patric Osergard
    他的主要贡献是用了全新的模拟冷却算法解决了旋转矩阵的构造问题，运用他的模拟冷却程序，可以很迅速的产生许许多多的旋转矩阵。   2.Alex Sidorenko
    他研究出了许多旋转矩阵和几种产生旋转矩阵的基于图灵理论的一般方法。
    3.Greg Kuperberg
    他注意到线性的[v,t]编码的补集可以给出区组长度不定的覆盖设计，而这可以产生对现有的旋转矩阵的一系列改进。   4.Dan Gordon
    他不仅是覆盖设计领域内多篇经典论文的合作者，而且总结了所有的旋转矩阵的成果，并且时时关注着该领域的最新进展。他收集的旋转矩阵是迄今为止最全面、最权威的。而这一切全凭他个人的兴趣，没有任何经费的支持。   以下我将对以上的数学家作一些介绍：
    Dan Gordon是圣地亚哥的通讯研究中心的研究员。个人兴趣：计数理论、组合学、代数分析。
    Greg Kuperberg是美国加州大学的数学系的副教授。主要研究方向是复杂性分析和微积分。他在覆盖设计的主要论文有：
    (1)Asymptotically optimal covering designs(with Daniel Gordon,Oren Patashnik,and Joel Spe-ncer).J.Combin.Theory Ser.A 75(1996),page 270-280.
    (2)Highly saturated packings and reduced coverings(with Gabor Fejes Toth and Wlodzimierz Kuperberg).Monats.Math.125(1998),page 127-145.
     Patric Ostergard是芬兰赫尔辛基理工大学计算科学和工程系的教授。
    他的兴趣集中在数学和计算机科学中系列问题。他的主要研究方向可分为以下几类：
    (1)组合结构的设计
         编码（覆盖编码，纠错编码等等）
         组合设计
         几何填装和覆盖问题
    (2)局部搜索的优化
         模拟冷却算法
         禁忌搜索
         全局优化的随机方法
    (3)加密与解密
    他是1996寇克曼奖的得主，这个奖是由国际组合学协会颁发的，以已故的著名组合学家寇克曼的名字来命名，用来奖励对组合学有突出贡献的数学家。除此之外，他还是组合设计杂志的编辑。
    他在覆盖设计的主要贡献是彩了模拟冷却方法研究出了全新的构造覆盖设计的全新方法。
    他在此领域的主要论文：
    Nurmela,K.J.and Ostergard,P.R.J.“Constructing Covering Designs by Simulated Annealing”,Helsinki University of Technology Digital Systems Laboratory Series B:Technical Reports,No.10；January,1993.（二）旋转矩阵的主要算法
    旋转矩阵的定义是很容易明白的，一般的业余数学爱好者理解没有任何障碍。然而，如何快速有效的构造旋转矩阵是一个数学家们一直在研究的问题。当然，这其中最关键的就是算法。而近年来最好的算法无疑是模拟冷却算法，它主要是由Patric Ostergard首创，并且得到了许多后来者的发展。
    下面我简要介绍一下他论文所用的算法的主要思想。
    1.Simulated Annealing模拟冷却算法
    模拟冷却算法是一种随机搜索方法，它的主要特点是不用穷遍集合中每一种可能性就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却过程来做到这一点的。在每一种状态，它随机地选择了一种相邻的状态，如这种相邻的状态有一个更低的成本，系统将会转移到该状态。如果这种相邻的状态有一个更高的成本，系统将可能会转移到该状态，也可能不会转移到该状态。转移的概率依赖现在的状态的温度参数（该值越高，转移的概率越大）和两个状态之间的成本的差异（差异越大，转移的概率越大）。温度将会渐渐低下来，最终会达到均衡。模拟冷却算法常常用来尝试发现离散数学中一些问题的几乎最优的解。   模拟算法的一般步骤如下：
    (1)给定一个初始状态和初始温度
    (2)外部循环
           A内部循环
             a随机选择一个相邻状态。若相邻状态的成本更低，转移
             b若相邻状态的成本更高，转移的概率为exp{-成本差异/温度}
           B降低温度
    (3)返回所遇到的最优状态
    模拟冷却算法的设计者需要选择以下6个参数：
    初始温度和初始状态
    一种状态的成本函数
    一种状态的相邻函数
    冷却程序
    内部循环方法
    外部循环方法
    初始状态和初始温度实际上对算法影响不大，成本函数一般来说也比较容易定义，尤其是对覆盖设计来说,成本可以定义成重复数字的总个数。相邻函数也可以随机挑选一个向量来解决。而有效的冷却程序一般用T\’=rT，这里T指原来的温度，T\’是新的温度，r是常数，也叫冷却因子。   Patric Ostergard的关于覆盖设计的经典论文基本上就是如此定义模拟算法的参数的。   运用该算法，可以很容易算出一般的旋转矩阵。   除了模拟冷却算法之外，还有另外一些构造旋转矩阵的常用方法。
    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的区组隔断，得到了每个区组个数不定的一个覆盖。最后，将这个覆盖进行如下的修补即可：对每一个长度为1的区组，将该区组替换成一个（1,k,t)的覆盖设计。这是一种比较复杂的算法，然而，却是迄今最好的算法之一。   运用它可以产生优化程度比较高的矩阵。然而，运用这种算法的一个很大的限制是，必须要有一个参数很大的旋转矩阵和许许多多的参数比它小的矩阵。   这样的条件比较苛刻，所以它的运用不是十分广泛。 

三、旋转矩阵如何提高中奖概率
 （一）对彩票中一些常用的概率的理解
    彩票之所以能够吸引成千上万的彩民，是因为它给许多人提供了一夜暴富的机会。而且成本很小，两元钱的投入就可能带来数以百万的回报。然而，它的每百万的大奖都是由上百万张没有中奖的彩票提供的。中大奖的机会微乎其微，这正是彩票的本质与魅力根源。
    尽管彩票中大奖的机会都十分小，然而各种不同彩票中大奖的概率还是有大差别的，比如32选7的北京风采中一等奖的概率为：
    而36选7的北京体彩中一等奖的概率仅为：
    简而言之，彩票号码球的个数越少，中大奖的机会就越大，而同样数目的号码球，选5型的比选7型的中大奖的机会更大。当然，天下不会有免费的午餐，中大奖的机会越大，大奖累种的奖金额越小。越难中的大奖，它累积的大奖金额越高。   一些人买彩票的心态可以分为两种，一种是瞄准百万大奖的，梦想着有朝一日可以改变自己的生活。这种彩民一般并不在意中奖的机会有多渺茫，而比较关心本期累积的大奖奖金有多高。另一种则更希望经常在彩市中有所斩获得一些不大不小的奖。这种人比较适合玩中奖机会稍大的彩票，如上海的天天彩与体彩的“四花选四”。这两种彩票中奖机会都比较高。   除了考虑奖金最高的一等奖，还要考虑次等级的二等奖、三等奖，它们的奖金虽不如一等奖那么高，也颇为丰厚。那么，如果买单注的话，中这些级别的奖的概率都可以算出来。但是，如果买多注的话，如何计算中各个级别的概率呢？如果这些注数胡乱买的，相互之间没有经过科学组合，那么应该如何估计中奖概率呢？   旋转矩阵利用科学的组合方式提高了这种中奖概率。 
——————————————————————————–
 （二）组合投注的中奖概率分析   不妨举个例子，以北京体彩（36选7）为例进行分析。比如我买了一注，那么中二等奖（6个正选号，无特别号）的概率可以用如下方法计算：   现在我想买10个号，如果用复式投注的话，需要买120注，中二等奖的概率可以这样计算：因为只有选的10个号中至少有6个正选号才可能出现二等奖。复式投注实际上由于各注之间重复的号码太多可以效率很低。   如果用旋转矩阵来投注的话，10个号码，需要购买10注。旋转矩阵的含义是，只要选的10个号中包含了7个正选号，一定含有二等奖。如果10个号中包含了6个正选号，也有可能有二等奖。   各种方式具体中奖概率比较：   1.假设用复式投注  若10个号码中含全部正选号；此条件下中二等奖的概率为100%，此条件发生概率为：  若10个号中含6个正选号，此条件下中二等奖的概率为100%，此条件发生概率为：  若10个号中含的正号少于6个，此条件下中二等奖的概率为0；   根据全概率公式，复式投注中二等奖概率为：   也就是说，旋转矩阵用的注数为复式投注的1/12，而中二等奖的概率却是复式投注的1/3，从数字的利用效率来说，旋转矩阵组合号码的效率大约是复式投注的4倍。从成本收益对比来看，旋转矩阵具有明显的优势。
    （三）旋转矩阵中奖的上下限分析   可以分析如果你选中某些正选号的情况下中奖情况（具体见平衡式旋转矩阵那一章）。   旋转矩阵为什么可以提高中奖的概率呢？   实际上，笔者一再强调天下没有免费的午餐。旋转矩阵之所以可以比复式投注与一般组合平均每注中二等奖概率要高，是以它牺牲中二等奖时的注数为前提的。举个例子，就可以明白这个问题了。   比如你准备选01，02，03，04，05，06，07，08，09，10这10个号，买10注有几种组合方式，如：   （1）最极端的方式：01，02，03，04，05，06，07，同样的号连买10注。   （2）一般组合方式：如轮次矩阵，10注。表2-1：10个号码组合轮次矩阵1. 01 02 03 04 05 06 07 2. 02 03 04 05 06 07 08 3. 03 04 05 06 07 08 09 4. 04 05 06 07 08 09 10 5. 05 06 07 08 09 10 01 6. 06 07 08 09 10 01 02 7. 07 08 09 10 01 02 03 8. 08 09 10 01 02 03 04 9. 09 10 01 02 03 04 05 10. 10 01 02 03 04 05 06 （3）旋转矩阵方式：10注。表2-2：10个号码（7，六）型旋转矩阵（10注）1. 01 05 06 07 08 09 10 2. 02 03 04 06 07 08 09 3. 02 03 04 05 07 08 10 4. 02 03 04 05 06 09 10 5. 01 03 04 05 06 07 08 6. 01 02 04 05 06 07 09 7. 01 02 03 05 06 07 10 8. 01 02 03 05 08 09 10 9. 01 02 04 06 08 09 10 10. 01 03 04 07 08 09 10 
    假设开出的中奖号码正选号即为01，02，03，04，05，06，07，那么显然第一种方法中的奖最多，为10个特等奖；系二种方法次之，有1个特等奖和2个二等奖；旋转矩阵只有3个二等奖。
     假设开出的中奖号码为02，03，04，05，06，07，08        第一种方法有10个二等奖；        第二种方法有1个特等奖和2个二等奖；        第三种方法有2个二等奖。    假设开出的号码为01，02，04，05，07，08，09        第一种方法：没有二等奖；        第二种方法：没有二等奖；        第三种方法：1个二等奖。    从以上可以看出，旋转矩阵的优势在于它比较均匀，只要选对7个正选号，无论是哪7个，它都能保证二等以上的奖。而一般组合方法，在某种情况下，可能会得一堆二等奖，其它情况可能只会得很小的奖。
     当然，从以上例子可以看出，在某些情况下，旋转矩阵得的奖比一般组合方式要少。这是由于旋转矩阵尽量分散了风险所致。实际上，旋转矩阵正如保险一样，它使你的收益更加确定。当然，在某些情况下，你收益可能会减少，但总体来说，稳定的收益更符合人的天性。
     此外，旋转矩阵中蕴含的修习的原理在整个保险的保费确定和保险经营中都得到了应用。实际上，旋转矩阵中蕴含的深刻的组合设计理论近百年来一直吸引着数学家，至今仍有许多这方面未解的难题。旋转矩阵以其无穷的魅力，激励着一代代数学家去突破、解决。