-
最優化原理
鎖定
最優化原理也稱最優性原理。指解決多階段決策問題的理論。這個理論是美國的貝爾曼在1956年提出的。它原來的表述是：一個過程的最優策略具有這樣的性質，即無論其初始狀態及初始決策如何，其以後諸決策對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略。這個原理的實質是多階段決策過程具有這樣的性質，即不管過去的過程如何，只從當前的狀態和系統的最優化要求出發，作出下一步的最優決策。
[1]
- 中文名
- 最優化原理
- 外文名
- principle of optimality
- 發現者
- 1951年美國數學家R．Bellman等人
- 問題求解模式
- 初始狀態→│決策1│→│決策
最優化原理背景知識
1951年美國數學家R．Bellman等人，根據一類多階段問題的特點，把多階段決策問題變換為一系列互相聯繫的單階段問題，然後逐個加以解決。一些靜態模型，只要人為地引進“時間”因素，分成時段，就可以轉化成多階段的動態模型，用動態規劃方法去處理。與此同時，他提出瞭解決這類問題的“最優化原理”(Principle of optimality)：
“一個過程的最優決策具有這樣的性質：即無論其初始狀態和初始決策如何，其今後諸策略對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略”。簡言之，一個最優策略的子策略，對於它的初態和終態而言也必是最優的。
這個“最優化原理”如果用數學化一點的語言來描述的話，就是：假設為了解決某一優化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優的，對於任何一個整數k，1 < k < n，不論前面k個決策是怎樣的，以後的最優決策只取決於由前面決策所確定的當前狀態，即以後的決策Dk+1，Dk+2，…，Dn也是最優的。
最優化原理是動態規劃的基礎。任何一個問題，如果失去了這個最優化原理的支持，就不可能用動態規劃方法計算。能採用動態規劃求解的問題都需要滿足一定的條件：
(1) 問題中的狀態必須滿足最優化原理；
(2) 問題中的狀態必須滿足無後效性。
所謂的無後效性是指：“下一時刻的狀態只與當前狀態有關，而和當前狀態之前的狀態無關，當前的狀態是對以往決策的總結”。
動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。動態規劃的設計都有着一定的模式，一般要經歷以下幾個步驟。
(1)劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(3)確定決策並寫出狀態轉移方程：因為決策和狀態轉移有着天然的聯繫，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態之間的關係來確定決策。
最優化原理算法實現
動態規劃的主要難點在於理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段,每個階段的狀態以及從前一個階段轉化到後一個階段之間的遞推關係。遞推關係必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來説，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重複計算，所以對於大規模問題來説，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表示一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關係，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取捨或者運算求得問題的最優解。下面分別以求解最大化投資回報問題和最長公共子序列問題為例闡述用動態規劃算法求解問題的一般思路。
實例：
最大化投資回報問題
某人有一定的資金用來購買不同面額的債卷，不同面額債卷的年收益是不同的，求給定資金，年限以及債卷面額、收益的情況下怎樣購買才能使此人獲得最大投資回報。
程序輸入約定：第一行第一列表示資金（1000的倍數）總量，第二列表示投資年限；第二行表示債卷面額總數；從第三行開始每行表示一種債卷，佔用兩列，前一列表示債卷面額，後一列表示其年收益，如下輸入實例，
10000 1
2
4000 400
3000 250
程序實現如下，註釋幾乎説明了一切，所以不再另外分析。
#include <iostream>
#include <memory.h>
using namespace std;
/// 此數組是算法的關鍵存儲結構，用來存儲不同階段各種債卷
/// 組合下對應可獲取的最大利息。
int saifa[80005];
/// 此函數用於計算當前債卷在不同購買額下的最優利息情況，
/// 注意此時的利息情況是基於上一次債卷的情況下計算得到的，
/// 也就是説當前利息最優是基於上一次利息最優的基礎上計算出來的，
/// 這也正好體現了動態規劃中“最優化原則”：不管前面的策略如何，
/// 此後的決策必須是基於當前狀態（由上一次決策產生）的最優決策。
/*
動態規劃的求解過程一般都可以用一個最優決策表來描述，
對於本程序，以示例輸入為例，對於第一年，其最優決策表如下：
0 1 2 3 4 5 6 7 8 9 10(*1000) -- (1)
0 0 0 0 400 400 400 400 800 800 800 -- (2)
0 0 0 250 400 400 500 650 800 900900 -- (3)
(1) -- 表示首先選利息為400的債卷在對應資金下的最優利息。
(2) -- 表示可用來購買債卷的資金。
(3) -- 表示在已有狀態下再選擇利息為300的債卷在對應資金下的最優利息。
注意上面表格，在求購買利息為300的債卷獲得的最優收益的時候，
參考了以前的最優狀態，以3行8列的650為例，7(*1000)可以
在以前購買了0張4000的債卷的基礎上再2張3000的，也可以在以前購
買了1張4000的基礎上再買1張3000，經比較取其收益大的，這就是典
型的動態規劃中的當前最優狀態計算。
本程序中把上面的最優決策二維表用一個一維數組表示，值得借鑑。
*/
void add(int a, int b)
{
cout << a << " " << b << endl; // for debug
for (int i = 0; i <= 80000; i++)
{
if (i + a > 80000)
{
break;
}
if (saifa[i] + b > saifa[i + a]) // 累計同時購買多種債卷時的利息
{
saifa[i + a] = saifa[i] + b;
}
if (i < 200) // for debug
cout << i << "-" << saifa[i] << " ";
}
cout << endl; // for debug
}
int main(void)
{
int n, d, money, year, pay, bond;
int ii, i;
scanf("%d", &n);
for (ii = 0; ii < n; ii++)
{
memset(saifa, 0, sizeof(saifa));
scanf("%d%d", &money, &year);
scanf("%d", &d);
for (i = 0; i < d; i++)
{
scanf("%d%d", &pay, &bond);
add(pay / 1000, bond);
}
// 計算指定年限內最優組合的本金利息總額
for (i = 0; i < year; i++)
{
cout << saifa[money / 1000] << " "; // for debug
money += saifa[money / 1000];
}
cout << endl; // for debug
printf("%d\n", money);
}
return 0;
}
上述程序實現方法同樣適合於揹包問題，最優庫存問題等，只是針對具體情況，最優決策表的表示和生成會有所不同。
