動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支捉腥，是求解決策過程最優(yōu)化的數(shù)學(xué)方法跃洛，通常情況下應(yīng)用于最優(yōu)化問題轨蛤，這類問題一般有很多個可行的解蜜宪，每個解有一個值，而我們希望從中找到最優(yōu)的答案祥山。
在計算機(jī)科學(xué)領(lǐng)域圃验，應(yīng)用動態(tài)規(guī)劃的思想解決的最基本的一個問題就是：尋找有向無環(huán)圖（籬笆網(wǎng)絡(luò)）當(dāng)中兩個點(diǎn)之間的最短路徑（實(shí)際應(yīng)用于地圖導(dǎo)航、語音識別枪蘑、分詞损谦、機(jī)器翻譯等等）。
下面舉一個比較簡單的例子做說明：求S到E的最短路徑岳颇。如下圖（各點(diǎn)之間距離不相同）：
我們知道照捡，要找到S到E之間最短路徑，最容易想到的方法就是窮舉法话侧。也就是把所有可能的路徑都例舉出來栗精。從S走向A層共有4種走法，從A層走向B層又有4種走法瞻鹏，從B層走向C層又有4種走法悲立，然后C層走向E點(diǎn)只有一種選擇。所以最終我們窮舉出了4X4X4=64種可能新博。顯然薪夕，這種方法必定可行。但在實(shí)際的應(yīng)用當(dāng)中赫悄，對于數(shù)量極其龐大的結(jié)點(diǎn)數(shù)和邊數(shù)的圖原献，其計算復(fù)雜度也將會變得非常大，而計算效率也會隨之降低埂淮。
因此姑隅，這里選擇使用一種基于動態(tài)規(guī)劃的方式來尋找最佳路徑。
所謂動態(tài)規(guī)劃倔撞。其核心就是“動態(tài)”的概念讲仰，把大的問題細(xì)分為多個小的問題，基于每一步的結(jié)果再去尋找下一步的策略痪蝇，通過每一步走過之后的局部最優(yōu)去尋找全局最優(yōu)鄙陡。這樣解釋比較抽象，下面直接用回剛剛的例子說明霹俺。如下圖：
首先柔吼，我們假設(shè)S到E之間存在一條最短路徑（紅色），且這條路徑經(jīng)過C2點(diǎn)丙唧，那么我們便一定能夠確定從S到C2的64條（4X4X4=64）子路徑當(dāng)中，該子路徑一定最短觅玻。（證明：反證法想际。如果S到C2之間存在一條更短的子路徑培漏，那么便可以用它來代替原先的路徑，而原先的路徑顯然就不是最短了胡本，這與原假設(shè)自相矛盾）牌柄。
同理，我們也可以得出從S到B2點(diǎn)為兩點(diǎn)間最短子路徑的結(jié)論侧甫。這時候珊佣，真相便慢慢浮出水面：既然如此，我們計算從S點(diǎn)出發(fā)到點(diǎn)C2的最短路徑披粟，是不是只要考慮從S出發(fā)到B層所有節(jié)點(diǎn)的最短路徑就可以了咒锻？答案是肯定的！因?yàn)槭靥耄瑥腟到E的“全局最短”路徑必定經(jīng)過在這些“局部最短”子路徑惑艇。沒錯！這就是上面提及到的通過局部最優(yōu)的最優(yōu)去尋找全局最優(yōu)拇泛，問題的規(guī)模被不斷縮斜醢汀！
接下來俺叭，要揭曉答案了恭取！繼續(xù)看下圖：
回顧之前的分析：我們計算從S起到C2點(diǎn)的最短路徑時候只需要考慮從S出發(fā)到B層所有節(jié)點(diǎn)的最短路徑，B層也如是熄守。對B2來說蜈垮，一共有4條路線可以到達(dá)，分別是A1→B2柠横，A2→B2窃款，A3→B2，A4→B2牍氛。我們需要做的就是把A2→B2這條最短路線保留晨继，而其他3條刪除掉（因?yàn)楦鶕?jù)以上的分析，它們不可能構(gòu)成全程的最短路線）搬俊。OK紊扬，來到這里，我們會發(fā)現(xiàn)一個小“漏洞”唉擂，這段S→A2→B2→C2→E的路線只是我一廂情愿的假設(shè)餐屎，最短路徑不一定是經(jīng)過以上這些點(diǎn)。所以玩祟，我們要把每層的每個節(jié)點(diǎn)都考慮進(jìn)來腹缩。
以下是具體的做法：
step1：從點(diǎn)S出發(fā)。對于第一層的3個節(jié)點(diǎn)，算出它們的距離d（S,A1）,d（S,A2）,d（S,A3）,d（S,A4）藏鹊，因?yàn)橹挥幸徊饺蠹ィ赃@些距離都是S到它們各自的最短距離。
step2：對于B層的所有節(jié)點(diǎn)（B1,B2,B3,B4）盘寡，要計算出S到它們的最短距離茎截。我們知道扼脐，對于特定的節(jié)點(diǎn)B2航闺，從S到它的路徑可以經(jīng)過A層的任何一個節(jié)點(diǎn)（A1,A2,A3,A4）软棺。對應(yīng)的路徑長就是d（S,B2）=d（S,Ai）+d（Ai,B2）（其中i=1,2,3,4）。由于A層有4個節(jié)點(diǎn)（即i有4個取值）影涉，我們要一一計算变隔，然后找到最小值。這樣常潮，對于B層的每個節(jié)點(diǎn)弟胀，都需要進(jìn)行4次運(yùn)算，而B層有4個節(jié)點(diǎn)喊式，所以共有4X4=16次運(yùn)算孵户。
step3：這一步是該算法的核心。我們從step2計算得出的結(jié)果只保留4個最短路徑值（每個節(jié)點(diǎn)保留一個）岔留。那么夏哭，若從B層走向C層來說，該步驟的基數(shù)已經(jīng)不再是4X4献联，而是變成了4竖配！也就是說，從B層到C層的最短路徑只需要基于B層得出的4個結(jié)果來計算里逆。這種方法一直持續(xù)到最后一個狀態(tài)进胯，每一步計算的復(fù)雜度為相鄰兩層的計算復(fù)雜度為4X4乘積的正比！再通俗點(diǎn)說原押，連接這兩兩相鄰層的計算符合變成了“+”號胁镐，取代了原先的“X”號。用這種方法诸衔，只需進(jìn)行4X4X2=32次計算盯漂！
其實(shí)上述的算法就是著名的維特比算法，事實(shí)上非常簡單笨农！
若假設(shè)整個網(wǎng)格的寬度為D就缆，網(wǎng)格長度為N，那么若使用窮舉法整個最短路徑的算法復(fù)雜度為O（DN）谒亦，而使用這種算法的計算復(fù)雜度為O（ND2）竭宰。試想一下空郊，若D與N都非常大，使用維特比算法的效率將會提高幾個數(shù)量級羞延！
代碼實(shí)現(xiàn)（C語言版）：
同樣是實(shí)現(xiàn)從S到E的最短路徑渣淳。不過這次把剛剛的情況簡化了一下脾还，原理是相同的伴箩。
#include<stdlib.h>
#include<stdio.h>
#define x 9999
#define max 9999
int data[10][10];
int dist[10];//記錄最短路徑為多少
int path[10];//記錄最短路徑
int kmin(int,int);
void fpath(int a[][10]);
int froute(int a[][10]);
void main()
{
int i,m;
int a[10][10]=
{
{x,4,2,3,x,x,x,x,x,x},
{x,x,x,x,10,9,x,x,x,x},
{x,x,x,x,6,7,10,x,x,x},
{x,x,x,x,x,3,8,x,x,x},
{x,x,x,x,x,x,x,4,8,x},
{x,x,x,x,x,x,x,9,6,x},
{x,x,x,x,x,x,x,5,4,x},
{x,x,x,x,x,x,x,x,x,8},
{x,x,x,x,x,x,x,x,x,4},
{x,x,x,x,x,x,x,x,x,x}
};
/*for (i=0;i<10;i++)
{
for(j=0;j<10;j++)
printf("%d ",a[i][j]);
printf("\n");
}*/
fpath(a);
printf("最短路徑大小為: %d\n",dist[9]);
m=froute(a);
for(i=m-1;i>=0;i--)
printf("最短路徑經(jīng)過: %d\n",path[i]);
}
void fpath(int a[][10])
{
int i,j,k;42 dist[0]=0;
for(i=1;i<10;i++)
{
k=max;
for(j=0;j<i;j++)
{
if(a[j][i]!=x)
if((dist[j]+a[j][i])<k)
k=dist[j]+a[j][i];
}
dist[i]=k;
}
}
int froute(int a[][10])
{
int j,b,k=1,i=9;
path[0]=10;
while(i>0)
{
for(j=i-1;j>=0;j--)
{
if(a[j][i]!=x)
{
b=dist[i]-a[j][i];
if(b==dist[j])
{
path[k++]=j+1;
i=j;
break;
}
}
}
}
return k;
}
