? ? ? ?經過之前的學習，相信大家已經對運籌學的動態(tài)規(guī)劃有了一定的了解，接下來小編將帶你學習新一章的內容，先來看看動態(tài)規(guī)劃的簡單介紹，然后再帶你領略該理論先驅的生平故事！

一、動態(tài)規(guī)劃

?簡 介

? ? ? ?動態(tài)規(guī)劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優(yōu)化的過程。20世紀50年代初，美國數(shù)學家理查德·貝爾曼（英語：Richard Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應用極其廣泛，包括工程技術、經濟、工業(yè)生產、軍事以及自動化控制等領域，并在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統(tǒng)可靠性問題等中取得了顯著的效果。

?基本思想

? ? ? ?動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。

? ? ? ?動態(tài)規(guī)劃針對的是最優(yōu)解問題，它的核心是定義合適的狀態(tài)（滿足最優(yōu)子結構性質和無后效性），找到狀態(tài)轉移方程，由邊界條件即可用遞推解決。它的子問題往往不獨立，可以利用空間換時間來優(yōu)化。有時候狀態(tài)轉移方程實現(xiàn)起來復雜度高，需要優(yōu)化。?

? ? ? ?而提到動態(tài)規(guī)劃，大家經常會將其與分治法混淆，因為兩者的基本思想均是將原問題分解成若干個子問題，先求子問題，然后從子問題的解得到原問題的解。但是兩者具有很多的不同點，如下所示：

△子問題往往不獨立

△自底向上求解

△通常用迭代法求解

○子問題往往相互獨立

○自頂向下求解

○通常用遞歸法求解

發(fā)展應用簡史

●1956年，C.Pontryagin提出了最優(yōu)控制的極大值原理。

●1957年，R.Bellman創(chuàng)立了動態(tài)規(guī)劃方法。

●1969&1971年,Merton最早將動態(tài)規(guī)劃方法運用到最優(yōu)投資與消費問題的求解，以后的許多學者都運用了此方法。

●1973年Johnson等人把動態(tài)規(guī)劃方法和模擬技術結合起來使用,確定聯(lián)臺運用系統(tǒng)的工程規(guī)模取得了成功。

●1982年,曾賽星、李壽聲采用動態(tài)規(guī)劃方法確定內蒙古河套灌區(qū)各種作物的灌水定額及灌水次數(shù)。

●1988年黃強把模糊動態(tài)規(guī)劃方法用于求解水電站水庫長期優(yōu)化調度問題，較隨機動態(tài)規(guī)劃法簡便，計算速度快。

●1989年,曾賽星等采用動態(tài)規(guī)劃方法確定各種作物的灌水定額及灌水次數(shù)。

●1991年，林學鈦等人運用動態(tài)規(guī)劃方法對白龜山水庫進行了優(yōu)化調度。

目前國內的具體應用領域如下圖所示

? ? ? ?簡單了解過動態(tài)規(guī)劃后，想必各位讀者朋友對上文提到的奠基人Bellman先生感到十分好奇。接下來，小編將對這位傳奇人物進行詳細介紹！

二、Richard Bellman的一生

? ? ? ?Richard Bellman，美國數(shù)學家，美國國家科學院院士，動態(tài)規(guī)劃的創(chuàng)始人。1920年8月26日生于紐約布魯克林,1984年3月19日卒于圣莫尼卡。主要生平經歷如下：

?1941年在布魯克林學院畢業(yè)，獲理學士學位；

?1943年在威斯康星大學獲理學碩士學位；

?1946年在普林斯頓大學獲博士學位；

?1946～1948年在普林斯頓大學任助理教授；

?1948～1952年在斯坦福大學任副教授；

?1953～1956年在美國蘭德公司任研究員；

?1956年后在南加利福尼亞大學任數(shù)學教授、電氣工程教授和醫(yī)學教授。

三、所獲榮譽與成就

獎 項

? ? ? ?Bellman因提出動態(tài)規(guī)劃而獲美國數(shù)學會和美國工程數(shù)學與應用數(shù)學會聯(lián)合頒發(fā)的第一屆維納應用數(shù)學獎（1970），卡內基－梅隆大學頒發(fā)的第一屆迪克森科學獎(1970)，美國管理科學研究會和美國運籌學會聯(lián)合頒發(fā)的馮·諾伊曼理論獎(1976)。他在1979年被授予電氣電子工程師協(xié)會獎，由于其在“決策過程和控制系統(tǒng)理論方面的貢獻，特別是動態(tài)規(guī)劃的發(fā)明和應用。”

榮 譽

? ? ? ?1977年Richard Bellman當選為美國藝術與科學研究院院士和美國工程科學院院士。

成 就

? ? ? ?Bellman曾是《數(shù)學分析與應用雜志》及《數(shù)學生物科學雜志》的主編，《科學與工程中的數(shù)學》叢書的主編。已出版30本著作和7本專著，發(fā)表了600多篇研究論文。

? ? ? ? Richard Bellman因在研究多段決策過程中提出動態(tài)規(guī)劃而聞名于世，可以說動態(tài)規(guī)劃的相關理論研究是他的重要成就。接下來，小編就講講貝爾曼和動態(tài)規(guī)劃之間不得不說的故事。

四、Bellman與動態(tài)規(guī)劃的故事

概念引入

? ? ? ?在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線。

Bellman提出的動態(tài)規(guī)劃

? ? ? ?把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產生出來的，故有“動態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃方法。

? ? ? ?1957年Richard Bellman的專著《動態(tài)規(guī)劃》出版后，被迅速譯成俄文、日文、德文和法文，對控制理論界和數(shù)學界有深遠影響。Bellman還把不變嵌入原理應用于理論物理和數(shù)學分析方面，把兩點邊值問題化為初值問題，簡化了問題的分析和求解過程。1955年后Bellman開始研究算法、計算機仿真和人工智能，把建模與仿真等數(shù)學方法應用到工程、經濟、社會和醫(yī)學等方面，取得許多成就。

強化學習發(fā)展

? ? ? ?正是由于Bellman在1956年提出了動態(tài)規(guī)劃方法，強化學習作為機器學習中的一個重要領域才能夠得以順利發(fā)展。強化學習最早可以追溯到巴甫洛夫的條件反射實驗，它從動物行為研究和優(yōu)化控制兩個領域獨立發(fā)展，最終經Richard Bellman之手將其抽象為馬爾可夫決策過程(Markov Decision Process，MDP)。因此Bellman不僅僅是動態(tài)規(guī)劃的創(chuàng)始人，也是強化學習的奠基者。

五、其他動態(tài)規(guī)劃學者

? ? ? ?1977年，美國學者Paul J. Werbos首次提出了自適應動態(tài)規(guī)劃（ADP）。ADP是一種新的非線性優(yōu)化方法，融合了強化學習和動態(tài)規(guī)劃的思想，模擬人通過環(huán)境反饋進行學習的思路。

? ? ? ?1997年，Prokhorov 和Wunsch討論了HDP, DHP和全局雙重啟發(fā)式動態(tài)規(guī)劃（GDHP）的設計，并提出了ADP的實現(xiàn)方法與訓練步驟。

? ? ? ?相信到這里，大家已經了解了動態(tài)規(guī)劃的由來，敬請持續(xù)關注，接下來小編將帶你學習動態(tài)規(guī)劃的知識點~

資料來源：

https://wiki.mbalib.com/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

http://www.mybatis.cn/archives/1627.html

https://baike.baidu.com/item/%E8%87%AA%E9%80%82%E5%BA%94%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/22987923?fr=aladdin

END

作者 | 劉文志? ?林若唯

責編 | 劉文志

審核 | 徐小峰

?·YUNCHOUSHUO·?

· 知乎｜運籌說 ·

· 簡書｜運籌說 ·

· CSDN | 運籌說 ·