十類算法的詳細說明

1、2.1算法大多數(shù)建模賽題中都離不開計算機仿真，隨機性模擬是非常常見的算法之一。舉個例子就是 97 年的 A 題，每個零件都有自己的標定值，也都有自己的容差等級，而求解最優(yōu)的組合方案將要面對著的是一個極其復雜的公式和 108 種容差選取方案，根本不可能去求解，那如何去找到最優(yōu)的方案呢？隨機性模擬搜索最優(yōu)方案就是其中的法，在每個零件可行的區(qū)間中按照正態(tài)分布隨機的選取一個標定值和選取一個容差值作為案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個最佳的。另一個例子就是去年y 的第二問，要求設計一種更好的方案，首先方案的優(yōu)劣取決于很多復雜的，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。2

2、.2 數(shù)據(jù)擬合、參數(shù)估計、插值等算法數(shù)據(jù)擬合在很多賽題中有應用，與圖形處理有關很多與擬合有關系，一個例子就是 98 年賽A 題，生物組織切片的三維插值處理，94 年A 題逢山開路，山體海拔高度的插值計算，還有吵的沸沸揚揚可能會考的“”問題也要用到數(shù)據(jù)擬合算法，觀察數(shù)據(jù)的進行處理。此類問題在中有很多現(xiàn)成的函數(shù)可以調用，熟悉，這些方法都能游刃有余的用好。2.3 規(guī)劃類問題算法競賽中很多問題都和數(shù)學規(guī)劃有關，可以說不少的模型都可以歸結為一組不等式作為約束條件、幾個函數(shù)表達式作為目標函數(shù)的問題，遇到這類問題，求解就是關鍵了，比如 98 年 B 題，用很多不等式完全可以把問題刻畫清楚，因此列舉出規(guī)劃后用

3、 Lindo、Lingo 等來進行解決比較方便，所以還需要熟悉這兩個軟件。2.4 圖論問題98 年B 題、00 年B 題、95 年鎖具裝箱等問題體現(xiàn)了圖論問題的重要性，這類問題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。每一個算法都應該實現(xiàn)一遍，否則到比賽時再寫就晚了。2.5 計算機算法設計中計算機算法設計包括很多內容：動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界。比如 92 年 B 題用分枝定界法，97 年 B 題是典型的動態(tài)規(guī)劃問題，此外 98年 B 題體現(xiàn)了分治算法。這方面問題和ACM 程序設計競賽中類似，看一下計算機算法設計與分

4、析（電子工業(yè)）等與計算機算法有關的書。2.6 最優(yōu)化理論的三大非經(jīng)典算法這十幾年來最優(yōu)化理論有了飛速發(fā)展，模擬退火法、神經(jīng)網(wǎng)絡、遺傳算法這三類算法發(fā)展很快。近幾年的賽題越來越復雜，很多問題沒很好的模型可以借鑒，于是這三類算法很多時候可以派上用場，比如：97 年 A 題的模擬退火算法，00 年 B 題的神經(jīng)網(wǎng)絡分類算法，象 01 年 B 題這種難題也可以使用神經(jīng)網(wǎng)絡，還有競賽 89 年 A 題也和 BP 算法有關系，當時是 86 年剛提出 BP 算法，89 年就考了，說明賽題可能是前沿科技的抽象體現(xiàn)。03 年B 題伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法。2.7 網(wǎng)格算法和窮舉算法

5、網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。比如要求在 N 個變量情況下的最優(yōu)化問題，那么對這些變量可取的空間進行采點，比如在a; b 區(qū)間內取 M +1 個點，就是那么這樣循環(huán)就需要進行 次運算，所以計算量很大。比如 97 年 A題、99 年B 題都可以用網(wǎng)格法搜索，這種方法最好在運算速度較快的計算機中進行，還有要用高級語言來做，最好不要用做網(wǎng)格，否則會算很久的。窮舉法大家都熟悉，就不說了。2.8 一些連續(xù)數(shù)據(jù)離散化的方法大部分物理問題的編程解決，都和這種方法有一定的聯(lián)系。物理問題是反映續(xù)的世界中，計算機只能處理離散的量，所以需要對連續(xù)量進行離散處理。這種方法應用很廣，而且和上面的很多算法有關。事實上，網(wǎng)格算法、算法、模擬退火都用了這個。2.9 數(shù)值分析算法這類算法是針對高級語言而專門設的，如果你用的是、Mathematica，大可不必準備，因為象數(shù)值分析中有很多函數(shù)一般的數(shù)學是具備的。2.10 圖象處理算法01 年A 題中需要你會讀 BMP 圖象賽 98 年 A 題需要你知