巧用旋轉矩陣找3D組選最少組合

3D旋轉矩陣包串全組合公式

旋轉矩陣是一個看似簡單實際卻異常復雜的問題，盡管有許許多多的人對它非常感興趣，然而真正在這個領域內做出了開創(chuàng)性貢獻的人卻不是很多。要想在此領域有所作為，不僅要對組合設計的經典理論和常用方法有深入的了解，還要在此基礎上有所創(chuàng)新。有許多國外的所謂彩票專家（比如美國的蓋爾。霍華德女士）聲稱旋轉矩陣是由她首先提出來的。實際上，所有的旋轉矩陣都是組合數學家們經過多年的精心研究得出的，而不是霍華德這樣的彩票專家所研究出來的。  
   
  在此領域內做出的突出貢獻的主要組合數學家有以下幾位：  
   
          1．   Patric   Ostergard　  
   
          他的主要貢獻是用了全新的模擬冷卻算法解決了旋轉矩陣的構造問題，運用他的模擬冷卻程序，可以很迅速的產生許許多多的旋轉矩陣。  
   
          2．   Alex   Sidorenko  
   
          他研究出了許多旋轉矩陣和幾種產生旋轉矩陣的基于圖靈理論的一般方法。  
   
          3．   Greg   Kuperberg    
   
          他注意到線性的[v,t]編碼的補集可以給出區(qū)組長度不定的覆蓋設計，而這可以產生對現有的旋轉矩陣的一系列改進。.  
   
          4．   Dan   Gordon　  
   
          他不僅是覆蓋設計領域內多篇經典論文的合作者，而且總結了所有的旋轉矩陣的成果，并且時時關注著該領域的最新進展。他收集的旋轉矩陣是迄今為止最全面、最權威的。而這一切全憑他個人的興趣，沒有任何經費的支持。  
   
  1．Simulated   Annealing模擬冷卻算法  
   
          模擬冷卻算法是一種隨機搜索方法，它的主要特點是不用窮遍集合中每一種可能性就可以找到最優(yōu)或幾乎最優(yōu)的狀態(tài)。它是通過模擬一個分子系統(tǒng)的自然冷卻系統(tǒng)來做到這一點的。在每一種狀態(tài)，它隨機地選擇了一種相鄰的狀態(tài)，如這種相鄰的狀態(tài)有一個更低的成本，系統(tǒng)將會轉移到該狀態(tài)。如果這種相鄰的狀態(tài)有一個更高的成本，系統(tǒng)將可能會轉移到該狀態(tài)，也可能不會轉移到該狀態(tài)。轉移的概率依賴于現在的狀態(tài)的溫度參數（該值越高，轉移的概率越大）和兩個狀態(tài)之間的成本的差異（差異越大，轉移的概率越大）。溫度將會漸漸低下來，最終會達到均衡。模擬冷卻算法常常用來嘗試發(fā)現離散數學中一些問題的幾乎最優(yōu)的解。  
   
          模擬算法的一般步驟如下：  
   
          A．給定一個初始狀態(tài)和初始溫度    
   
          B．外部循環(huán)    
   
          1.   內部循環(huán)    
   
          1.   隨機選擇一個相鄰狀態(tài)若相鄰狀態(tài)的成本更低，轉移  
   
          2.   若相鄰狀態(tài)的成本更高，轉移的概率為exp{-成本差異/溫度}    
   
          2.   降低溫度    
   
          C．返回所遇到的最優(yōu)狀態(tài)    
   
          模擬冷卻算法的設計者需要選擇以下6個參數：  
   
          初始溫度和初始狀態(tài)    
   
          ·   一種狀態(tài)的成本函數    
   
          ·   一種狀態(tài)的相鄰函數    
   
          ·   冷卻程序    
   
          ·   內部循環(huán)方法    
   
          ·   外部循環(huán)方法.    
   
          初始狀態(tài)和初始溫度實際上對算法影響不大，成本函數一般來說也比較容易定義，尤其是對覆蓋設計來說，成本可以定義成重復數字的總個數。相鄰函數也可以隨機挑選一個向量來解決。而有效的冷卻程序一般用T’=rT，這里T指原來的溫度，T’是新的溫度，r是常數，也叫冷卻因子。  
   
          Patric   Ostergard的關于覆蓋設計的經典論文基本上就是如此定義模擬算法的參數的。  
   
          運用該算法，可以很容易算出一般的旋轉矩陣。  
   
          除了模擬冷卻算法之外，還有另外三種構造旋轉矩陣的常用方法：  
   
          1．   非連通的集合來結合覆蓋設計  
   
          如果對某個v=v1+v2和所有的t1+t2=t,都有大小為N1的覆蓋設計（v1,k1,t1）和大小為N2的覆蓋設計(v2,k2,t2)存在，那么將有大小為N=N1*N2的覆蓋設計存在。然而，可以用這種方法產生的旋轉矩陣數量很少，而且構造的過程也很復雜。很少的旋轉矩陣是用這種方法產生的。  
   
          2．貪婪算法。這種算法產生了許多許多的旋轉矩陣。這種算法的核心思想是：每個區(qū)組都盡可能少重復前面區(qū)組的數字，一直重復下去，直到你得到一個覆蓋設計。你可以用順序、逆序或灰色、隨機的順序來重復這個過程?；蛘呖梢杂媚闼矚g的設計。事實上，筆者起初的時候正是用這個方法來產生一些比較簡單的矩陣，但是這種算法看起來容易，實際上卻十分繁瑣，如果不用計算機，即使是很簡單的矩陣，也要耗費無數的精力。而且，這種算法只能保證可以產生旋轉矩陣，卻無法保證產生的旋轉矩陣一定是最優(yōu)的。當參數很大時，用它產生的矩陣離最優(yōu)的矩陣還差的很遠。  
   
          但是，可以用這種方法產生旋轉矩陣，然后利用其他的優(yōu)化算法對它再進一步優(yōu)化，這樣可以產生比較優(yōu)良的旋轉矩陣。  
   
          3．用誘致算法。Greg   Kuperberg是這種算法的主要創(chuàng)立者和提倡者。  
   
          先利用一個巨大的參數為(V,K,t)   的旋轉矩陣   ，從V個點中按照某種順序或完全隨機的選出v個點，然后將他們用原來的長度為   K的區(qū)組隔斷，得到了每個區(qū)組個數不定的一個覆蓋。最后，將這個覆蓋進行如下的修補即可：對每一個長度為l的區(qū)組，將該區(qū)組替換成一個（l,k,t）的覆蓋設計。這是一種比較復雜的算法，然而，確是迄今最好的算法之一。  
   
          運用他可以產生優(yōu)化程度比較高的矩陣。然而，運用這種算法的一個很大的限制是，必須要有一個參數很大的旋轉矩陣和許許多多的參數比它小的矩陣。  
   

          這樣的條件比較苛刻，所以它的運用不是十分廣泛

求教【旋轉矩陣選號法】算法 

本人在報紙上看到一則彩票【旋轉矩陣選號法】，原文如下：  
  設定供選擇的復式投注10個號碼為：2，4，6，8，10，12，14，16，18，20  
  旋轉矩陣組合形成的12注7位號碼顯示為：  
  02   04   06   08   10   12   14  
  02   04   06   08   16   18   20  
  02   04   06   10   12   16   20  
  02   04   06   10   12   18   20  
  02   04   08   10   12   16   20  
  02   04   08   10   12   18   20  
  02   04   10   12   14   16   18  
  02   06   10   14   16   18   20  
  04   08   12   14   16   18   20  
  06   08   10   12   14   16   18  
  06   08   10   12   14   16   20  
  06   08   10   12   14   18   20  
  本人一時之間還看不出其中的算法規(guī)律，特此向各位高手請教