古詩詞大全網 - 成語用法 - 什麽是動態規劃?動態規劃的意義是什麽

什麽是動態規劃?動態規劃的意義是什麽

動態規劃(dynamic programming)是運籌學的壹個分支,是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時,提出了著名的最優化原理(principle of optimality),把多階段過程轉化為壹系列單階段問題,利用各階段之間的關系,逐個求解,創立了解決這類過程優化問題的新方法——動態規劃。1957年出版了他的名著《Dynamic Programming》,這是該領域的第壹本著作。

動態規劃壹般可分為線性動規,區域動規,樹形動規,背包動規四類。

舉例:

線性動規:攔截導彈,合唱隊形,挖地雷,建學校,劍客決鬥等;

區域動規:石子合並, 加分二叉樹,統計單詞個數,炮兵布陣等;

樹形動規:貪吃的九頭龍,二分查找樹,聚會的歡樂,數字三角形等;

背包問題:01背包問題,完全背包問題,分組背包問題,二維背包,裝箱問題,

動態規劃問世以來,在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題,用動態規劃方法比用其它方法求解更為方便。

雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題,但是壹些與時間無關的靜態規劃(如線性規劃、非線性規劃),只要人為地引進時間因素,把它視為多階段決策過程,也可以用動態規劃方法方便地求解。

動態規劃程序設計是對解最優化問題的壹種途徑、壹種方法,而不是壹種特殊算法。不像搜索或數值計算那樣,具有壹個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對壹種最優化問題,由於各種問題的性質不同,確定最優解的條件也互不相同,因而動態規劃的設計方法對不同的問題,有各具特色的解題方法,而不存在壹種萬能的動態規劃算法,可以解決各類最優化問題。因此讀者在學習時,除了要對基本概念和方法正確理解外,必須具體問題具體分析處理,以豐富的想象力去建立模型,用創造性的技巧去求解。我們也可以通過對若幹有代表性的問題的動態規劃算法進行分析、討論,逐漸學會並掌握這壹設計方法。