基本介紹
- 中文名：動態規劃
- 外文名： Dynamic Programming
- 所屬學科：運籌學
- 簡稱：DP
- 運用：求解決策過程（decision process）最最佳化的數學方法
- 第一本著作：《Dynamic Programming》
- 分支：運籌學的一個分支
原理,概念引入,基本思想,基本概念,基本結構,適用條件,分類,局限性,
原理
概念引入
在現實生活中，有一類活動的過程，由於它的特殊性，可將過程分成若干個互相聯繫的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴於當前面臨的狀態，又影響以後的發展。當各個階段決策確定後，就組成一個決策序列，因而也就確定了整個過程的一條活動路線。這種把一個問題看作是一個前後關聯具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最最佳化的過程為動態規劃方法。
基本思想
動態規划算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規划算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重複計算了很多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重複計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規划算法多種多樣，但它們具有相同的填表格式。
基本概念
- 多階段決策問題
如果一類活動過程可以分為若干個互相聯繫的階段，在每一個階段都需作出決策（採取措施），一個階段的決策確定以後，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線，則稱它為多階段決策問題。
各個階段的決策構成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選擇，因而就有許多策略供選取，對應於一個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優策略，使在預定的標準下達到最好的效果。
- 動態規劃問題中的術語
階段：把所給求解問題的過程恰當地分成若干個相互聯繫的階段，以便於求解，過程不同，階段數就可能不同。描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。
狀態：狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
無後效性：我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用一個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性。
決策：一個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多問題中，決策可以自然而然地表示為一個數或一組數。不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的範圍稱為允許決策集合。
策略：由每個階段的決策組成的序列稱為策略。對於每一個實際的多階段決策過程，可供選取的策略有一定的範圍限制，這個範圍稱為允許策略集合。
允許策略集合中達到最優效果的策略稱為最優策略。
給定k階段狀態變數x(k)的值後，如果這一階段的決策變數一經確定，第k+1階段的狀態變數x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關係看成(x(k)，u(k))與x(k+1)確定的對應關係，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態轉移規律，稱為狀態轉移方程。
最最佳化原理：作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，餘下的子策略必然構成“最優子策略”。
最優性原理實際上是要求問題的最優策略的子策略也是最優。
基本結構
多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最最佳化問題的方法為動態規劃方法。
適用條件
任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最最佳化原理和無後效性。
- 最最佳化原理（最優子結構性質）
最最佳化原理可這樣闡述：一個最最佳化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最最佳化策略的子策略總是最優的。一個問題滿足最最佳化原理又稱其具有最優子結構性質。
將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱為無後效性。
- 子問題的重疊性
動態規划算法的關鍵在於解決冗餘，這是動態規划算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間複雜度要大於其他的算法。選擇動態規划算法是因為動態規划算法在空間上可以承受，而搜尋算法在時間上卻無法承受，所以我們舍空間而取時間。
分類
動態規劃的數學模型。根據決策過程的演變是確定性的還是隨機性的。可分為確定性決策過程和隨機性決策過程。另外。也可按時間參量是離散的或是連續的變數。分為離散決策過程和連續決策過程。組合起來就有離散確定性、離散隨機性、連續確定性、連續隨機性四種決策過程模型。
對於確定性的決策過程。問題中下一段的狀態已由當前段的狀態及決策完全確定。對於隨機性決策過程。它與確定性決策過程的區別在於下一段的狀態並不能由當前段的狀態及決策完全確定。而是按某種機率分布來決定下一段的狀態。這種機率分布是由當前段的狀態和決策完全確定。
局限性
動態規劃對於解決多階段決策問題的效果是明顯的，但是動態規劃也有一定的局限性。首先，它沒有統一的處理方法，必須根據問題的各種性質並結合一定的技巧來處理；另外當變數的維數增大時，總的計算量及存貯量急劇增大。因而，受計算機的存貯量及計算速度的限制，當今的計算機仍不能用動態規劃方法來解決較大規模的問題，這就是“維數障礙”。
