巧用旋轉(zhuǎn)矩陣找3D組選最少組合

3D旋轉(zhuǎn)矩陣包串全組合公式

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

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

求教【旋轉(zhuǎn)矩陣選號(hào)法】算法 

本人在報(bào)紙上看到一則彩票【旋轉(zhuǎn)矩陣選號(hào)法】，原文如下：  
  設(shè)定供選擇的復(fù)式投注10個(gè)號(hào)碼為：2，4，6，8，10，12，14，16，18，20  
  旋轉(zhuǎn)矩陣組合形成的12注7位號(hào)碼顯示為：  
  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  
  本人一時(shí)之間還看不出其中的算法規(guī)律，特此向各位高手請教