-
動態規劃
鎖定
- 中文名
- 動態規劃
- 外文名
- Dynamic Programming
- 所屬學科
- 運籌學
- 簡 稱
- DP
- 運 用
- 求解決策過程(decision process)最優化的數學方法
- 第一本著作
- 《Dynamic Programming》
- 分 支
- 運籌學的一個分支
動態規劃原理
雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題,但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃),只要人為地引進時間因素,把它視為多階段決策過程,也可以用動態規劃方法方便地求解
[3]
。
動態規劃概念引入
在現實生活中,有一類活動的過程,由於它的特殊性,可將過程分成若干個互相聯繫的階段,在它的每一階段都需要作出決策,從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定,它依賴於當前面臨的狀態,又影響以後的發展。當各個階段決策確定後,就組成一個決策序列,因而也就確定了整個過程的一條活動路線。這種把一個問題看作是一個前後關聯具有鏈狀結構的多階段過程就稱為多階段決策過程,這種問題稱為多階段決策問題。在多階段決策問題中,各個階段採取的決策,一般來説是與時間有關的,決策依賴於當前狀態,又隨即引起狀態的轉移,一個決策序列就是在變化的狀態中產生出來的,故有“動態”的含義,稱這種解決多階段決策最優化的過程為動態規劃方法
[4]
。
動態規劃基本思想
動態規劃算法通常用於求解具有某種最優性質的問題。在這類問題中,可能會有許多可行解。每一個解都對應於一個值,我們希望找到具有最優值的解。動態規劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然後從這些子問題的解得到原問題的解。與分治法不同的是,適合於用動態規劃求解的問題,經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題,則分解得到的子問題數目太多,有些子問題被重複計算了很多次。如果能夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,這樣就可以避免大量的重複計算,節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到,只要它被計算過,就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣,但它們具有相同的填表格式
[5]
。
動態規劃基本概念
- 多階段決策問題
如果一類活動過程可以分為若干個互相聯繫的階段,在每一個階段都需作出決策(採取措施),一個階段的決策確定以後,常常影響到下一個階段的決策,從而就完全確定了一個過程的活動路線,則稱它為多階段決策問題
[6]
。
各個階段的決策構成一個決策序列,稱為一個策略。每一個階段都有若干個決策可供選擇,因而就有許多策略供選取,對應於一個策略可以確定活動的效果,這個效果可以用數量來確定。策略不同,效果也不同,多階段決策問題,就是要在可以選擇的那些策略中間,選取一個最優策略,使在預定的標準下達到最好的效果
[6]
。
- 動態規劃問題中的術語
階段:把所給求解問題的過程恰當地分成若干個相互聯繫的階段,以便於求解,過程不同,階段數就可能不同。描述階段的變量稱為階段變量。在多數情況下,階段變量是離散的,用k表示。此外,也有階段變量是連續的情形。如果過程可以在任何時刻作出決策,且在任意兩個不同的時刻之間允許有無窮多個決策時,階段變量就是連續的
[6]
。
狀態:狀態表示每個階段開始面臨的自然狀況或客觀條件,它不以人們的主觀意志為轉移,也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置,它既是該階段某路的起點,同時又是前一階段某支路的終點
[6]
。
無後效性:我們要求狀態具有下面的性質:如果給定某一階段的狀態,則在這一階段以後過程的發展不受這階段以前各段狀態的影響,所有各階段都確定時,整個過程也就確定了。換句話説,過程的每一次實現可以用一個狀態序列表示,在前面的例子中每階段的狀態是該線路的始點,確定了這些點的序列,整個線路也就完全確定。從某一階段以後的線路開始,當這段的始點給定時,不受以前線路(所通過的點)的影響。狀態的這個性質意味着過程的歷史只能通過當前的狀態去影響它的未來的發展,這個性質稱為無後效性
[6]
。
決策:一個階段的狀態給定以後,從該狀態演變到下一階段某個狀態的一種選擇(行動)稱為決策。在最優控制中,也稱為控制。在許多問題中,決策可以自然而然地表示為一個數或一組數。不同的決策對應着不同的數值。描述決策的變量稱決策變量,因狀態滿足無後效性,故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史
[6]
。
給定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階段的狀態轉移規律,稱為狀態轉移方程
[6]
。
動態規劃基本結構
多階段決策問題中,各個階段採取的決策,一般來説是與時間有關的,決策依賴於當前狀態,又隨即引起狀態的轉移,一個決策序列就是在變化的狀態中產生出來的,故有“動態”的含義,稱這種解決多階段決策最優化問題的方法為動態規劃方法
[7]
。
動態規劃適用條件
- 最優化原理(最優子結構性質)
最優化原理可這樣闡述:一個最優化策略具有這樣的性質,不論過去狀態和決策如何,對前面的決策所形成的狀態而言,餘下的諸決策必須構成最優策略。簡而言之,一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質
[8]
。
將各階段按照一定的次序排列好之後,對於某個給定的階段狀態,它以前各階段的狀態無法直接影響它未來的決策,而只能通過當前的這個狀態。換句話説,每個狀態都是過去歷史的一個完整總結。這就是無後向性,又稱為無後效性
[8]
。
- 子問題的重疊性
動態規劃算法的關鍵在於解決冗餘,這是動態規劃算法的根本目的。動態規劃實質上是一種以空間換時間的技術,它在實現的過程中,不得不存儲產生過程中的各種狀態,所以它的空間複雜度要大於其他的算法。選擇動態規劃算法是因為動態規劃算法在空間上可以承受,而搜索算法在時間上卻無法承受,所以我們舍空間而取時間
[8]
。
動態規劃分類
動態規劃的數學模型。根據決策過程的演變是確定性的還是隨機性的。可分為確定性決策過程和隨機性決策過程。另外。也可按時間參量是離散的或是連續的變量。分為離散決策過程和連續決策過程。組合起來就有離散確定性、離散隨機性、連續確定性、連續隨機性四種決策過程模型
[9]
。
對於確定性的決策過程。問題中下一段的狀態已由當前段的狀態及決策完全確定。對於隨機性決策過程。它與確定性決策過程的區別在於下一段的狀態並不能由當前段的狀態及決策完全確定。而是按某種概率分佈來決定下一段的狀態。這種概率分佈是由當前段的狀態和決策完全確定
[9]
。
動態規劃侷限性
動態規劃對於解決多階段決策問題的效果是明顯的,但是動態規劃也有一定的侷限性。首先,它沒有統一的處理方法,必須根據問題的各種性質並結合一定的技巧來處理;另外當變量的維數增大時,總的計算量及存貯量急劇增大。因而,受計算機的存貯量及計算速度的限制,當今的計算機仍不能用動態規劃方法來解決較大規模的問題,這就是“維數障礙”
[10]
。
- 參考資料
-
- 1. 許國根,趙後隨,黃智勇.最優化方法及其MATLAB實現:許國根,趙後隨,黃智勇,2018-07:91
- 2. Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein.Introduction to Algorithms, Third Edition:麻省理工大學出版社,2009
- 3. 沈大慶.國防工業出版社:國防工業出版社,2015-08:71
- 4. 田翠華.算法設計與分析:冶金工業出版社,2007-08:106
- 5. 宋榮興,荊湘霞,李扶民.運籌學:東北財經大學出版社,2018-03:149
- 6. 葉金霞,白春章.信息技術 九年級:遼寧師範大學出版社,2008-07:113-114
- 7. 黎遠松.算法分析與設計:西南交通大學出版社,2013-08:52
- 8. 袁平波,顧為兵,尹東編.數據結構及應用算法:中國科學技術大學出版社,2013-09:352
- 9. 傅英定,成孝予,唐應輝.最優化理論與方法:國防工業出版社,2008-06:260
- 10. 王曉原,孫亮.交通與運輸類系列教材 運籌學:西南交通大學出版社,2018-01:110