《數(shù)學(xué)建模十類常用算法及歷年試題分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)建模十類常用算法及歷年試題分析.ppt（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

數(shù)學(xué)建模十類常用算法 雄鷹 1 蒙特卡羅算法 該算法又稱隨機(jī)性模擬算法 是通過(guò)計(jì)算機(jī)仿真來(lái)解決問(wèn)題的算法 同時(shí)可以通過(guò)模擬來(lái)檢驗(yàn)自己模型的正確性 幾乎是比賽時(shí)必用的方法 2 數(shù)據(jù)擬合 參數(shù)估計(jì) 插值等數(shù)據(jù)處理算法 比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理 而處理數(shù)據(jù)的關(guān)鍵就在于這些算法 通常使用MATLAB作為工具 3 線性規(guī)劃 整數(shù)規(guī)劃 多元規(guī)劃 二次規(guī)劃等規(guī)劃類算法 建模競(jìng)賽大多數(shù)問(wèn)題屬于最優(yōu)化問(wèn)題 很多時(shí)候這些問(wèn)題可以用數(shù)學(xué)規(guī)劃算法來(lái)描述 通常使用Lindo Lingo軟件求解 4 圖論算法 這類算法可以分為很多種 包括最短路 網(wǎng)絡(luò)流 二分圖等算法 涉及到圖論的問(wèn)題可以用這些方法解決 需要認(rèn)真準(zhǔn)備 5 動(dòng)態(tài)規(guī)劃 回溯搜索 分治算法 分支定界等計(jì)算機(jī)算法 這些算法是算法設(shè)計(jì)中比較常用的方法 競(jìng)賽中很多場(chǎng)合會(huì)用到 6 最優(yōu)化理論的三大非經(jīng)典算法 模擬退火算法 神經(jīng)網(wǎng)絡(luò)算法 遺傳算法 這些問(wèn)題是用來(lái)解決一些較困難的最優(yōu)化問(wèn)題的 對(duì)于有些問(wèn)題非常有幫助 但是算法的實(shí)現(xiàn)比較困難 需慎重使用 7 網(wǎng)格算法和窮舉法 兩者都是暴力搜索最優(yōu)點(diǎn)的算法 在很多競(jìng)賽題中有應(yīng)用 當(dāng)重點(diǎn)討論模型本身而輕視算法的時(shí)候 可以使用這種暴力方案 最好使用一些高級(jí)語(yǔ)言作為編程工具 8 一些連續(xù)數(shù)據(jù)離散化方法 很多問(wèn)題都是實(shí)際來(lái)的 數(shù)據(jù)可以是連續(xù)的 而計(jì)算機(jī)只能處理離散的數(shù)據(jù) 因此將其離散化后進(jìn)行差分代替微分 求和代替積分等思想是非常重要的 9 數(shù)值分析算法 如果在比賽中采用高級(jí)語(yǔ)言進(jìn)行編程的話 那些數(shù)值分析中常用的算法比如方程組求解 矩陣運(yùn)算 函數(shù)積分等算法就需要額外編寫庫(kù)函數(shù)進(jìn)行調(diào)用 10 圖象處理算法 賽題中有一類問(wèn)題與圖形有關(guān) 即使問(wèn)題與圖形無(wú)關(guān) 論文中也會(huì)需要圖片來(lái)說(shuō)明問(wèn)題 這些圖形如何展示以及如何處理就是需要解決的問(wèn)題 通常使用MATLAB進(jìn)行處理 2十類算法的詳細(xì)說(shuō)明 以下將結(jié)合歷年的競(jìng)賽題 對(duì)這十類算法進(jìn)行詳細(xì)地說(shuō)明 2 1蒙特卡羅算法 大多數(shù)建模賽題中都離不開(kāi)計(jì)算機(jī)仿真 隨機(jī)性模擬是非常常見(jiàn)的算法之一 舉個(gè)例子就是97年的A題 每個(gè)零件都有自己的標(biāo)定值 也都有自己的容差等級(jí) 而求解最優(yōu)的組合方案將要面對(duì)著的是一個(gè)極其復(fù)雜的公式和108種容差選取方案 根本不可能去求解析解 那如何去找到最優(yōu)的方案呢 隨機(jī)性模擬搜索最優(yōu)方案就是其中的一種方法 在每個(gè)零件可行的區(qū)間中按照正態(tài)分布隨機(jī)的選取一個(gè)標(biāo)定值和選取一個(gè)容差值作為一種方案 然后通過(guò)蒙特卡羅算法仿真出大量的方案 從中選取一個(gè)最佳的 另一個(gè)例子就是去年y的彩票第二問(wèn) 要求設(shè)計(jì)一種更好的方案 首先方案的優(yōu)劣取決于很多復(fù)雜的因素 同樣不可能刻畫出一個(gè)模型進(jìn)行求解 只能靠隨機(jī)仿真模擬 2 2數(shù)據(jù)擬合 參數(shù)估計(jì) 插值等算法 數(shù)據(jù)擬合在很多賽題中有應(yīng)用 與圖形處理有關(guān)的問(wèn)題很多與擬合有關(guān)系 一個(gè)例子就是98年美國(guó)賽A題 生物組織切片的三維插值處理 94年A題逢山開(kāi)路 山體海拔高度的插值計(jì)算 還有吵的沸沸揚(yáng)揚(yáng)可能會(huì)考的 非典 問(wèn)題也要用到數(shù)據(jù)擬合算法 觀察數(shù)據(jù)的走向進(jìn)行處理 此類問(wèn)題在MATLAB中有很多現(xiàn)成的函數(shù)可以調(diào)用 熟悉MATLAB 這些方法都能游刃有余的用好 2 3規(guī)劃類問(wèn)題算法 競(jìng)賽中很多問(wèn)題都和數(shù)學(xué)規(guī)劃有關(guān) 可以說(shuō)不少的模型都可以歸結(jié)為一組不等式作為約束條件 幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問(wèn)題 遇到這類問(wèn)題 求解就是關(guān)鍵了 比如98年B題 用很多不等式完全可以把問(wèn)題刻畫清楚 因此列舉出規(guī)劃后用Lindo Lingo等軟件來(lái)進(jìn)行解決比較方便 所以還需要熟悉這兩個(gè)軟件 2 4圖論問(wèn)題 98年B題 00年B題 95年鎖具裝箱等問(wèn)題體現(xiàn)了圖論問(wèn)題的重要性 這類問(wèn)題算法有很多 包括 Dijkstra Floyd Prim Bellman Ford 最大流 二分匹配等問(wèn)題 每一個(gè)算法都應(yīng)該實(shí)現(xiàn)一遍 否則到比賽時(shí)再寫就晚了 2 5計(jì)算機(jī)算法設(shè)計(jì)中的問(wèn)題 計(jì)算機(jī)算法設(shè)計(jì)包括很多內(nèi)容 動(dòng)態(tài)規(guī)劃 回溯搜索 分治算法 分支定界 比如92年B題用分枝定界法 97年B題是典型的動(dòng)態(tài)規(guī)劃問(wèn)題 此外98年B題體現(xiàn)了分治算法 這方面問(wèn)題和ACM程序設(shè)計(jì)競(jìng)賽中的問(wèn)題類似 推薦看一下 計(jì)算機(jī)算法設(shè)計(jì)與分析 電子工業(yè)出版社 等與計(jì)算機(jī)算法有關(guān)的書 2 6最優(yōu)化理論的三大非經(jīng)典算法 這十幾年來(lái)最優(yōu)化理論有了飛速發(fā)展 模擬退火法 神經(jīng)網(wǎng)絡(luò) 遺傳算法這三類算法發(fā)展很快 近幾年的賽題越來(lái)越復(fù)雜 很多問(wèn)題沒(méi)有什么很好的模型可以借鑒 于是這三類算法很多時(shí)候可以派上用場(chǎng) 比如 97年A題的模擬退火算法 00年B題的神經(jīng)網(wǎng)絡(luò)分類算法 象01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò) 還有美國(guó)競(jìng)賽89年A題也和BP算法有關(guān)系 當(dāng)時(shí)是86年剛提出BP算法 89年就考了 說(shuō)明賽題可能是當(dāng)今前沿科技的抽象體現(xiàn) 03年B題伽馬刀問(wèn)題也是目前研究的課題 目前算法最佳的是遺傳算法 2 7網(wǎng)格算法和窮舉算法 網(wǎng)格算法和窮舉法一樣 只是網(wǎng)格法是連續(xù)問(wèn)題的窮舉 比如要求在N個(gè)變量情況下的最優(yōu)化問(wèn)題 那么對(duì)這些變量可取的空間進(jìn)行采點(diǎn) 比如在 a b 區(qū)間內(nèi)取M 1個(gè)點(diǎn) 就是那么這樣循環(huán)就需要進(jìn)行次運(yùn)算 所以計(jì)算量很大 比如97年A題 99年B題都可以用網(wǎng)格法搜索 這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行 還有要用高級(jí)語(yǔ)言來(lái)做 最好不要用MATLAB做網(wǎng)格 否則會(huì)算很久的 窮舉法大家都熟悉 就不說(shuō)了 2 8一些連續(xù)數(shù)據(jù)離散化的方法 大部分物理問(wèn)題的編程解決 都和這種方法有一定的聯(lián)系 物理問(wèn)題是反映我們生活在一個(gè)連續(xù)的世界中 計(jì)算機(jī)只能處理離散的量 所以需要對(duì)連續(xù)量進(jìn)行離散處理 這種方法應(yīng)用很廣 而且和上面的很多算法有關(guān) 事實(shí)上 網(wǎng)格算法 蒙特卡羅算法 模擬退火都用了這個(gè)思想 2 9數(shù)值分析算法 這類算法是針對(duì)高級(jí)語(yǔ)言而專門設(shè)的 如果你用的是MATLAB Mathematica 大可不必準(zhǔn)備 因?yàn)橄髷?shù)值分析中有很多函數(shù)一般的數(shù)學(xué)軟件是具備的 01年A題中需要你會(huì)讀BMP圖象 美國(guó)賽98年A題需要你知道三維插值計(jì)算 03年B題要求更高 不但需要編程計(jì)算還要進(jìn)行處理 而數(shù)模論文中也有很多圖片需要展示 因此圖象處理就是關(guān)鍵 做好這類問(wèn)題 重要的是把MATLAB學(xué)好 特別是圖象處理的部分 2 10圖象處理算法 thanks