數(shù)學(xué)建模中常用的十種算法課件

數(shù)學(xué)建模中常用的十種算法服從真理，就能征服一切事物數(shù)學(xué)建模中常用的十種算法服從真理，就能征服一切事物1數(shù)學(xué)建模競賽中應(yīng)當(dāng)掌握的十類算法:■1、蒙特卡羅算法(該算法又稱隨機性模擬算法,是通過計算機仿真來解決問題的算法,同時可以通過模擬來檢驗自己模型的正確性,是比賽時必用的方法)2、數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法(比賽中通常會遇到大量的數(shù)據(jù)需要處理,而處理數(shù)據(jù)的關(guān)鍵就在于這些算法,通常使用Matlab作為工具)3、線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題(建模競賽大多數(shù)問題屬于最優(yōu)化問題,很多時候這些問題可以用數(shù)學(xué)規(guī)劃算法來描述,通常使用Lindo、Lingo軟件實現(xiàn))數(shù)學(xué)建模競賽中應(yīng)當(dāng)掌握的十類算法:2■4、圖論算法(這類算法可以分為很多種,包括最短路網(wǎng)絡(luò)流、二分圖等算法,涉及到圖論的問題可以用這些方法解決,需要認(rèn)真準(zhǔn)備)■5、動態(tài)規(guī)劃、回溯搜索、分支定界等計算機算法(這些算法是算法設(shè)計中比較常用的方法,很多場合可以用到競賽中)6、最優(yōu)化理論的三大非經(jīng)典算法:模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法(這些問題是用來解決一些較困難的最優(yōu)化問題的算法,對于有些問題非常有幫助,但是算法的實現(xiàn)比較困難,需慎重使用7、網(wǎng)格算法和窮舉法(網(wǎng)格算法和窮舉法都是暴力搜索最優(yōu)點的算法,在很多競賽題中有應(yīng)用,當(dāng)重點討論模型本身而輕視算法的時候,可以使用這種暴力方案,最好使用一些高級語言作為編程工具)■4、圖論算法(這類算法可以分為很多種,包括最短路3■8、一些連續(xù)離散化方法(很多問題都是實際來的,數(shù)據(jù)可以是連續(xù)的,而計算機只認(rèn)的是離散的數(shù)據(jù),因此將其離散化后進(jìn)行差分代替微分、求和代替積分等思想是非常重要的)■9、數(shù)值分析算法(如果在比賽中采用高級語言進(jìn)行編程的話,那一些數(shù)值分析中常用的算法比如方程組求解、矩陣運算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進(jìn)行調(diào)用)■10、圖象處理算法(賽題中有一類問題與圖形有關(guān),即使與圖形無關(guān),論文中也應(yīng)該要不乏圖片的,這些圖形如何展示以及如何處理就是需要解決的問題,通常使用Matlab進(jìn)行處理)■8、一些連續(xù)離散化方法(很多問題都是實際來的,數(shù)據(jù)4十類算法的詳細(xì)說明1、蒙特卡羅方法(Mc)(Montecarlo)■蒙特卡羅(MoηnteCarlo)方法,或稱計算機隨機模擬方法,是一種基于“隨機數(shù)”的計算方法。這一方法源于美國在第二次世界大戰(zhàn)進(jìn)行研制原子彈的“曼哈頓計劃”該計劃的主持人之一、數(shù)學(xué)家馮·諾伊曼用馳名世界的賭城一摩納哥的Montecarlo一來命名這種方法,為它蒙上了一層神秘色彩。十類算法的詳細(xì)說明5蒙特卡羅方法的基本原理及思想如下■當(dāng)所要求解的問題是某種事件出現(xiàn)的概率,或者是某個隨機變量的期望值時,它們可以通過某種“試驗”的方法,得到這種事件出現(xiàn)的頻率,或者這個隨機變數(shù)的平均值,并用它們作為問題的解。這就是蒙特卡羅方法的基本思想。蒙特卡羅方法通過抓住事物運動的幾何數(shù)量和幾何特征,利用數(shù)學(xué)方法來加以模擬,即進(jìn)行一種數(shù)字模擬實驗。它是以一個概率模型為基礎(chǔ),按照這個模型所描繪的過程,通過模擬實驗的結(jié)果,作為問題的近似解可以把蒙特卡羅解題歸結(jié)為三個主要步驟構(gòu)造或描述概率過程;實現(xiàn)從已知概率分布抽樣;建立各種估計量。蒙特卡羅方法的基本原理及思想如下6例.蒲豐氏問題為了求得圓周率T值,在十九世紀(jì)后期,有很多人作了這樣的試驗:將長為2/的一根針任意投到地面上,用針與一組相間距離為2a(K<a)的平行線相交的頻率代替概率P,再利用準(zhǔn)確的關(guān)系式:P=—求出丌值2l2/N其中N為投計次數(shù),n為針與平行線相交次數(shù)。這就是古典概率論中著名的蒲豐氏問題。例.蒲豐氏問題7一些人進(jìn)行了實驗,其結(jié)果列于下表:□實驗者年份投計次數(shù)π的實驗值沃爾弗(Wol)18505003.1596斯密思(mh)185532043.1553?？怂?Fox)18941203.1419拉查里尼1901134083.1415929lazar一些人進(jìn)行了實驗,其結(jié)果列于下表:□8設(shè)針投到地面上的位置可以用一組參數(shù)(x,日)來描述,x為針中心的坐標(biāo),θ為針與平行線的夾角,如圖所示。任意投針,就是意味著x與θ都是任意取的,但x的范圍限于[0,a],夾角θ的范圍限于[0,丌]。在此情況下,針與平行線相交的數(shù)學(xué)條件是x≤l.sinO針在平行線間的位置設(shè)針投到地面上的位置可以用一組參數(shù)(x,日)來描述,9如何產(chǎn)生任意的(x,0)?x在[0,a]上任意取值表示x在[0,a]上是均勻分布的,其分布密度函數(shù)為0≤xf1(x)「o.其他1/丌,0≤日≤丌類似地,θ的分布密度函數(shù)為:f2()=10,其他因此,產(chǎn)生任意的(x,日)的過程就變成了由f()抽樣x及由f(抽樣θ的過程了。由此得到:7其中51,52均為(0,1)上均勻分布的隨機變量如何產(chǎn)生任意的(x,0)?x在[0,a]上任意取值10每次投針試驗,實際上變成在計算機上從兩個均勻分布的隨機變量中抽樣得到(x,θ),然后定義描述針與平行線相交狀況的隨機變量s(X,O),為1,當(dāng)x≤l·sins(r0,其他如果投針N次,則∑s(x,O1)是針與平行線相交概率P的估計值。事實上,P=』s(x,O)f(x)f()dlemdecsinedx21于是有2lP每次投針試驗,實際上變成在計算機上從兩個均勻分布11數(shù)學(xué)建模中常用的十種算法課件12數(shù)學(xué)建模中常用的十種算法課件13數(shù)學(xué)建模中常用的十種算法課件14數(shù)學(xué)建模中常用的十種算法課件15數(shù)學(xué)建模中常用的十種算法課件16數(shù)學(xué)建模中常用的十種算法課件17數(shù)學(xué)建模中常用的十種算法課件18數(shù)學(xué)建模中常用的十種算法課件19數(shù)學(xué)建模中常用的十種算法課件20數(shù)學(xué)建模中常用的十種算法課件21數(shù)學(xué)建模中常用的十種算法課件22數(shù)學(xué)建模中常用的十種算法課件23數(shù)學(xué)建模中常用的十種算法課件24數(shù)學(xué)建模中常用的十種算法課件25數(shù)學(xué)建模中常用的十種算法課件26數(shù)學(xué)建模中常用的十種算法課件27數(shù)學(xué)建模中常用的十種算法課件28數(shù)學(xué)建模中常用的十種算法課件29數(shù)學(xué)建模中常用的十種算法課件30數(shù)學(xué)建模中常用的十種算法課件31數(shù)學(xué)建模中常用的十種算法課件32數(shù)學(xué)建模中常用的十種算法課件33數(shù)學(xué)建模中常用的十種算法課件34數(shù)學(xué)建模中常用的十種算法課件35數(shù)學(xué)建模中常用的十種算法課件36數(shù)學(xué)建模中常用的十種算法課件37數(shù)學(xué)建模中常用的十種算法課件38數(shù)學(xué)建模中常用的十種算法課件39數(shù)學(xué)建模中常用的十種算法課件40數(shù)學(xué)建模中常用的十種算法課件41數(shù)學(xué)建模中常用的十種算法課件42數(shù)學(xué)建模中常用的十種算法課件43數(shù)學(xué)建模中常用的十種算法課件44數(shù)學(xué)建模中常用的十種算法課件45數(shù)學(xué)建模中常用的十種算法課件46數(shù)學(xué)建模中常用的十種算法課件4751、天下之事常成于困約，而敗于奢靡。——陸