動(dòng)態(tài)規(guī)劃算法應(yīng)用及其在時(shí)間效率上的優(yōu)化.pdf

1、算法設(shè)計(jì)是軟件設(shè)計(jì)的靈魂內(nèi)容，動(dòng)態(tài)規(guī)劃作為相對(duì)成熟的算法設(shè)計(jì)技術(shù)，不斷地被運(yùn)用到工農(nóng)業(yè)生產(chǎn)、經(jīng)濟(jì)、軍事、工程技術(shù)等很多方面，顯示出其高效、實(shí)用的性能和寬闊的應(yīng)用前景。本文對(duì)動(dòng)態(tài)規(guī)劃所涉及的諸多方面進(jìn)行了深入的研究，通過大量的程序設(shè)計(jì)實(shí)例闡述了包括動(dòng)態(tài)規(guī)劃的理論基礎(chǔ)、實(shí)際應(yīng)用、優(yōu)化方法在內(nèi)的幾大方面的問題。具體包括： 一、從動(dòng)態(tài)規(guī)劃的本質(zhì)入手，介紹了多階段決策問題、階段與狀態(tài)、決策與策略、最優(yōu)化原理與無后效性、最優(yōu)指標(biāo)函數(shù)和規(guī)劃方

2、程等一些專有名詞的定義；利用一些常見的實(shí)例闡述了動(dòng)態(tài)規(guī)劃在設(shè)計(jì)與實(shí)現(xiàn)時(shí)的多樣性、模式性和技巧性等特點(diǎn)；通過與一些常見算法的比較，講解了動(dòng)態(tài)規(guī)劃與這些算法的區(qū)別和聯(lián)系，突出了使用動(dòng)態(tài)規(guī)劃時(shí)的最優(yōu)化、高效率和高消費(fèi)等特性。 二、從三個(gè)具體問題的解決過程中可以看出，動(dòng)態(tài)規(guī)劃是必不可少的有力工具。通過問題描述、樣例分析、算法設(shè)計(jì)、問題實(shí)現(xiàn)、測(cè)試結(jié)果等幾個(gè)步驟詳細(xì)討論了動(dòng)態(tài)規(guī)劃在應(yīng)用中的實(shí)現(xiàn)過程和思考方法，體現(xiàn)出在應(yīng)用中相應(yīng)的實(shí)踐指導(dǎo)意義

3、。 三、鑒于動(dòng)態(tài)規(guī)劃在簡(jiǎn)單設(shè)計(jì)后還存在很大的時(shí)間冗余，從構(gòu)成其時(shí)間復(fù)雜度的三個(gè)方面：狀態(tài)總數(shù)、每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)、每次狀態(tài)轉(zhuǎn)移的時(shí)間進(jìn)行優(yōu)化，使得動(dòng)態(tài)規(guī)劃在時(shí)間效率上得到了進(jìn)一步的提升，以期面對(duì)并解決更大數(shù)據(jù)規(guī)模的問題。不僅給出了優(yōu)化的理論依據(jù)和具體方法，而且還給出了五個(gè)引用實(shí)例在優(yōu)化前后的實(shí)驗(yàn)運(yùn)行對(duì)比結(jié)果。 最后，總結(jié)全文，分析了動(dòng)態(tài)規(guī)劃的應(yīng)用和優(yōu)化在面對(duì)不同問題時(shí)需要進(jìn)一步完善的地方，并指出了今后工作的研究方向。