動(dòng)態(tài)規(guī)劃算法在實(shí)際工程中的應(yīng)用,職稱論文

動(dòng)態(tài)規(guī)劃算法在實(shí)際工程中的應(yīng)用,職稱論文內(nèi)容摘要：本文闡述了動(dòng)態(tài)規(guī)劃法的原理、解決思路和解決步驟，同時(shí)列舉了動(dòng)態(tài)規(guī)劃法怎樣解決計(jì)算機(jī)專業(yè)常出現(xiàn)的多段圖的最短途徑問(wèn)題、資源分配問(wèn)題以及背包問(wèn)題，進(jìn)而結(jié)合動(dòng)態(tài)規(guī)劃法的數(shù)學(xué)思想和解決步驟分析其在實(shí)際工程中的應(yīng)用，為實(shí)際生活生產(chǎn)的決策問(wèn)題提供理論根據(jù)。本文關(guān)鍵詞語(yǔ)：動(dòng)態(tài)規(guī)劃算法；工程；計(jì)算機(jī)語(yǔ)言；目錄1動(dòng)態(tài)規(guī)劃法原理概述..................................12解動(dòng)態(tài)規(guī)劃法的基本方式方法..................................22.1解決思路..................................32.2解決步驟..................................33動(dòng)態(tài)規(guī)劃法的應(yīng)用..................................43.1多段圖的最短途徑問(wèn)題..................................53.2動(dòng)態(tài)規(guī)劃算法在工程中的應(yīng)用..................................54結(jié)束語(yǔ)..................................6文內(nèi)圖表..................................7圖1..................................7以下為參考文獻(xiàn)..................................8動(dòng)態(tài)規(guī)劃算法最早提出于20世紀(jì)50年代，由美國(guó)數(shù)學(xué)家提出，最初是為了優(yōu)化簡(jiǎn)單的多階段生產(chǎn)決策問(wèn)題，其數(shù)學(xué)思想的本質(zhì)是將復(fù)雜的多階段問(wèn)題分割成為一系列的單階段問(wèn)題，進(jìn)而逐個(gè)分析單個(gè)階段，確定各階段的關(guān)系，最終分析出多階段問(wèn)題的最優(yōu)方案，即對(duì)實(shí)際生產(chǎn)多階段問(wèn)題構(gòu)成動(dòng)態(tài)規(guī)劃思維，通俗來(lái)講，動(dòng)態(tài)規(guī)劃法具有實(shí)時(shí)性，根據(jù)前一階段動(dòng)態(tài)分析下一階段的最優(yōu)途徑法，動(dòng)態(tài)規(guī)劃法不僅能夠正確分析當(dāng)下階段，同時(shí)也能結(jié)合各階段的條件合理判定最優(yōu)方案，動(dòng)態(tài)規(guī)劃法以其高效性、簡(jiǎn)化性等優(yōu)點(diǎn)被廣泛應(yīng)用于各類生產(chǎn)調(diào)度、優(yōu)化控制等問(wèn)題。1動(dòng)態(tài)規(guī)劃法原理概述動(dòng)態(tài)規(guī)劃算法的本質(zhì)是階段拆分，將復(fù)雜的多階段和多條件拆分為單階段問(wèn)題，結(jié)合各階段條件狀態(tài)對(duì)其進(jìn)行合理的定義，明確各階段之間的關(guān)系，使得當(dāng)下階段的問(wèn)題能夠結(jié)合當(dāng)下條件和下一階段的實(shí)際情況合理選擇下一階段的途徑。動(dòng)態(tài)規(guī)劃的數(shù)學(xué)思維與遞推思維類似，均是為了著重解決重疊子問(wèn)題和最優(yōu)子構(gòu)造選擇問(wèn)題而設(shè)計(jì)的數(shù)學(xué)算法，其在數(shù)學(xué)、計(jì)算機(jī)學(xué)、經(jīng)濟(jì)學(xué)以及生產(chǎn)調(diào)度中應(yīng)用極為廣泛，計(jì)算機(jī)學(xué)中主要通太多種計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)數(shù)學(xué)算法，相對(duì)于傳統(tǒng)的整體規(guī)劃法能極大程度節(jié)約算法調(diào)度的時(shí)間和效率。不同于排序算法或二叉樹(shù)前序、后序、中序等遍歷算法固有的分析范式，能夠根據(jù)既定算法進(jìn)行問(wèn)題處理，而動(dòng)態(tài)規(guī)劃算法的重點(diǎn)是分析，即便存在固有算法，在實(shí)際問(wèn)題決策中仍然需要結(jié)合各階段條件和狀態(tài)動(dòng)態(tài)分析下一階段的途徑選擇，僅依靠其數(shù)學(xué)思想去解決實(shí)際問(wèn)題是遠(yuǎn)遠(yuǎn)不夠的，更重要的是合理構(gòu)造動(dòng)態(tài)規(guī)劃算法所需形式，進(jìn)而結(jié)合動(dòng)態(tài)規(guī)劃算法的思想才能解決實(shí)際調(diào)度問(wèn)題。形如：初始狀態(tài)│決策1││決策2││決策n│結(jié)束狀態(tài)，動(dòng)態(tài)規(guī)劃法的基本思想就是將復(fù)雜問(wèn)題分為若干子問(wèn)題，子問(wèn)題之間是互相關(guān)聯(lián)的，最終構(gòu)成一條最優(yōu)化的解決方式。動(dòng)態(tài)規(guī)劃算法在各子階段都需要做出相應(yīng)的決策，確保途徑規(guī)劃的整體經(jīng)過(guò)都到達(dá)最優(yōu)化，子階段的決策根據(jù)當(dāng)下階段的狀態(tài)，當(dāng)下階段的狀態(tài)可能由前一階段生成，是前一狀態(tài)的總結(jié)，但前一階段的狀態(tài)并不會(huì)影響當(dāng)下?tīng)顟B(tài)的下一狀態(tài)，即歷史無(wú)關(guān)性，歷史性狀態(tài)只能決定下一階段的狀態(tài)，并不會(huì)影響將來(lái)階段的狀態(tài)，階段3的決策只依靠階段2的輸出狀態(tài)，與狀態(tài)1無(wú)關(guān)。各階段決策的總體稱為決策序列，決策序列即最優(yōu)的解決方案，多決策經(jīng)過(guò)即將一個(gè)具有多種分支途徑或階段的復(fù)雜問(wèn)題拆分成為前后相關(guān)且具有鏈狀構(gòu)造的子階段。2解動(dòng)態(tài)規(guī)劃法的基本方式方法2.1解決思路圖1動(dòng)態(tài)規(guī)劃相比于樸素算法解決了重復(fù)子問(wèn)題，動(dòng)態(tài)規(guī)劃算法對(duì)任一子問(wèn)題都只解決一次，其需要通過(guò)計(jì)算機(jī)的二維數(shù)組保存重疊子問(wèn)題的狀態(tài)和階段，二維數(shù)組的引入能夠有效避免子階段重復(fù)運(yùn)算的問(wèn)題。因而，動(dòng)態(tài)規(guī)劃算法多依靠計(jì)算機(jī)學(xué)相關(guān)語(yǔ)言實(shí)現(xiàn)。其解決步驟主要分為將實(shí)際問(wèn)題拆分為子階段、根據(jù)實(shí)際情況定義問(wèn)題狀態(tài)和狀態(tài)關(guān)系。2.1.1實(shí)際問(wèn)題分割從生產(chǎn)問(wèn)題的實(shí)際出發(fā)分析問(wèn)題，將其分為若干子階段處理分析，子階段的劃分需要結(jié)合實(shí)際，注意子問(wèn)題之間的共性，確保能夠通過(guò)遞推或遞歸的方式解決各子問(wèn)題，動(dòng)態(tài)規(guī)劃算法的重要步驟就是分析子問(wèn)題的遞推或遞歸的可能性，遞推或遞歸具有一定的關(guān)聯(lián)性，當(dāng)下子問(wèn)題的決策方式方法應(yīng)該適用于下一子問(wèn)題。動(dòng)態(tài)規(guī)劃算法不僅能夠從前至后推導(dǎo)，可以從后至前推導(dǎo)，因而問(wèn)題的分割也具有多樣性，能夠考慮多方面的分割方式，問(wèn)題能夠分割為大問(wèn)題和小問(wèn)題，分割應(yīng)考慮大問(wèn)題和小問(wèn)題的共有特性，尋找狀態(tài)各子問(wèn)題狀態(tài)轉(zhuǎn)移的規(guī)律，當(dāng)然這需要一定的數(shù)學(xué)思維和經(jīng)歷體驗(yàn)，根據(jù)狀態(tài)轉(zhuǎn)移規(guī)律分析設(shè)計(jì)出合適子問(wèn)題的決策方案。2.1.2定義子問(wèn)題狀態(tài)和狀態(tài)的共性及關(guān)系即確定狀態(tài)轉(zhuǎn)移方程式，類似于數(shù)學(xué)公式的推導(dǎo)，將子問(wèn)題的狀態(tài)進(jìn)行合理有效的量化，使用程序化的方式推導(dǎo)各子問(wèn)題的狀態(tài)，一般多以計(jì)算機(jī)語(yǔ)言表示出狀態(tài)轉(zhuǎn)移公式，計(jì)算機(jī)語(yǔ)言相較于數(shù)學(xué)能夠表示出抽象的狀態(tài)轉(zhuǎn)移公式，有助于推導(dǎo)狀態(tài)的共性和轉(zhuǎn)移方式。因而，動(dòng)態(tài)規(guī)劃算法多使用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)，其數(shù)學(xué)思想和方式方法也成為近年來(lái)互聯(lián)網(wǎng)企業(yè)機(jī)試考察的重點(diǎn)和難點(diǎn)。其實(shí)，動(dòng)態(tài)規(guī)劃算法的原理和思想與分治算法有異曲同工之處，分治法同樣是拆分復(fù)雜問(wèn)題，將其分解為若干同類型的子問(wèn)題，但分治法與動(dòng)態(tài)規(guī)劃算法不同的是歷史無(wú)關(guān)性，動(dòng)態(tài)規(guī)劃法的下一子階段狀態(tài)與決策與當(dāng)下階段的之前階段和狀態(tài)無(wú)關(guān)，而分治法則依靠于之前階段決策出的最優(yōu)值。2.2解決步驟動(dòng)態(tài)規(guī)劃算法的整體步驟可分為如下階段：2.2.1分析最優(yōu)解的性質(zhì)，并刻畫(huà)其構(gòu)造特征首先需要全面分析實(shí)際問(wèn)題，其能否合適使用動(dòng)態(tài)規(guī)劃算法求解，動(dòng)態(tài)規(guī)劃法使用于生產(chǎn)調(diào)度、途徑規(guī)劃等實(shí)際問(wèn)題，因而分析經(jīng)過(guò)需要總結(jié)出問(wèn)題的構(gòu)造特征，通過(guò)拆分算法將問(wèn)題簡(jiǎn)單化，分析各子問(wèn)題的共性，這也是動(dòng)態(tài)規(guī)劃算法的首要步驟，確定子問(wèn)題共性是分析最優(yōu)質(zhì)的基礎(chǔ)。2.2.2遞歸的定義最優(yōu)解子問(wèn)題的共性是為了使各問(wèn)題都能知足遞歸或遞推法的決策方式，遞歸遞推方式能否適用是規(guī)劃算法拆分的最終目的也是動(dòng)態(tài)規(guī)劃算法的核心，當(dāng)然動(dòng)態(tài)規(guī)劃法與二叉樹(shù)遍歷算法的區(qū)別也在于此，二叉樹(shù)遍歷算法是固有范式的算法思想，知足條件的二叉樹(shù)都可使用遍歷算法查找，而動(dòng)態(tài)規(guī)劃算法則不同，為并不存在固有范式進(jìn)行最優(yōu)解計(jì)算，決策經(jīng)過(guò)是通過(guò)子問(wèn)題的共性進(jìn)行合理的遞推和遞歸算法。2.2.3以自底向上或自頂向下的記憶化方式〔備忘錄法〕計(jì)算出最優(yōu)值動(dòng)態(tài)規(guī)劃算法的最優(yōu)值能夠自底向上可以自頂向下決策，不同方向的決策經(jīng)過(guò)如出一轍，都是利用遞歸算法決策當(dāng)下階段的最優(yōu)值，實(shí)際生產(chǎn)問(wèn)題中多采用自頂向下的決策經(jīng)過(guò)。不斷的遞歸決策出每個(gè)子問(wèn)題的最優(yōu)值，在頂端或底端決策的結(jié)果就是整個(gè)問(wèn)題的最優(yōu)值。3動(dòng)態(tài)規(guī)劃法的應(yīng)用3.1多段圖的最短途徑問(wèn)題階段：如此圖1所示，將整體階段劃分為12個(gè)子階段。狀態(tài)：每個(gè)子階段到下一子階段都有若干個(gè)可供選擇的途徑，途徑的判定需要結(jié)合輸入的狀態(tài)。決策：根據(jù)輸入狀態(tài)判定當(dāng)下子問(wèn)題應(yīng)進(jìn)行的下一步子問(wèn)題，即最優(yōu)值的決策。決策必須知足計(jì)算機(jī)語(yǔ)言表示出的方程式，即遞歸算法的本質(zhì)，方程式也同樣適用于各子問(wèn)題。如多段圖最短途徑的算法方程式為：規(guī)劃方程：f〔k〕表示狀態(tài)k到終點(diǎn)狀態(tài)的最短距離。初始條件：f〔k〕=0;方程：f〔k-1〕=min{f〔k〕+W〔k-1,k〕}華而不實(shí)W〔k-1,k〕表示狀態(tài)k-1到狀態(tài)k的距離。3.2動(dòng)態(tài)規(guī)劃算法在工程中的應(yīng)用動(dòng)態(tài)規(guī)劃算法已經(jīng)被廣泛應(yīng)用于地鐵修建、人流量疏通、水電資源分配等實(shí)際工程應(yīng)用中，文章選取某市的地鐵修建問(wèn)題分析動(dòng)態(tài)規(guī)劃算法在實(shí)際工程中的應(yīng)用。假設(shè)某市有n個(gè)交通線，華而不實(shí)1號(hào)和n號(hào)非常重要，為了加強(qiáng)運(yùn)輸能力，某市決定在1號(hào)到n號(hào)樞紐間修建一條地鐵。地鐵由很多段隧道組成，每段隧道連接兩個(gè)交通樞紐。經(jīng)過(guò)勘探，有m段隧道作為候選，兩個(gè)交通樞紐之間最多只要一條候選的隧道，沒(méi)有隧道兩端連接著同一個(gè)交通樞紐。如今有n家隧道施工的公司，每段候選的隧道只能由一個(gè)公司施工，每家公司施工需要的天數(shù)一致。而每家公司最多只能修建一條候選隧道。所有公司同時(shí)開(kāi)場(chǎng)施工?；诖藢?shí)際工程問(wèn)題，怎樣選擇最優(yōu)方案實(shí)現(xiàn)最少天數(shù)內(nèi)完成整條地鐵修建。工程的資源分配問(wèn)題已經(jīng)簡(jiǎn)化了問(wèn)題拆分步驟，初始化已經(jīng)將問(wèn)題分解為資源和生產(chǎn)，即階段和狀態(tài)問(wèn)題，因而上述的工程問(wèn)題中階段即生產(chǎn)間，狀態(tài)即條件，需要在生產(chǎn)設(shè)備總數(shù)一定的情況下求解能夠產(chǎn)生最大利潤(rùn)的分配方式，這就是最優(yōu)化的問(wèn)題。又由于在當(dāng)下設(shè)備分配選擇中都跟前面已經(jīng)做出的選擇有關(guān)，具有一定的重疊性問(wèn)題，類似于這種子問(wèn)題具有重疊性的最優(yōu)化問(wèn)題求解，動(dòng)態(tài)規(guī)劃占有很大的優(yōu)勢(shì)。首先確定交通樞紐的數(shù)量和候選隧道的數(shù)量，總數(shù)范圍內(nèi)樞紐a和樞紐b之間能夠修建一條隧道，需要時(shí)間為dist[i]天。那么修建整條地鐵所需總數(shù)最小的算法思想如下。第1步：從第一個(gè)樞紐開(kāi)場(chǎng)，找到與其鄰接的點(diǎn)：1,2,3,更新dist[]數(shù)組，因0不與4鄰接，故dist[4]為正無(wú)窮。在dist[]中找到最小值，其頂點(diǎn)為2,即此時(shí)已找到0到2的最短路。第2步：從2開(kāi)場(chǎng)，繼續(xù)更新dist[]數(shù)組：2與1不鄰接，不更新；2與3鄰接，因023比dist[3]大，故不更新dist[3];2與4鄰接，因024比dist[4]小，故更新dist[4]為4.在dist[]中找到最小值，其頂點(diǎn)為3,即此時(shí)又找到0到3的最短路。第3步：從3開(kāi)場(chǎng)，繼續(xù)更新dist[]數(shù)組：3與1鄰接，因031比dist[1]小，更新dist[1]為5;3與4鄰接，因034比dist[4]大，故不更新。在dist[]中找到最小值，其頂點(diǎn)為4,即此時(shí)又找到0到4的最短路。第4步：從4開(kāi)場(chǎng)，繼續(xù)更新dist[]數(shù)組：4與1不鄰接，不更新。在dist[]中找到最小值，其頂點(diǎn)為1,即此時(shí)又找到0到1的最短路。第5步：所有點(diǎn)都已找到，停止。根據(jù)上面的證明，動(dòng)態(tài)規(guī)劃算法每次循環(huán)都能夠確定一個(gè)頂點(diǎn)的最短途徑，故程序需要循環(huán)n-1次?？偨Y(jié)：當(dāng)我們通過(guò)分析得到相應(yīng)的動(dòng)態(tài)規(guī)劃狀態(tài)方程時(shí)，用其求解問(wèn)題的效率會(huì)優(yōu)于普通的理論計(jì)算。4結(jié)束語(yǔ)總之，動(dòng)態(tài)規(guī)劃算法在解決多階段最優(yōu)決策問(wèn)題上具有很大的優(yōu)勢(shì)，能夠有效的結(jié)合工程調(diào)度和資源分配問(wèn)題，且比照于遞歸算法，動(dòng)態(tài)規(guī)劃的算法效率更高層次。當(dāng)然它也具有一定的局限性，由于每個(gè)問(wèn)題對(duì)應(yīng)的模型不同，要找到其相應(yīng)的狀態(tài)轉(zhuǎn)移方程并不是一件容易的