旋转矩阵的数学原理.doc

《旋转矩阵的数学原理.doc》由会员分享，可在线阅读，更多相关《旋转矩阵的数学原理.doc（18页珍藏版）》请在金锄头文库上搜索。

1、旋转矩阵的数学原理注意：本章专门为那些有一定数学基础的、对旋转矩阵的设计非常感兴趣的人而写。如果你的数学功底不够，或者只关心旋转矩阵的运用，那么建议你直接跳过这一章。一、从寇克曼女生问题讲起旋转矩阵涉及到的是一种组合设计：覆盖设计。而覆盖设计，填装设计，斯坦纳系，t-设计都是离散数学中组合优化问题。它们解决的是如何组合集合中的元素以达到某种特定的要求。为了使读者更容易明白这些问题，下面先从一道相当古老的数学名题讲起。（一）寇克曼女生问题 某教员打算这样安排她班上的十五名女生散步：散步时三名女生为一组，共五组。问能否在一周内每日安排一次散步，使得每两名女生在这周内一道散步恰好一次？ 看起来题目似

2、乎很简单，然而它的彻底解决并不容易。事实上，寇克曼于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），（

3、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-设计中很特殊的一类可分解斯坦纳设计。下面我会详细解释这几个名词的含义。

4、（二）几种组合设计的含义 所谓t-设计是“策略组态，Tactical Configuration”的简称。 不妨用数学语言来定义t-设计： S=S1，S2，SV是一个包含有v个元素的集合； B1，B2，Bb是S的b个子集，而它们包含的元素个数和都是k个； B=B1，B2，Bb是由这b个子集组成的集合（子集系）， 对于固定整数t，和S的任意一个t元子集（t1），如果包含该子集的B中子集的个数都是同一个常数t，则称B=B1,B2,，Bb是集合S上的一个t-(v,k,t)设计，简称t-设计。 如果t-(v,k,t)设计中，t=2,=1,则称为斯坦纳系（Steiner)。在该领域，我国已故的数学家陆家

5、羲作出的巨大的贡献，如今每一本讲组合设计的书讲到这个问题，就不能不提到他的大名和以他的名字命名的定理。至今为止，斯坦纳系仍然存在着许多未解决的问题，至今还没有人证明S（17，5，4=476）和S（18，6，5=1428）的存在或不存在。虽然它的参数显得很小。 而旋转矩阵涉及的则是另一种更加复杂、参数更多的组合设计覆盖设计。 覆盖设计是一种经过精心设计的b个区组组成的子集系，其中每个区组都有k个元素组成。它可以确保如果选出k个元素，有m个在其中，至少有个区组中的元素有t个元素符合。区组中元素的顺序与区组的排列顺序不影响覆盖设计本身。 （c:v,k,t,m,=b) 可以用数学语言来定义比较简单的覆

6、盖设计： S=S1，S2，SV）是一个包含有v个元素的集合； B1，B2，Bb是S的b个子集，而它们包含的元素个数都是k个； B=B1，B2，Bb是由这b个子集组成的集合（子集系）。 对于固定整数t，和S的任意一个t元子集（t1），如果该子集至少包含在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元子集（t1）

7、，如果该子集至多包含在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)，与著名的推销员旅行问题或成本最小化、利润最大化问题，都是优化问题的

8、一种。 但是集合覆盖问题往往经这些问题更加困难。因为其它问题往往已经有比较成熟的、固定的方法。而覆盖设计并没有通用的公式，所以大部分的设计即使用如克雷般超级电脑也很难求出，全盘搜索的算法耗用时间将会是一个天文数字。 这方面，算法就显得相当重要。Oester Grad教授创造出一种全新的模拟算法，它大大提高了求解覆盖设计的速度，但它不能保证找到的覆盖设计一定是最小覆盖设计。它具有很强的通用性。而之前的其他算法往往只能解决固定某些参数的特定问题，解决的往往只是一类问题。 对覆盖设计的研究始于19世纪，1835年JPlue Cker和W.S.B.Wool House(1844)开始研究此类问题。 到

9、了1969年，人们发现它对军队中布阵与战略设计以及计算机芯片设计都大有用途，因此得到了迅速发展。在统计上，医药设计，农业试验，核研究，质量控制甚至在彩票中都大有用途。 组合设计问题往往来自于智力游戏，对它们的研究也是纯数学的。但是当研究逐渐深入时，人们逐渐地在生产与其他学科中发现了它的用武之地。这样对它的研究就有了更强大的动力，吸引了更多人的注意，成果也就更加丰富。 在选7的彩票涉及的旋转矩阵中，所有的（6，六）型和（5，五）型旋转矩阵都是t-设计。而一般的旋转矩阵都是覆盖设计。由于数学上对t-研究的比较多，所以有时候我们可以利用t-设计生成一些覆盖设计。 如以下的设计即为一个t-(10,3,

10、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.存在性问题 若给出要求，研究符合要求的组合设计是否存在，以及存在的条件问题。比如，彩票中的覆盖设计问题，它的存在性就不是问题，因为只要注数足够多，总是可以覆盖的（它的

11、上限为复式投注即完全组合，有意义的是它的下限）。而t-设计又叫恰好覆盖，它的存在性就是一个很值得研究的问题，也就是说，参数要符合什么条件，才会存在恰好覆盖一次的设计。 对存在性的研究更多的是从理论上。然而，对于一般情形的t-设计是否存在的问题，还远远没有解决。2.构造问题 如果已知某种组合设计存在时，如何把它们构造出来？这是与实际应用联系最紧的问题。实际上，最终无论在彩票中，还是新药设计中，人们关心的是构造出的组合设计。经过数学家上百年的努力，现在已经有一些构造方法。如利用有限的射影几何，关联矩阵，数论中的差集等构造出大量的设计。用组合论自身也能解决一些构造问题。然而，对于一般情形的组合设计的

12、构造性问题离解决还相当遥远。比如彩票中覆盖设计问题（即旋转矩阵）当参数变大时，设计的难度是几何级数上升。 对于一般的最小覆盖问题，仍然没有通用的构造方法。也就是说，目前市场上出现的许许多号码比较多的旋转矩阵，都很难保证是最小覆盖设计，也就是无法保证它是最优的。很多旋转矩阵不断地有人刷新它的下限纪录，也就是越来越接近最小覆盖设计。然而，要证明一个旋转矩阵是否已经是最小覆盖设计，是极其困难的，如果号码很少，还可以通过计算机编程用穷举的方式来解决，而号码稍微多一点，用穷举法超级电脑运算所耗用的时间也将是天文数字。 3.组合设计之间的关系 例如：一个组合设计是否与另外一个组合设计本质上一样的（同构）。

13、比如把组合中某两个数字互换，这两个设计应该算同一种设计。每一种设计的同构设计是非常多的。有些同构是很难直接看出的，所以就需要研究同构的设计有什么特点，如何准确快速的判断和产生同构设计。 组合设计还研究如何由一个组合设计构造出另外一个。 比如旋转矩阵中存在着这样的问题，比如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，六）型平衡式矩阵。 又如一个旋转矩阵与另外一个旋转矩阵是否同构。即使两个旋转矩阵所有参数都相同，也不一定同构。然而，

14、在实际运用中，人们并不关心同构问题。因为只要能用就行了。 又如10个号码（7，六）型的有8注，比如是01-10这10个号码，问能否在这基础上添上尽可能少的注数，使得它成为11个号码的（7，六）型的旋转矩阵（01-11）。 4.计数问题 如果已知某类组合设计存在，自然希望知道这类设计的个数。也就是说互不同构的设计的个数。然而，这个问题是一个极其艰难的问题，现在还很少人去研究它。 比如很简单的10个号码的（7，六）型矩阵，共有多少种。号码一多，这将是一个很困难的问题。 5.最优设计 在诸多的满足要求的组合设计中，找到一个最优的设计，这是它研究的内容。比如覆盖设计很多，如何找出最小覆盖设计就是一具艰

15、难的问题。旋转矩阵中需要用到组合优化的算法与组合构造算法。二、旋转矩阵的主要算法（一）对旋转矩阵做出突出贡献的主要数学家 旋转矩阵是一个看似简单实际却异常复杂的问题，尽管有许许多多的人对它非常感兴趣，然而真正在这个领域内做出了开创性贡献的人却不是很多。要想在此领域有所作为，不仅要对组合设计的经典理论和常用方法有深入的了解，还要在此基础上有所创新。有许多国外的彩票专家，比如美国的盖尔霍华德女士，声称旋转矩阵是由她首先提出来的。实际上，所有的旋转矩阵都是组合数学家们经过多年的精心研究得出的，而不是霍华德这样的彩票专家所能研究出来的。 在此领域内做出了突出贡献的主要组合数学家有以下几位： 1.Patric Osergard 他的主要贡献是用了全新的模拟冷却算法解决了旋转矩阵的构