十類算法的詳細說明
偶以賽題為背景來說明一下：
1、蒙特卡羅算法：
在大多數建模賽題中都離不開計算機的仿真，隨機性模擬是非常常見的算法之一。
舉個例子就是97年的A題，每個零件都有自己的標定值，也都有自己的容差等級，而求解最優的組合方案將要面對著的是一個極其復雜的公式和108種容差選取方案，根本不可能去解析求解的，那如何去找到最優的方案呢？隨機性模擬搜索最優方案就是其中的一種方法，在每個零件可行的區間中按照正態分布隨機的選取一個標定值和選取一個容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個最佳的。另一個例子就是去年的彩票第二問，要求設計一種更好的方案，首先方案的優劣決定于很多復雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。
2、數據擬合、參數估計、插值等算法：
數據擬合在很多賽題中有應用，與圖形處理有關的問題很多與擬合有關系，一個例子就是98年美賽A題，生物組織切片的三維插值處理，94年A題逢山開路，山體海拔高度的插值計算，還有吵的沸沸揚揚可能會考的非典問題也要用到數據擬合算法，觀察數據的走向進行處理。此類問題在Matlab中有很多數據處理現成的函數可以調用，熟悉Matlab，這些方法都能游刃有余的做好。
3、規劃類問題算法：
競賽中很多問題都和數學規劃有關，可以說不少的模型都可以歸結為一組不等式組作為約束條件、幾個函數表達式作為目標函數的問題，遇到這類問題，求解就是關鍵了，比如98B，用很多不等式完全可以把問題刻畫清楚，因此列舉出規劃后用Lindo、Lingo等軟件來進行解決比較方便，所以還需要熟悉這兩個軟件。
4、圖論問題：
98B、00B、95鎖具裝箱等問題體現了圖論問題的重要性，這類問題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。每一個算法認真的話都應該寫一遍，否則到比賽時再寫就晚了，
5、計算機算法設計中的問題：
計算機算法設計包括很多內容：動態規劃、回溯搜索、分治算法、分支定界。比如92B用分支定界法，97B是典型的動態規劃問題，此外98B體現了分治算法。這方面問題和acm中的問題類似，推薦的書籍有《計算機算法設計與分析》電子工業出版社等與計算機算法有關的書。
6、最優化理論的三大非經典算法：
模擬退火法、神經網絡、遺傳算法。這十幾年來最優化理論有了飛速發展，這三類算法發展很快，近幾年的賽題越來越復雜，很多問題沒有什么很好的模型可以借鑒，于是這三類算法很多時候可以派上用場，比如：97A的模擬退火算法、00B的神經網絡分類算法、象01B這種難題也可以使用神經網絡、還有美國競賽89A也和BP算法有關系，當時是86年剛提出BP算法，89年就考了，說明賽題可能是當今前沿科技的抽象體現。03B伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法。
7、網格算法和窮舉算法
網格算法和窮舉法一樣，只是網格法是連續問題的窮舉。比如要求在N個變量情況下的最優化問題，那么可以對這些變量可取的空間進行采點，比如在[a,b]區間內取M+1個點，就是在a、a+(b-a)/M、a+2*(b-a)/M、……、b那么這樣循環就需要進行(M+1)^N次運算，所以計算量很大。
比如97年A題、99年B題都可以用網格法搜索，這種方法最好在運算速度叫快的計算機中進行，還有要用高級語言來做，最好不要用Matlab做網格，否則會算很久的。窮舉法大家都熟悉，就不說了。
8、一些連續離散化方法
大部分物理問題的編程解決，都和這種方法有一定的聯系，物理問題是反映我們生活在一個連續的世界中，計算機求解只認離散的變量，所以需要將連續量進行離散處理，這種方法應用很廣，大都和上面的很多算法有關，事實上，網格算法、蒙特卡羅算法、模擬退火都用了這個思想。
9、數值分析算法
這類算法是針對高級語言而專門設的，如果你用的是Matlab、Mathematica，大可不必準備，因為象數值分析中有很多函數一般的數學工具是具備的。
10、圖象處理算法
01A中需要你會讀bmp圖象、98美賽A需要你知道三維插值計算，03B要求更高，不但需要編程計算還要進行處理，而數模論文中也有很多圖片需要展示，因此圖象處理就是關鍵，做好這類問題，重要的是把Matlab學好，特別是圖象處理的部分。
模擬退火算法（轉載）
退火概念是80年代初期研究組合優化問題時提出的，該方法解決優化問題
的出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似
性。在對固體物質進行退火處理時，通常是先將它加溫熔化，使其中的粒子
可以自由運動，然后降溫，粒子就逐漸形成低能態的晶體。如果凝結點附近
溫度下降足夠慢，那么固體物質一定能夠形成最低能量的狀態。模擬退火就
是模擬了這一過程，從而求得組合優化問題的全局（近似）最優解。
-------------------------------------------------
發信人: daniel (小丹尼), 信區: AI
標 題: 模擬退火(2)
發信站: 南大小百合信息交換站 (Sun Apr 5 20:03:55 1998), 轉信
設E[{xi}]表示某系統在微觀狀態{xi}（{xi}為一組狀態變量，如速度、
位置等）下的內能，對于給定溫度T，如果系統處于熱平衡狀態，那么
E[{xi}]將服從Boltzmann分布，分布函數為：
f = C(T)e^(-E[{xi}]/kT)
C(T)-1/(e^(-E[{x1}]/kT)+e^(-E[{x2}]/kT)+...+e^(-E[{xn}]/kT))
其中k是Boltzmann常數。
T下降將導致內能E下降，如果T下降速度足夠慢，那么系統就可以保持熱
平衡，使其內能在該溫度下達到最低值。當T=0（開氏溫度）時，內能將達到
最小值。這樣的降溫過程就是退火過程。
-------------------------------------------------
發信人: daniel (小丹尼), 信區: AI
標 題: 模擬退火(3)
發信站: 南大小百合信息交換站 (Sun Apr 5 20:04:45 1998), 轉信
在退火過程中經常要用Metropolis抽樣，它可以用來模擬溫度T下系統的
熱平衡。
隨機選一初始狀態{xi}， 然后隨機地給系統加一個擾動{delta xi},則
內能增量為：
delta E = E[{xi+delta xi}] - E[{xi}]
如果delta E<0，那么這個擾動就將被接受，否則該擾動將按概率
e^(-delta E/kT) 被接受。如果擾動被接受，那么就用{xi+delta xi}代替
原來的{xi}；否則就產生一個新的擾動......
如此反復，則{xi}將逐漸滿足前述Boltzmann分布。
如果讓T從一個足夠大的值逐漸下降，對于每個T都用Metropolis抽樣使
系統熱平衡，那么到T=0時，就實現了模擬退火，E[{xi}]達到最小值。
-------------------------------------------------
發信人: daniel (小丹尼), 信區: AI
標 題: 模擬退火(4)
發信站: 南大小百合信息交換站 (Sun Apr 5 20:05:19 1998), 轉信
計算機實現模擬退火的思想是：將每種可能的組合狀態作為{xi}，E作為
目標函數，T作為控制參數，令T逐漸減小為0，從而得到目標函數最優值。
基本步驟為：
初始化：對初始狀態{xi}，取初始值T(0)，計算目標函數E[{xi}]；
1. 產生隨機擾動，計算delta E = E[{xi+delta xi}] - E[{xi}]
2. 若delta E<0, goto 4,否則產生[0，1]上的一個均勻分布隨機數y；
3. 若e^(-E/T)<=y，goto 1 ；
4. 用{xi+delta xi}代替{xi},E+delta E代替E;
5. 檢驗Metropolis抽樣是否穩定，若不穩定，goto 1;
6. T減小；
7. 是否滿足目標，是則結束，否則goto 1。
-------------------------------------------------
發信人: daniel (小丹尼), 信區: AI
標 題: 模擬退火(5)
發信站: 南大小百合信息交換站 (Sun Apr 5 20:05:41 1998), 轉信
模擬退火是否能達到E的最小值決定于T(0)是否足夠大，和T是否下降得
足夠慢，以及對于每個T，Metropolis抽樣是否穩定。
模擬退火的典型特征是除了接受目標函數的改進外，還接受一個衰減極限，
當T較大時，接受較大的衰減，當T逐漸減小時，接受較小的衰減，當T為0
時，就不再接受衰減。這一特征意味著模擬退火與局部搜索相反，它能避開
局部極小，并且還保持了局部搜索的通用性和簡單性。
值得注意的是，當T為0時，模擬退火就成為局部搜索的一個特例