彩票旋转矩阵的数学原理

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

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 ）一、從寇克曼女生問題講起旋轉矩陣涉及到的是一種組合設計：覆蓋設計。而覆蓋設計，填裝設計，斯坦納系，t-設計都是離散數學中組合優

3、化問題。它們解決的是如何組合集合中的元素以達到某種特定的要求。為了使讀者更容易明白這些問題，下面先從一道相當古老的數學名題講起。（一）寇克曼女生問題 某教員打算這樣安排她班上的十五名女生散步：散步時三名女生為一組，共五組。問能否在一周內每日安排一次散步，使得每兩名女生在這周內一道散步恰好一次？ 看起來題目似乎很簡單，然而它的徹底解決並不容易。事實上，寇克曼於 1847 年提出了該問題，過了 100 多年後，對於一般形式的寇克曼問題的存在性才徹底解決。 用 1-15 這 15 個數字分別代表這 15個女生，下面給出一組符合要求的分組方法：星期日：（1，2，3），（4，8，12），（5，10，15

4、），（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

5、，13），（6，10，12） 該問題就是最典型的組合設計問題。其本質就是如何將一個集合中的元素組合成一定的子集系以滿足一定的要求。表面上看起來，寇克曼女生問題是純粹的數學遊戲，然而它的解卻在醫藥試驗設計上有很廣泛的運用。 寇克曼女生問題是 t-設計中很特殊的一類可分解斯坦納設計。下面我會詳細解釋這幾個名詞的含義。（二）幾種組合設計的含義所謂 t-設計是“策略組態，Tactical Configuration”的簡稱。不妨用數學語言來定義 t-設計：S=S1，S2，SV是一個包含有 v 個元素的集合；B1，B2，Bb 是 S 的 b 個子集，而它們包含的元素個數和都是 k 個；B=B1，B2，B

6、b是由這 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)。在該領域，我國已故的數學家陸家羲作出的巨大的貢獻，如今每一本講組合設計的書講到這個問題，就不能不提到他的大名和以他的名字命名的定理。至今為止，斯坦納系仍然存在著許多未解決的問題，至今還沒有酥鱏（17，5， 4=476）和S（18，6，5=1428）的存在或不存在。雖然它的參數顯

7、得很小。 而旋轉矩陣涉及的則是另一種更加復雜、參數更多的組合設計覆蓋設計。覆蓋設計是一種經過精心設計的 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 的任意一個

8、 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），如果該子集至多包含在B 的 個區組中，則稱 B=B1,B2，Bb是集合 S 上的一個 p- (v,k,t）設計，簡稱填裝設計。 t-設計又叫恰好覆蓋與恰好填裝。t-設計

9、不一定存在，而覆蓋設計一定存在。t-設計中，=1，而覆蓋設計一般1。此外，t-設計中 m=t，所以 t-設計只是覆蓋設計中比較特殊的一種。只要 b 足夠大，顯然覆蓋設計一定存在。而有意義的是找到 b 的最小值，並找出在上最小值下的覆蓋設計，此時的覆蓋設計叫做最小覆蓋。尋找最小覆蓋的問題是組合優化問題的一類，被稱為集合覆蓋問題（SCP，Set covering problem)，與著名的推銷員旅行問題或成本最小化、利潤最大化問題，都是優化問題的一種。 但是集合覆蓋問題往往經這些問題更加困難。因為其它問題往往已經有比較成熟的、固定的方法。而覆蓋設計並沒有通用的公式，所以大部分的設計即使用如克雷般超

10、級電腦也很難求出，全盤搜索的算法耗用時間將會是一個天文數字。 這方面，算法就顯得相當重要。Oester Grad 教授創造出一種全新的模擬算法，它大大提高了求解覆蓋設計的速度，但它不能保證找到的覆蓋設計一定是最小覆蓋設計。它具有很強的通用性。而之前的其他算法往往只能解決固定某些參數的特定問題，解決的往往只是一類問題。 對覆蓋設計的研究始於 19 世紀，1835 年 JPlue Cker 和 W.S.B.Wool House(1844)開始研究此類問題。到了 1969 年，人們發現它對軍隊中布陣與戰略設計以及計算機芯片設計都大有用途，因此得到了迅速發展。在統計上，醫藥設計，農業試驗，核研究，質量

11、控制甚至在彩票中都大有用途。 組合設計問題往往來自於智力遊戲，對它們的研究也是純數學的。但是當研究逐漸深入時，人們逐漸地在生產與其他學科中發現了它的用武之地。這樣對它的研究就有了更強大的動力，吸引了更多人的註意，成果也就更加豐富。 在選 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

12、） （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-設計又叫恰好覆蓋，它的存在性就是一個很值

13、得研究的問題，也就是說，參數要符合什麽條件，才會存在恰好覆蓋一次的設計。對存在性的研究更多的是從理論上。然而，對於一般情形的 t-設計是否存在的問題，還遠遠沒有解決。2.構造問題如果已知某種組合設計存在時，如何把它們構造出來？這是與實際應用聯系最緊的問題。實際上，最終無論在彩票中，還是新藥設計中，人們關心的是構造出的組合設計。經過數學家上百年的努力，現在已經有一些構造方法。如利用有限的射影幾何，關聯矩陣，數論中的差集等構造出大量的設計。用組合論自身也能解決一些構造問題。然而，對於一般情形的組合設計的構造性問題離解決還相當遙遠。比如彩票中覆蓋設計問題（即旋轉矩陣）當參數變大時，設計的難度是幾何級

14、數上升。 對於一般的最小覆蓋問題，仍然沒有通用的構造方法。也就是說，目前市場上出現的許許多號碼比較多的旋轉矩陣，都很難保證是最小覆蓋設計，也就是無法保證它是最優的。很多旋轉矩陣不斷地有人刷新它的下限紀錄，也就是越來越接近最小覆蓋設計。然而，要證明一個旋轉矩陣是否已經是最小覆蓋設計，是極其困難的，如果號碼很少，還可以通過計算機編程用窮舉的方式來解決，而號碼稍微多一點，用窮舉法超級電腦運算所耗用的時間也將是天文數字。 3.組合設計之間的關系例如：一個組合設計是否與另外一個組合設計本質上一樣的（同構）。比如把組合中某兩個數字互換，這兩個設計應該算同一種設計。每一種設計的同構設計是非常多的。有些同構是

15、很難直接看出的，所以就需要研究同構的設計有什麽特點，如何準確快速的判斷和產生同構設計。 組合設計還研究如何由一個組合設計構造出另外一個。比如旋轉矩陣中存在著這樣的問題，比如 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 註，

16、比如是 01-10 這 10 個號碼，問能否在這基礎上添上盡可能少的註數，使得它成為 11 個號碼的（7，六）型的旋轉矩陣（01-11）。 4.計數問題如果已知某類組合設計存在，自然希望知道這類設計的個數。也就是說互不同構的設計的個數。然而，這個問題是一個極其艱難的問題，現在還很少人去研究它。比如很簡單的 10 個號碼的（7，六）型矩陣，共有多少種。號碼一多，這將是一個很困難的問題。 5.最優設計在諸多的滿足要求的組合設計中，找到一個最優的設計，這是它研究的內容。比如覆蓋設計很多，如何找出最小覆蓋設計就是一具艱難的問題。旋轉矩陣中需要用到組合優化的算法與組合構造算法。二、旋轉矩陣的主要算法（一）對旋轉矩陣做出突出貢獻的主要數學家旋轉矩陣是一個看似簡單實際卻異常復雜的問題，盡管有許許多多的人對它非常感興趣，然而真正在這個領域內做出了開創性貢獻的人卻不是很多。要想在此領域有所作為，不僅要對