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

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

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

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