算法設(shè)計實(shí)例教程 課件 第5-9章 字符串和高精度運(yùn)算-高級算法

算法設(shè)計實(shí)例教程算法設(shè)計實(shí)例教程教學(xué)分析目錄CONCENTS123456789第5章字符串和高精度運(yùn)算第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第6章圖論算法第7章動態(tài)規(guī)劃算法第8章計算幾何基礎(chǔ)第9章高級算法字符串匹配是計算機(jī)科學(xué)中最古老、研究最廣泛的問題之一，在信息檢索、拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、網(wǎng)絡(luò)入侵檢測等方面具有廣泛的應(yīng)用。本章第一部分重點(diǎn)介紹常見的字符串匹配問題的求解策略。盡管現(xiàn)在的計算機(jī)的能力已經(jīng)非常強(qiáng)大，但依然是有一個上限，它能夠表示和處理的數(shù)的范圍和精度總是有限的，如果在解決實(shí)際問題時，所需要處理的數(shù)據(jù)超出了計算機(jī)所能表示的范圍，那么這些超出范圍的數(shù)據(jù)在計算機(jī)中該如何處理呢？本章的第二部分將介紹大數(shù)求和以及階乘的精確計算等高精度問題的求解方法。第5章字符串和高精度運(yùn)算在計算機(jī)中進(jìn)行信息的檢索實(shí)際就是字符串匹配的應(yīng)用。所謂的檢索就是從被檢索的文檔中找出匹配的信息，被檢索文檔會顯示匹配信息具體的位置。所謂字符串匹配就是在主串中搜索模式串是否存在及其存在的位置。如果在字符串S中查找字符串T，那么字符串S就是主串，字符串T就是模式串。5.1字符串匹配樸素模式匹配算法也稱之為暴力(BF，BruteForce)算法。該算法的思想就是將主串S的第一個字符與模式串T的第一個字符進(jìn)行匹配，如果相等，則比較S的第二個字符和T的第二個字符；若不相等即失配，則將模式串T整體右移一位，再將主串S的第二個字符和T的第一個字符，依次比較，直到得出最后的匹配結(jié)果。5.1.1樸素模式匹配下面圖示來說明該算法，例如S=“abaacd”,T=“aac”5.1.1樸素模式匹配圖5-1第一次匹配主串和模式串的第一個字符相等，進(jìn)行第二個字符的比較，比較發(fā)現(xiàn)不相等，也就是失配了，則將模式串T整體右移一位，如下圖所示：圖5-2第二次匹配5.1.1樸素模式匹配將S的第二個字符和T的第一個字符比較，比較發(fā)現(xiàn)不相等，則將模式串T整體再右移一位，如下圖所示：圖5-3第三次匹配將S的第三個字符匹配T的第一個字符，S的第四個字符和T的第二個字符匹配，繼續(xù)匹配發(fā)現(xiàn)S中有和T匹配的部分，匹配成功，計算出匹配成功的位置。如果不能匹配則繼續(xù)按照上述的規(guī)則，T繼續(xù)右移一位，依次類推。當(dāng)發(fā)生不匹配的時候，模式串整體右移1位，主串S索引i的位置相比上一次模式串整體右移1位時的位置右移1位，模式串索引j位置回到串的起始位置。【例5.1】：查找字符串”abaacd”中查找串”aac”，如果找到請返回匹配位置，如果找不到請輸出字符串“不匹配！“。樸素模式匹配算法思想、實(shí)現(xiàn)較為簡單，但是效率較為低下，時間復(fù)雜度O(s_len*t_len)，其中s_len是主串長度，t_len是模式串長度。5.1.1樸素模式匹配1#include<stdio.h>

2#include<string.h>

3#defineN200

4intmatch(char*s,char*t)

5{

6 inti=0;

7 intj=0;

8 ints_len=strlen(s);

9 intt_len=strlen(t);

10 while(i<=(s_len-1)&&j<=(t_len-1))

11 {

12 if(s[i]==t[j])

13 {

14 i++;

15 j++;

16 }

17 else

18 {

19 i=i-j+1;//下標(biāo)回到開始比對的位置的下一個位置20 j=0;

21 }

22 }

23 if(j==t_len)

24 returni-t_len;//返回下標(biāo)開始比對的位置25 else

26 return-1;

27}

28intmain()

29{

30chars[N]="abaacd";

31 chart[N]="aac";

32 intx=match(s,t);

33 if(x==-1)

34printf("不匹配！");

35else

36 printf("匹配位置=%d",x);

37 return0;

38}樸素模式匹配算法中忽略了已經(jīng)匹配過的字符的規(guī)律。為了提高匹配效率，下面討論另外一種算法-KMP算法。樸素的模式匹配算法中模式串T在第j位失配時，默認(rèn)把T串整體后移一位。但在前一輪的比較中，已經(jīng)知道T的第j位之前的字符段與S中間對應(yīng)的字符段已經(jīng)匹配成功了。那么可否利用這些已經(jīng)匹配的字符串，讓模式串T多右移幾位，從而達(dá)到減少遍歷的次數(shù),這也就是KMP算法的核心5.1.2KMP模式匹配圖5-4失配5.1.2KMP模式匹配

從上面的圖可以看出在T5處失配，那么T0至T4與主串的部分字符已經(jīng)匹配成功，現(xiàn)在就是需要通過找到已經(jīng)匹配成功的部分字符串的規(guī)律，讓模式串盡可能的多右移幾位。分析T0至T4也就是“ababa”已經(jīng)匹配的這部分字符串的特點(diǎn)，通過觀察發(fā)現(xiàn)“ababa”的后面一部分aba和前面一部分aba是重合的，那么可以將模式串整體右移2位，j的位置由原來的5變?yōu)?。圖5-5重新匹配的位置因?yàn)樵谀Ｊ酱娜我馕恢胘都可能失配，因此為了能提高效率，KMP算法提前構(gòu)建一個next數(shù)組，用來存儲j位置失配時下次重新匹配的位置next[j]。next[j]中的j表示當(dāng)前失配的位置，next[j]表示下次重新開始匹配時的位置。j的范圍是0到模式串長-1。通過剛才的分析，假設(shè)當(dāng)前j的位置出現(xiàn)不匹配，T0…Tj-1和主串部分字符是相同的，找出T0…Tj-1字符串的規(guī)律，也就是首尾是否有重合的字符串，假設(shè)T0…Tj-1首尾重合部分的長度為x，很顯然右移以后下次匹配的j的位置next[j]為x,不難算出模式串T需要右移j-x。為了能遍歷完整，首尾重合部分的元素個數(shù)應(yīng)取到最多，例如“ababa”的首尾重合的字符串是“aba”，而不是“a”，但是也必須小于“ababa”，所以next[j]應(yīng)取盡量大的值，那么求解next[j]的公式如下所示：5.1.2KMP模式匹配圖5-6next數(shù)組的計算假設(shè)主串S的匹配索引是i，模式串匹配索引是j，KMP算法的思想描述如下：從串頭開始匹配，在某次匹配過程中，如果S[i]和T[j]不匹配，也就是S[i]≠T[j]，那么從next數(shù)組里找到next[j]的值x，讓S[i]和T[s]比較。但是如果在串頭就不匹配，也就是說S[i]≠T[0]，就需要讓i進(jìn)1位，再讓S[i]和T[0]開始比較，進(jìn)入下一輪匹配。KMP的核心算法如下：while（i<s_len&&j<t_len）//s_len、t_len表示主串S和模式串T的長度{if(j==-1){j++,i++;contintue;}//若j退到頭，i右移1位，j=0if(a[i]==t[j]){j++,i++;contintue;}//若匹配成功，i和j同時向前移動繼續(xù)匹配j=next[j];//如果匹配不成功，索引i位置不變，下次重新開始匹配的位置為next[j]}5.1.2KMP模式匹配下面就是要求解next數(shù)組。很容易想到的方法，就是把T[0,j-1]的所有后綴子串找出來，依次看看是否能跟T[0,j-1]的前綴子串匹配。很顯然，這個方法也可以計算得到next數(shù)組，但是效率非常低。下面的方法可以較為高效地計算出next數(shù)組。假設(shè)現(xiàn)在要求next[8]，next[8]之前的數(shù)組元素已經(jīng)計算出結(jié)果。假設(shè)next[7]=3,那么就意味著T[0:2]=T[4:6]。如果T7=T3,那么next[8]=3+1=4。5.1.2KMP模式匹配圖5-7T[0:2]=T[4:6]的情況5.1.2KMP模式匹配如果T7≠T3，但next[3]=1，那么T0=T2=T4=T6,同上，如果T7=T1則next[8]=1+1=2，圖5-8T0=T2=T4=T6的情況如果T7≠T1，但next[1]=0，如果T7=T0,那么next[8]=1,如果T7≠T0，那么next[8]=0該算法的代碼實(shí)現(xiàn)如下所示：voidgetNext(charch[],intnext[]){next[0]=-1;inti=0,j=-1;while(i<strlen(ch)-1){if(j==-1||ch[i]==ch[j])next[++i]=++j;elsej=next[j];}}5.1.2KMP模式匹配next數(shù)組計算的時間復(fù)雜度是O(t_len)，匹配過程的時間復(fù)雜度是O(s_len)，KMP算法的時間復(fù)雜度是O(t_len+s_len)。樸素模式匹配算法簡單，時間復(fù)雜度是O(t_len*s_len)，在實(shí)際的軟件開發(fā)中，因?yàn)檫@種算法實(shí)現(xiàn)簡單，對于處理小規(guī)模的字符串匹配很好用。5.1.2KMP模式匹配【例5.2】：使用KMP算法查找字符串”abaacd”中查找串”aac”，如果找到請返回匹配位置，如果找不到請輸出字符串“不匹配！“。#include<stdio.h>

#include<string.h>

#include<malloc.h>

#defineN200

voidgetNext(charch[],intnext[])

{

next[0]=-1;

inti=0,j=-1;

while(i<strlen(ch)-1)

{

if(j==-1||ch[i]==ch[j])

next[++i]=++j;

else

j=next[j];

}

}

intKMP(charS[],charT[])

{

intt_len=strlen(T),s_len=strlen(S);

intnext[t_len];

getNext(T,next);

inti=0,j=0;

while(i<s_len&&j<t_len){

if(j==-1||S[i]==T[j]){

i++;

j++;

}

else

j=next[j];

}

if(j==t_len)

returni-t_len;

else

return-1;

}

intmain(){

charS[N]="abaacd";

charT[N]="aac";

intlocation=KMP(S,T);

if(location==-1)

printf("S和T不匹配！");

else

printf("匹配點(diǎn)的位置=%d",location);

return0;

}計算機(jī)內(nèi)數(shù)據(jù)存儲的最大值都是有限的，比如longlong類型是8個字節(jié)，它能表示的整數(shù)范圍為-9223372036854775808~9223372036854775807。如果需要計算的數(shù)據(jù)繼續(xù)增大，我們該怎么辦呢？這種問題屬于大數(shù)求和問題。所謂大數(shù)是指數(shù)的位數(shù)超過了計算機(jī)中基本數(shù)據(jù)類型的表示范圍。大數(shù)運(yùn)算就是大數(shù)進(jìn)行加、減、乘、除等一系列的運(yùn)算。5.2高精度運(yùn)算在小學(xué)我們就學(xué)過通過列豎式求兩個數(shù)的和。例如，列豎式計算整數(shù)9223372036854775808+1234的值，參加圖8.3。5.2.1小學(xué)時候的計算方法-“列豎式”圖5-9列豎式計算“9223372036854775808+1234”5.2.1小學(xué)時候的計算方法-“列豎式”我們首先需要將被加數(shù)和加數(shù)的數(shù)位靠右對齊，然后由右至左依次計算每個數(shù)位，如果超過10就產(chǎn)生進(jìn)位。如果我們將兩個整數(shù)逆序書寫，然后列豎式計算，得到的結(jié)果也是逆序的，參見圖5.4。圖5-10列豎式逆序計算“9223372036854775808+1234”如果我們把這兩個整數(shù)的每個數(shù)位按照字符逆序存儲在兩個數(shù)組中，然后讓這兩個數(shù)組對應(yīng)的數(shù)位進(jìn)行累加計算，并將結(jié)果存儲在第3個數(shù)組中，那么逆序輸出第3個數(shù)組中的字符就可以得到大數(shù)計算的結(jié)果。例如，分別用字符數(shù)組a，b，c逆序存儲被加數(shù)9223372036854775808、加數(shù)1234、和，參見圖8.5。5.2.1小學(xué)時候的計算方法-“列豎式”圖5.11用數(shù)組存儲被加數(shù)、加數(shù)與和數(shù)組c中每個元素的初始值為0，如果a[i]+b[i]+c[i]的值小于10，那么c[i]=a[i]+b[i]+c[i]，否則c[i]=a[i]+b[i]+c[i]-10，同時c[i+1]=1，用于保存進(jìn)位。在圖8.5中，a[0]+b[0]+c[0]=8+4+0=12，結(jié)果大于10，因此c[0]=12-10=2，同時c[1]=1。依次計算出數(shù)組c中所有元素的值，參見圖5.6。圖5.12用數(shù)組實(shí)現(xiàn)大數(shù)計算利用數(shù)組來實(shí)現(xiàn)兩個大數(shù)求和運(yùn)算的方法被稱為數(shù)組法。大數(shù)求和的基本思想是：使用字符數(shù)組來保存用戶的輸入數(shù)字和運(yùn)算結(jié)果，將兩個大數(shù)的每一位數(shù)字分別存儲在兩個數(shù)組中，然后模擬人工列豎式算加法的方式，對兩個數(shù)組的數(shù)組元素從最低位開始相加，并判斷是否進(jìn)位，一直到最高位結(jié)束。5.2.1小學(xué)時候的計算方法-“列豎式”【例5.3】數(shù)組法求兩個大整數(shù)的和。問題分析：從鍵盤以字符串的方式將兩個大數(shù)讀入到數(shù)組a和數(shù)組b中。設(shè)計一個逆序函數(shù)reverse對數(shù)組a和數(shù)組b中的字符串進(jìn)行逆序排列。設(shè)計一個bigDataSum函數(shù)完成“列豎式”計算。算法設(shè)計：算法描述參見圖5-13。假設(shè)數(shù)組a中的數(shù)字位數(shù)多，位數(shù)為n，數(shù)組b中的數(shù)字位數(shù)少，位數(shù)為m。5.2.2大數(shù)求和的程序?qū)崿F(xiàn)圖5-13用數(shù)組法求大數(shù)和的流程圖如果要將數(shù)組中元素的排列由正序變?yōu)槟嫘?，只要將首尾相對?yīng)位置的數(shù)組元素位置對調(diào)就可以實(shí)現(xiàn)。函數(shù)reverse的代碼實(shí)現(xiàn)如下：intreverse(chara[N]){inti,temp,len=strlen(a);//調(diào)用strlen函數(shù)獲得大數(shù)的位數(shù)for(i=0;i<len/2;i++)//將數(shù)組a中的數(shù)組元素按照首尾相對應(yīng)位置做對調(diào){temp=a[i];//從首部0開始第i個元素與從尾部len-1倒數(shù)第i個元素len-1-i的位置對調(diào)a[i]=a[len-1-i];a[len-1-i]=temp;}returnlen;}5.2.2大數(shù)求和的程序?qū)崿F(xiàn)數(shù)組a和數(shù)組b中存儲的大數(shù)的字符串長度可能是不同的，也就是說兩個進(jìn)行計算的大數(shù)的數(shù)位長度可能是不同的。在“列豎式”計算的時候，兩個數(shù)組元素中的字符數(shù)字需要先轉(zhuǎn)換成整數(shù)，然后再求和，最后判斷是否需要進(jìn)位。另外，兩個數(shù)組的數(shù)位對齊后，非對齊數(shù)位和對齊數(shù)位的處理方法是不同的，因此需要先判斷數(shù)組a和數(shù)組b中大數(shù)數(shù)位的長短。5.2.2大數(shù)求和的程序?qū)崿F(xiàn)bigDataSum函數(shù)有4個輸入數(shù)據(jù)：數(shù)位較長數(shù)組的地址char*l，數(shù)位較短數(shù)組的地址char*s，數(shù)位較長的大數(shù)的長度n，數(shù)位較短的大數(shù)的長度m。bigDataSum函數(shù)的算法描述參見圖5-14。5.2.2大數(shù)求和的程序?qū)崿F(xiàn)圖5-14用數(shù)組法求大數(shù)和的算法階乘的精確計算：例如輸入不超過1000的正整數(shù)n，輸出的精確結(jié)果。例如輸入30輸出265252859812191058636308480000000當(dāng)輸入1000時1000的階乘約4*10^(2567)，大概3000位數(shù)字，如果采用普通的階乘算法很明顯溢出：intfun(intn){inti;ints=1;for(i=1;i<=n;i++)s*=i;returns;}//求n的階乘的普通算法5.2.3階乘的精確計算故需要引入高精度算法。引入一個大小3000的數(shù)字a_int，讓a_int[0]保留個位，讓a_int[1]保留十位，讓a_int[2]保留百位……為什么要這么做，可作以下分析：當(dāng)n=1時，最終結(jié)果1，a_int[0]=1，其他位0即可。當(dāng)n=2時，最終結(jié)果2，a_int[0]=2，其他位0即可。當(dāng)n=3時，最終結(jié)果6，a_int[0]=6，其他位0即可。當(dāng)n=4時，最終結(jié)果24，a_int[0]=24，此時需要十位和個位拆開，a_int[0]=4，a_int[1]=2，其他位0即可。當(dāng)n=5時，最終結(jié)果120，此時a_int[0]=4，a_int[1]=2，其他位0，即120=24*5，4*5=20的個位0放在a_int[0]，而其十位需要進(jìn)位，2*5=10為百位和十位，再加上剛才的進(jìn)位，得百位十位為12，類似拆開a_int[1]=2，a_int[1]=1其他位0即可；抽象分析，假設(shè)i結(jié)果已經(jīng)算出并保存在j個數(shù)據(jù)單元里即i!=a_int[j]a_int[j-1]...a_int[2]a_int[1]a_int[0]，故輸入i+1時，按照要求：(i+1)，可寫出此時乘法豎式。5.2.3階乘的精確計算對于個位a_int[0]，a_int[0]*（i+1）所得數(shù)值取其個位保留在a_int[0]，剩余的位作為進(jìn)位。對于十位位a_int[1]，a_int[1]*（i+1）所得數(shù)值再加上個位的進(jìn)位取其個位保留在a_int[1]，剩余的位作為進(jìn)位。對于第k位a_int[k-1]，a_int[k-1]*（i+1）所得數(shù)值取其個位保留在a_int[k-1]，剩余的位作為進(jìn)位。5.2.3階乘的精確計算應(yīng)用舉例時間限制：1000ms內(nèi)存限制：32MB問題描述輸入一個正整數(shù)n，輸出n!的值。 其中n!=1*2*3*…*n。輸入格式 輸入包含一個正整數(shù)n，n<=1000。輸出格式 輸出n!的準(zhǔn)確值。樣例輸入10樣例輸出36288005.2.3階乘的精確計算1#include<stdio.h>

2#include<string.h>

3#include<iostream>4usingnamespacestd;

5intmain()

6{

7intn,a[5000],s,i,j,t,d;

8scanf("%d",&n);

9memset(a,0,sizeof(a));

10a[0]=1;

11d=1;

12for(i=2;i<=n;i++)

13{

14s=0;

15for(j=0;j<d;j++)

16{

17t=a[j]*i+s;//當(dāng)前位置的數(shù)之前在這個位置上的數(shù)乘以i，18a[j]=t%10;//然后加上前一位數(shù)的進(jìn)位19s=t/10;

20}

21while(s)

22{

23a[d++]=s%10;

24s/=10;

25}

26}

27for(i=4900;a[i]==0;i--);

28for(j=i;j>=0;j--)

29printf("%d",a[j]);

30printf("\n");

31return0;

32}5.3本章小結(jié)隨著計算機(jī)技術(shù)應(yīng)用的發(fā)展，海量數(shù)據(jù)的處理需求的出現(xiàn)，使得字符匹配算法越來越重要，通常希望匹配算法越快越好。在網(wǎng)絡(luò)速度迅速發(fā)展的今天，基于字符匹配技術(shù)的網(wǎng)絡(luò)應(yīng)用存在著性能瓶頸，各種各樣的匹配算法不斷出現(xiàn)提高系統(tǒng)的整體性能是研究和設(shè)計者的主要工作。由于現(xiàn)有計算編程語言的數(shù)據(jù)類型限制，對于大數(shù)據(jù)的存儲能力與計算能力有限。所以進(jìn)行大數(shù)據(jù)運(yùn)算時，大數(shù)據(jù)計算的一般思路為：將大數(shù)據(jù)拆分成多個小數(shù)據(jù)，使用編輯語言能夠計算的小數(shù)據(jù)進(jìn)行計算，再將小數(shù)據(jù)合并成大數(shù)據(jù)。。5.3本章小結(jié)算法設(shè)計實(shí)例教程教學(xué)分析目錄CONCENTS123456789第6章圖論算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第5章字符串和高精度運(yùn)算第7章動態(tài)規(guī)劃算法第8章計算幾何基礎(chǔ)第9章高級算法圖論〔GraphTheory〕是數(shù)學(xué)的一個分支。它以圖為研究對象。圖是由若干給定的點(diǎn)及連接兩點(diǎn)的邊所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的邊表示相應(yīng)兩個事物間具有某種關(guān)系。在計算機(jī)科學(xué)技術(shù)的許多學(xué)科中,如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯方法、網(wǎng)絡(luò)理論、信息的組織與檢索,均離不開由這種“節(jié)點(diǎn)”和“邊”組成的圖，除了這些學(xué)科以外，我們在很多的應(yīng)用領(lǐng)域，如集成電路的布線、網(wǎng)絡(luò)線路的鋪設(shè)、各類關(guān)系表示都需要抽象成圖來解決以及優(yōu)化。本章節(jié)重點(diǎn)介紹圖論中的最小生成樹、最短路徑、最大匹配等問題使用到的算法等知識。第6章圖論算法實(shí)際應(yīng)用中很多問題都需要抽象成賦權(quán)圖來解決，而賦權(quán)圖最關(guān)心也是最有用的是最小生成樹，下面來介紹它的概念及生成算法。設(shè)G為連通的邊賦權(quán)圖，T為G的生成樹,那么T中各邊權(quán)之和稱為生成樹T的權(quán),權(quán)值最小的生成樹稱為最小生成樹。賦權(quán)圖求最小生成樹的問題在實(shí)際應(yīng)用中具有很大的應(yīng)用價值，例如用最低的造價建造公路把n個城市連接起來、用最低成本的線路將n個站點(diǎn)連成一個網(wǎng)絡(luò)，等等。下面介紹求解最小生成樹的經(jīng)典算法--克魯斯克爾(Kruskal)算法，該算法由JosephKruskal在1956年發(fā)表。6.1最小生成樹Kruskal算法簡單直觀，算法的基本思想是：首先將邊的權(quán)值從小到大的排序，然后逐邊將它們放回到所關(guān)聯(lián)的頂點(diǎn)上，每次添加一條邊之前需要檢查添加的這條邊是否會產(chǎn)生回路。如果產(chǎn)生回路，那么就舍棄這條邊，選擇下一條邊，直至產(chǎn)生一個n-1條邊的無回路的子圖。由于該算法得到的子圖沒有回路，且m=n–1，根據(jù)樹的定理性質(zhì)，很容易證明產(chǎn)生的圖是G的生成樹，因?yàn)槭前凑者叺臋?quán)值大小順序逐步添加，所以得到一棵最小生成樹。Kruskal算法同樣適用于有邊權(quán)相同的賦權(quán)圖，相同權(quán)值的邊可以按任意次序排列，得到的都是最小生成樹。6.1最小生成樹Kruskal算法主要圍繞邊及其權(quán)值展開，也就是說需要有數(shù)據(jù)結(jié)構(gòu)用于存儲每條邊及其權(quán)值，每條邊可以通過邊的兩個端點(diǎn)描述，因此，定義如下的結(jié)構(gòu)體用于描述邊：typedefstruct{ intstart;//邊的起點(diǎn)節(jié)點(diǎn) intend;//邊的終點(diǎn)節(jié)點(diǎn) intvalue;//邊的權(quán)值}Edges;因?yàn)橘x權(quán)圖通常使用鄰接矩陣描述，那么邊的數(shù)組需要通過遍歷鄰接矩陣來轉(zhuǎn)換，且按照按照邊的權(quán)值升序排序。為了判斷添加某邊是否會產(chǎn)生回路，定義了一個尋找某節(jié)點(diǎn)父節(jié)點(diǎn)的函數(shù)searchFather。intsearchFather(intfather[],intstart)//查找start節(jié)點(diǎn)的父節(jié)點(diǎn){while(father[start]>0)start=father[start];returnstart;}6.1最小生成樹下面是克魯斯卡爾算法描述：6.1最小生成樹1．設(shè)置計數(shù)器count用于統(tǒng)計添加的邊的數(shù)量，初始化father數(shù)組，該數(shù)組用于記錄每個節(jié)點(diǎn)的父節(jié)點(diǎn)，初始值為0；2．通過鄰接矩陣構(gòu)造邊的數(shù)組，并將邊按照邊的權(quán)值升序排序；3．按照權(quán)值選取邊，如果當(dāng)前邊的起始節(jié)點(diǎn)的父節(jié)點(diǎn)不等于當(dāng)前邊的終點(diǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)，那么就可以把這條邊加入生成樹，計數(shù)器count加1，設(shè)置father數(shù)組；如果相等，表示如果加入這條邊會產(chǎn)生回路，則舍去這條邊，繼續(xù)取下一條邊；4．如果count等于圖的頂點(diǎn)數(shù)-1，根據(jù)樹的定義，則最小生成樹創(chuàng)建結(jié)束。以圖6-1為例，詳細(xì)說明克魯斯卡爾算法的實(shí)現(xiàn)過程，邊的數(shù)組edges元素如下表所示。以1（AF）為例，1（AF）表示edges[0]，1表示權(quán)值，A、F分別表示起點(diǎn)，終點(diǎn)。表6-1邊的數(shù)組edges6.1最小生成樹edges[0]edges[1]edges[2]edges[3]edges[4]edges[5]edges[6]edges[7]edges[8]edges[9]1（AF）2（BC）3（CF）3（DE）4（AB）4（EF）5（AE）5（BF）6（DF）6（CD）father數(shù)組初始值：（0，1，2，3，4，5分別對應(yīng)A,B,C,D,E,F結(jié)點(diǎn)）下標(biāo)0123450000006.1最小生成樹按照權(quán)值排序，依次選取邊：（1）選取edges[0]，判斷邊的起始節(jié)點(diǎn)的父節(jié)點(diǎn)和終點(diǎn)的父節(jié)點(diǎn)不相等，因此可以把AF這條邊加入到最小生成樹中，并且設(shè)置father[0]=5，即A點(diǎn)的父節(jié)點(diǎn)為F點(diǎn)。圖6-3加入第一條邊AFfather數(shù)組：下標(biāo)：0123455000006.1最小生成樹（2）選取edges[1]，判斷兩個點(diǎn)的父節(jié)點(diǎn)返回值不相等，因此可以把BC這條邊加入到最小生成樹中，并且father[1]=2圖6-4加入第二條邊BCfather數(shù)組：下標(biāo)：0

123455200006.1最小生成樹（3）選取edges[2]，判斷可以把CF這條邊加入到最小生成樹中，并且father[2]=5圖6-5加入第三條邊CFfather數(shù)組：下標(biāo)：0

123455250006.1最小生成樹（4）選取edges[3]，可以把DE這條邊加入到最小生成樹中，并且father[3]=4圖6-6加入第四條邊DEfather數(shù)組：下標(biāo)：0

123455254006.1最小生成樹（5）選取edges[4]，判斷兩個點(diǎn)的父節(jié)點(diǎn)返回值相等，因此可以判斷加入AB邊會形成回路，丟棄AB邊。圖6-7丟棄AB邊f(xié)ather數(shù)組：下標(biāo)：0

123455254006.1最小生成樹（6）選取edges[5]，可以加入EF邊。圖6-8加入第六條邊EFfather數(shù)組：下標(biāo)：0

12345525400（7）判斷出此時邊數(shù)等于頂點(diǎn)數(shù)減1，生成樹構(gòu)造完成。6.2最短路徑邊賦權(quán)圖經(jīng)常用來為實(shí)際生活中的網(wǎng)絡(luò)建模，如用邊的權(quán)值表示公路里程、造價或者通信線路的帶寬、數(shù)據(jù)傳輸時延等。很多時候，組成一條路徑的各邊權(quán)值之和具有某種物理意義，例如，代表連接兩個城市的公路總里程或者總造價，或者代表兩臺計算機(jī)之間的數(shù)據(jù)傳輸總時延。這時,往往需要找到兩點(diǎn)之間里程(造價、時延)最小的那條路徑,這就是最短路徑問題，最短路徑長度稱為源點(diǎn)到終點(diǎn)的距離。最短路徑問題十分復(fù)雜，為簡單起見，首先介紹單源最短路徑問題的Dijkstra算法。6.2.1Dijkstra算法單源最短路徑就是固定一個節(jié)點(diǎn)為源點(diǎn),求源點(diǎn)到圖中其他各個節(jié)點(diǎn)的最短路徑。單源最短路徑可構(gòu)成一棵根樹，源點(diǎn)為樹根。Dijkstra算法有個限制就是只討論邊權(quán)值為正實(shí)數(shù)的圖，下面以邊權(quán)值為正實(shí)數(shù)的有向圖為例，邊權(quán)值為正實(shí)數(shù)的無向圖，可以看成雙向的有向圖。Dijkstra算法描述如下所示：6.2.1Dijkstra算法1．對每個頂點(diǎn)進(jìn)行狀態(tài)標(biāo)記，初始化為0，如果已經(jīng)計算出最短路徑的點(diǎn)那么該點(diǎn)標(biāo)記為1，標(biāo)記為0的點(diǎn)是未確定最短路徑的點(diǎn)；2．使用鄰接矩陣w來描述賦權(quán)圖，一維數(shù)組dis存儲源點(diǎn)s到其它點(diǎn)的邊權(quán)值，初始值是w中的以s為源點(diǎn)的那一行；3．選取最小的數(shù)組中最小元素dis[x]（意味著源點(diǎn)s->x節(jié)點(diǎn)的路徑最短），并將此dis[x]邊對應(yīng)的點(diǎn)的標(biāo)記設(shè)置為1；4．把x作為中間點(diǎn)，找到與x相鄰的所有的節(jié)點(diǎn)，以相鄰節(jié)點(diǎn)y為例，對y做如下判斷：如果dis[y]>dis[x]+w[x][y]，那么更新dis[y]的值為dis[x]+w[x][y]。這一步驟的意思是，如果當(dāng)前已知的s->y的最短路徑的值大于源點(diǎn)s經(jīng)由x再到y(tǒng)的值，就意味著源點(diǎn)s經(jīng)由x再到y(tǒng)的路徑更短，那么dis[y]的值就由dis[x]+w[x][y]代替。與i相鄰的所有點(diǎn)都需完成這個步驟。5.重復(fù)3，4兩步，直到所有的點(diǎn)均標(biāo)記為1，此時dis中存儲的是源點(diǎn)到每個節(jié)點(diǎn)的最短路徑長度。6.2.1Dijkstra算法以圖6-9為例，下面將依據(jù)算法描述詳細(xì)分析算法的實(shí)現(xiàn)過程，初始狀態(tài)下，所有點(diǎn)的狀態(tài)標(biāo)記均為0,dis數(shù)組的值如下所示，描述的過程中為了說明問題的方便，使用頂點(diǎn)A、B、C、D、E、F作為數(shù)組下標(biāo)：。ABCDEF0∞∞∞∞∞圖6-9示例圖6.2.1Dijkstra算法1．第一次循環(huán)，A為源點(diǎn)，選取數(shù)組中最小值0，A頂點(diǎn)標(biāo)記為1，以A為中間點(diǎn)，出去三條邊分別指向B，C和E，分別計算AB、AC、AE,首先計算AB距離，dis[A]+w[A][B]=2，小于dis[B],更新dis[B]為2，以此類推，更新dis[C]為10，dis[E]為6。dis數(shù)組的值如下所示：ABCDEF0210∞6∞此時以A為中間點(diǎn)得到當(dāng)前到各個頂點(diǎn)的最短路徑如下：AB最短路徑：A->BAC最短路徑:A->CAE最短路徑:A->E圖6-10第一次循環(huán)6.2.1Dijkstra算法2．除去dis[A](因?yàn)锳已經(jīng)被標(biāo)記為1)從數(shù)組中選擇最短距離2(AB)，把B點(diǎn)標(biāo)記為1。選出點(diǎn)B，把B作為中間點(diǎn)，由B點(diǎn)出去兩條邊BE和BD,那么分別計算AD距離和AE距離。首先計算AD，從A出發(fā)，若經(jīng)過B到達(dá)D，距離是dis[B]+w[B][D]=5，小于dis[D](∞)，那么更新dis[D]為5；再計算AE,距離是dis[B]+w[B][E]=3，小于dis[E](6),更新dis[E]為3。dis數(shù)組的值如下所示：ABCDEF此時以B為中間點(diǎn)得到當(dāng)前到各個頂點(diǎn)的最短路徑如下：AB最短路徑：A->BAC最短路徑:A->CAD最短路徑:A->B->DAE最短路徑:A->B->E021053∞圖6-11第二次循環(huán)6.2.1Dijkstra算法3．除去dis[A]、dis[B],再選最短距離3(A到E)，選出E點(diǎn)，E點(diǎn)標(biāo)記為1，把E作為中間點(diǎn)，E往外有兩條邊，兩條邊指向C和F,那么分別計算AC距離和AF距離。首先計算AC,距離是dis[E]+w[E][C]=7，小于dis[C](10)，那么更新dis[C]為7；再計算AF,距離是dis[E]+w[E][F]=15，小于dis[F](∞),更新dis[F]為15。dis數(shù)組的值如下所示：ABCDEF此時以E為中間點(diǎn)得到當(dāng)前到各個頂點(diǎn)的最短路徑如下:AB最短路徑：A->BAC最短路徑：A->B->E->CAD最短路徑:A->B->DAE最短路徑:A->B->EAF最短路徑:A->B->E->F0275315圖6-12第三次循環(huán)6.2.1Dijkstra算法4．除去dis[A]、dis[B]、dis[E]，再選最短距離5(A到D)，選出D點(diǎn)，把D點(diǎn)標(biāo)記為1，D作為中間點(diǎn)，D往外有兩條邊，兩條邊指向E和F，因?yàn)镋已經(jīng)被標(biāo)記，那么只考慮AF距離。dis[D]+w[D][F]=37，大于dis[F](15)，因此dis[F]不變。dis數(shù)組的值如下所示：ABCDEF此時以D為中間點(diǎn)得到當(dāng)前到各個頂點(diǎn)的最短路徑如下:AB最短路徑：A->BAC最短路徑：A->B->E->CAD最短路徑:A->B->DAE最短路徑:A->B->EAF最短路徑:A->B->E->F0275315圖6-13第四次循環(huán)6.2.1Dijkstra算法5．除去dis[A]、dis[B]、dis[E]、dis[D]，選最短距離7(A到C)，選出C點(diǎn)，把C點(diǎn)標(biāo)記為1，C作為中間點(diǎn)，C往外有一條邊，指向F,dis[C]+w[C][F]=16，大于dis[F](15)，因此dis[F]不變。dis數(shù)組的值如下所示：ABCDEF此時以C為中間點(diǎn)得到當(dāng)前到各個頂點(diǎn)的最短路徑如下:AB最短路徑：A->BAC最短路徑：A->B->E->CAD最短路徑:A->B->DAE最短路徑:A->B->EAF最短路徑:A->B->E->F0275315圖6-14第五次循環(huán)6.2.1Dijkstra算法6．選取最小值15，以F為中間點(diǎn)，此時沒有出去的邊，將F點(diǎn)標(biāo)記為1，循環(huán)結(jié)束。AB最短路徑：A->BAD最短路徑:A->B->DAE最短路徑:A->B->EAC最短路徑：A->B->E->CAF最短路徑:A->B->E->F圖6-15第六次循環(huán)6.2.1Dijkstra算法只能使用Dijkstra算法求解權(quán)值為正的情況下的最短路徑長度。如果使用Dijkstra算法求解下圖AC的最短路徑長度，第一次循環(huán)標(biāo)記點(diǎn)A，數(shù)組dis={0，8，6}；第二次循環(huán)標(biāo)記C點(diǎn)，以C為中間點(diǎn)，但是沒有出去的邊；第三次循環(huán)，未標(biāo)記的只有B，此時標(biāo)記B點(diǎn)，到此AC的最短路徑就是6，而實(shí)際上AC最短路徑需要加入邊BC，AC的最短路徑長度是4，路徑應(yīng)該是A->B->C。圖6-16負(fù)權(quán)值的圖6.2.2使用優(yōu)先隊列的Dijkstra算法Dijkstra算法有大量時間都用在通過鄰接矩陣w找邊和搜索當(dāng)前最短路徑中。在搜索最短路徑時每次需要查找整個dis數(shù)組找到最小值。為了優(yōu)化算法，可以使用優(yōu)先級隊列(priority_queue)來完成查找dis數(shù)組中的最小值，也就是Dijkstra算法描述的第3步，優(yōu)先隊列是隊列的一種特殊形式，它滿足隊列的所有條件，區(qū)別于隊列的是優(yōu)先隊列中的元素按照某種特定順序排列，優(yōu)先級隊列的插入、刪除操作只需要logv的時間花費(fèi)，因此降低了不少運(yùn)行時間，因此使用優(yōu)先隊列的Dijkstra算法的時間復(fù)雜度為vlogv。6.2.3Bellman—Ford算法Dijkstra算法能解決單源最短路徑問題，但是它不能解決帶有負(fù)權(quán)邊（邊的權(quán)值為負(fù)數(shù)）的圖，而Bellman-Ford算法解決了邊為負(fù)權(quán)的問題。Bellman-Ford算法的核心代碼如下所示：1.for(j=1;j<=v-1;j++)//v表示節(jié)點(diǎn)數(shù)2.for(i=0;i<e;i++)//e表示邊數(shù)3.if(dis[edges[i].end]>dis[edges[i].start]+edges[i].value)4.dis[edges[i].end]=dis[edges[i].start]+edges[i].value;以下圖6-17為例分析該算法，這里假設(shè)A為源點(diǎn)。圖6-17示例圖6.2.3Bellman—Ford算法表6-2邊數(shù)組edges起點(diǎn)終點(diǎn)權(quán)值edges[0]CF9edges[1]EF-3edges[2]DF32edges[3]DE-6edges[4]EC4edges[5]BD3edges[6]AC-10edges[7]BE1edges[8]AE6edges[9]AB2dis數(shù)組初始值及對應(yīng)的最短路徑如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值0∞∞∞∞∞最短路徑

6.2.3Bellman—Ford算法（1）對每條邊第一輪循環(huán)后，dis數(shù)組值如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值02-10∞6∞最短路徑ABAC

AE（2）對每條邊第二輪循環(huán)后，dis數(shù)組值如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值02-1053-1最短路徑ABACABDABEACF（3）對每條邊第三輪循環(huán)后，dis數(shù)組值如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值02-105-1-1最短路徑ABACABDABDEACF（4）對每條邊第四輪循環(huán)后，頂點(diǎn)ABCDEFdis數(shù)組的值02-105-1-4最短路徑ABACABDABDEABDEF（5）對每條邊第五輪循環(huán)后，頂點(diǎn)ABCDEFdis數(shù)組的值02-105-1-4最短路徑ABACABDABDEABDEF6.2.3Bellman—Ford算法外循環(huán)需要循環(huán)v-1次，其中v表示頂點(diǎn)的個數(shù)，需要v-1次循環(huán)的原因是因?yàn)樵袋c(diǎn)到目的點(diǎn)之間的最短路徑最多包含v-1邊，如果超出v-1條邊，那么源點(diǎn)到目的點(diǎn)的路徑中存在有回路。第1輪循環(huán)對所有的邊進(jìn)行比之后，得到的是從A頂點(diǎn)“只能經(jīng)過一條邊”到達(dá)其余各頂點(diǎn)的最短路徑長度；第2輪對所有的邊進(jìn)行比較之后，得到的是從A頂點(diǎn)“最多經(jīng)過兩條邊”到達(dá)其余各頂點(diǎn)的最短路徑長度；以此類推。例如：A->B的最短路徑長度為1，那么必定在第一輪循環(huán)中求解出A->B最短路徑;A->E的最短路徑長度為3，那么最短路徑必定在第3輪循環(huán)結(jié)束前求解出，也就是說只可能在第1輪或者第2輪或者第3輪中求出，不可能在第4輪或者第5輪循環(huán)中求解出。

6.2.3Bellman—Ford算法Bellman-Ford算法可以解決賦權(quán)圖中包含負(fù)權(quán)回路的問題，例如下圖所示：圖6-18負(fù)權(quán)回路圖B->C->B形成了一個權(quán)值為-2的回路。如何去判斷是否存在負(fù)權(quán)回路呢？其實(shí)只需要在完成核心代碼的雙重循環(huán)后，再次對所有的邊進(jìn)行循環(huán)，計算dis數(shù)組，如果發(fā)現(xiàn)數(shù)組元素有變小的情況，那么就可以判定存在有負(fù)權(quán)回路。加入標(biāo)記flag，如果flag發(fā)生變化說明dis數(shù)組元素變?。篿ntflag=0;for(i=0;i<e;i++)//e表示邊數(shù)if(dis[edges[i].end]>dis[edges[i].start]+edges[i].value){//比較dis[edges[i].end]=dis[edges[i].start]+edges[i].value;flag=1}6.2.4Floyd算法Floyd算法適用于求解每對頂點(diǎn)之間的最短路徑，也就是多源最短路徑問題，算法采用動態(tài)規(guī)劃原理和逐步優(yōu)化技術(shù)，算法容易理解，實(shí)現(xiàn)也較為簡單。由前面的討論，很容易能想到任意節(jié)點(diǎn)i到j(luò)的最短路徑兩種可能：（1）直接從i到j(luò)；（2）從i經(jīng)過若干個節(jié)點(diǎn)k到j(luò)。Wij表示節(jié)點(diǎn)i到j(luò)最短路徑的距離，對于每一個節(jié)點(diǎn)k，判斷Wij>Wik+Wkj，如果成立，說明從i到中間點(diǎn)k，再由k點(diǎn)到j(luò)點(diǎn)的路徑比i到j(luò)不經(jīng)過中間點(diǎn)k的路徑短，那么Wij=Wik+Wkj；修改Pij的路徑，使得Pij為Pik連接Pkj。遍歷每個k，并作上述的操作。Floyd算法描述：voidFloyd(需要的參數(shù)){inti,j,k;for(i=0;i<v;i++)//v為頂點(diǎn)的個數(shù)for(j=0;j<v;j++){Wij=邊ij的長度；if(Wij不是無窮大)Pij=ij；elsePij=空}//加入中間點(diǎn)for（k=0;k<v;k++）for(i=0;i<v;i++)for(j=0;j<v;j++)if(Wij>Wik+Wkj){Wij=Wik+WkjPij=Pik鏈接Pkj}6.2.4Floyd算法Floyd算法對于邊權(quán)可正可負(fù)，無負(fù)權(quán)回路即可，運(yùn)行一次算法即可求得任意兩點(diǎn)間最短路。通過下面的例子給出Floyd算法的分析過程：圖6-20例圖表6-3鄰接矩陣W初始值

表6-4路徑矩陣初始值A(chǔ)BCA0215B∞04C6100ABCA

ABACB

BCCCACB6.2.4Floyd算法以A為中間點(diǎn)，執(zhí)行內(nèi)部的雙層循環(huán)，得到的路徑長度及路徑矩陣如下：表6-5鄰接矩陣W表6-6路徑矩陣ABCA0215B∞04C680ABCA

ABACB

BCCCACAB6.2.4Floyd算法以B為中間點(diǎn)，執(zhí)行內(nèi)部的雙層循環(huán)，得到的路徑長度及路徑矩陣如下：表6-7鄰接矩陣W表6-8路徑矩陣ABCA026B∞04C680ABCA

ABABCB

BCCCACAB以C為中間點(diǎn)，執(zhí)行內(nèi)部的雙層循環(huán)，得到的路徑長度及路徑矩陣如下：表6-9鄰接矩陣W表6-10路徑矩陣ABCA026B1004C680ABCA

ABABCBBCA

BCCCACAB6.2.4Floyd算法以B為中間點(diǎn)，執(zhí)行內(nèi)部的雙層循環(huán)，得到的路徑長度及路徑矩陣如下：矩陣W記錄頂點(diǎn)間的最小路徑，例如W[A][B]=10，說明頂點(diǎn)A到B的最短路徑為10；矩陣P記錄頂點(diǎn)間最小路徑中的中轉(zhuǎn)點(diǎn)。路徑P矩陣初始化時，如果i、j點(diǎn)之間沒有邊或者i=j那么，P[i][j]=-1，如果i、j有邊那么P[i][j]=i。Floyd算法的核心代碼如下：for(k=0;k<v;k++)for(i=0;i<v;i++)for(j=0;j<v;j++)if(W[i][j]>W[i][k]+W[k][j]){W[i][j]=W[i][k]+W[k][j];P[i][j]=P[k][j];}6.3最大匹配——匈牙利算法匹配是二分圖中的一組沒有公共端點(diǎn)的邊的集合。設(shè)G=<X,E,Y>為二分圖,M?E,如果M中任何兩條邊都沒有公共端點(diǎn),那么稱M為G的一個匹配。M=?時稱M為空匹配。G的所有匹配中邊數(shù)最多的匹配稱為最大匹配。如果X(Y)中任一頂點(diǎn)均為匹配M中邊的端點(diǎn),那么稱M為X(Y)完全匹配。若M既是X完全匹配又是Y完全匹配,則稱M為G的完全匹配。M中邊的端點(diǎn)稱為M-頂點(diǎn)，其它頂點(diǎn)稱為非M-頂點(diǎn)；M中的邊稱為匹配邊；其它邊稱為非匹配邊。設(shè)P是G中以vk為起點(diǎn)，vh為終點(diǎn)的一條通路，如果vh、vk均為非M-頂點(diǎn)，且P中非匹配邊與匹配邊交替出現(xiàn)，則稱P為G關(guān)于匹配M的一條交替鏈。當(dāng)某邊(u,v)的兩端點(diǎn)均為非M-頂點(diǎn)時，(u,v)也稱為交替鏈。求取最大匹配的經(jīng)典算法是匈牙利算法，其算法基本思想就是不斷尋找交替鏈，每找到一條交替鏈即將其中的匹配邊和非匹配邊對換，從而增加一條匹配邊，直至從初始匹配擴(kuò)充為最大匹配。6.3最大匹配——匈牙利算法以圖6-22為例，分析求解最大匹配的過程：圖6-22匹配初始狀態(tài)初始狀態(tài)下M={{x1,y1},{x2,y2}}，找到交替鏈(x3,y1,x1,y4),其中匹配邊{x1,y1},非匹配邊{x3,y1},{x1,y4}，置M={{x3,y1},{x1,y4},{x2,y2}}；圖6-23找到第一條交替鏈6.3最大匹配——匈牙利算法找到交替鏈(x4,y3)，置M={{x3,y1},{x1,y4},{x2,y2},{x4,y3}}；找到交替鏈(x5,y4,x1,y1,x3,y7)，其中匹配邊{x1,y4},{x3,y1};非匹配邊{x5,y4},{x1,y1},{x3,y7}，置M={{x4,y3},{x2,y2},{x5,y4},{x1,y1},{x3,y7}}；圖6-24找到第二條交替鏈圖6-25找到第三條交替鏈找不到可標(biāo)記頂點(diǎn)，M={{x4,y3},{x2,y2},{x5,y4},{x1,y1},{x3,y7}}已為最大匹配。6.3最大匹配——匈牙利算法下面是匈牙利算法的核心代碼：Map數(shù)組用于描述圖，i，j點(diǎn)分別為邊的起點(diǎn)、終點(diǎn)，flag數(shù)組用于描述i->j的邊是否被訪問過，p數(shù)組用于記錄該邊的起點(diǎn)。boolmatch(inti){for(intj=1;j<=N;++j)if(Map[i][j]&&!flag[j]){flag[j]=true;if(p[j]==0||match(p[j]))//如果暫無匹配，或者原來匹配的起始點(diǎn)可以找到新的匹配{p[j]=i;returntrue;//返回匹配成功}}returnfalse;找不到可標(biāo)記頂點(diǎn)，M={{x4,y3},{x2,y2},{x5,y4},{x1,y1},{x3,y7}}已為最大匹配。6.4本章小結(jié)求解最小生成樹問題、最短路徑問題、最大匹配問題都是現(xiàn)實(shí)生活中很常見的問題。在n個城市之間建造一個通信網(wǎng)絡(luò)、高速公路等，常常需要從多個涉及方案中選出一個造價成本最低的方案是最小生成樹問題的應(yīng)用；車站、賓館等公共場所設(shè)置的查詢系統(tǒng)，為網(wǎng)絡(luò)通信尋求最佳路由是最短路徑問題的應(yīng)用；找工作應(yīng)聘崗位，婚介所等涉及到最大匹配問題。這些問題的相關(guān)算法為我們解決實(shí)際問題提供了有力的支撐，因此圖論算法是不可或缺的知識點(diǎn)。6.4本章小結(jié)算法設(shè)計實(shí)例教程教學(xué)分析目錄CONCENTS123456789第7章動態(tài)規(guī)劃算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第5章字符串和高精度運(yùn)算第6章圖論算法第8章計算幾何基礎(chǔ)第9章高級算法動態(tài)規(guī)劃（DynamicProgramming，DP）是運(yùn)籌學(xué)的一個分支，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初，美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題等中取得了顯著的效果。本章主要介紹動態(tài)規(guī)劃的基本思想和概念、算法的原理和步驟以及常見的背包問題分析和解決方法。第7章動態(tài)規(guī)劃算法在現(xiàn)實(shí)生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線。這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃方法(DP，dynamicprogramming)。7.1基本思想和概念雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動態(tài)規(guī)劃方法所耗時間往往遠(yuǎn)少于樸素解法。通常在求解具有某種最優(yōu)性質(zhì)的問題時，可能會有許多可行解，每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。一般來說，只要問題可以劃分為規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解，則可以考慮用動態(tài)規(guī)劃解決。7.1基本思想和概念動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。7.1基本思想和概念

即子問題的解一旦確定，就不再改變，不受在這之后、包含它的更大的問題的求解決策影響。在使用動態(tài)規(guī)劃算法求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題反復(fù)計算多次，動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只計算一次，然后將其計算結(jié)果保存在一個表格中，當(dāng)再次需要計算已經(jīng)計算過的子問題時，只是在表格中簡單地查看一下結(jié)果，從而獲得較高的效率。因此，在使用動態(tài)規(guī)劃的時候，問題必須滿足以下條件：

7.1基本思想和概念1.最優(yōu)子結(jié)構(gòu)如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重要線索。2.無后效性動態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余的結(jié)合。因此，動態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲子問題的解，使得每個子問題只求解一次，最終獲得原問題的答案，以解決最優(yōu)化問題的算法策略。這一點(diǎn)與貪心算法和遞歸算法相比是類似的，但它們之間的區(qū)別在于貪心算法選擇當(dāng)前最優(yōu)解，而動態(tài)規(guī)劃通過求解局部子問題的最優(yōu)解來達(dá)到全局最優(yōu)解。在計算過程中遞歸算法需要對子問題進(jìn)行重復(fù)計算，需要耗費(fèi)更多的時間與空間，而動態(tài)規(guī)劃對每個子問題只求解一次。雖然可以對遞歸法進(jìn)行優(yōu)化，使用記憶化搜索的方式減少重復(fù)計算，但在解決重疊子問題時，本質(zhì)上記憶化搜索的遞歸算法是自頂向下的解決問題，而動態(tài)規(guī)劃算法則是自底向上的解決問題。7.2算法原理和步驟下面通過一個例子來說明動態(tài)規(guī)劃算法的基本原理?，F(xiàn)在有一段長度為n的木材，要將其切割后售出，木材長度與價格的對應(yīng)關(guān)系如下表，問如何切割能獲得最大收益。7.2算法原理和步驟長度i12345678910價格pi1589101717202430根據(jù)對價格表進(jìn)行分析，發(fā)現(xiàn)當(dāng)木材長度為10時單位長度的價格最高，當(dāng)木材長度為6時單位長度的價格第二高，其單位長度的價格的排序依次是10>6>3，9>2，8>7>4>5>1。根據(jù)貪心算法策略，木材切割后單位長度的價格越高越好，所以切割的方案應(yīng)該是先全切長度為10的木材，剩下的木材長度不足10的按照單位長度的價格高低來選擇切割長度。如果用分治思想的采用遞歸算法策略，設(shè)計一個遞歸函數(shù)，函數(shù)輸入當(dāng)前切割木材的價值和未切割木材的長度，輸出最優(yōu)收益。當(dāng)未切割木材的長度為0的時候，遞歸停止。有了這個遞歸函數(shù)之后，問題其實(shí)就是遍歷所有的切割方案，尋找其中收益最高的方案。代碼如下：intn,maxGet;intprice[11]={0,1,5,8,9,10,17,20,24,30};voiddfs(intcur,intrm)//cur:當(dāng)前已切割木材的價值；rm:等待切割的木材長度{if(rm==0)maxGet=max(maxGet,cur);for(inti=1;i<=rm;i++)dfs(cur+price[i],rm-i);}intmain(){cin>>n;maxGet=-1;dfs(0,n);cout<<”最優(yōu)收益為：”<<maxGet;}7.2算法原理和步驟不難發(fā)現(xiàn)，在遞歸展開過程會遇到很多的重復(fù)計算。隨著我們整個遞歸過程的展開，重復(fù)計算的次數(shù)會呈倍數(shù)增長。這種方法會枚舉2n-1種可能，結(jié)合求解結(jié)構(gòu)樹可以計算時間復(fù)雜度為O(2n)。既然是重復(fù)計算導(dǎo)致的時間代價過高，我們自然會想到將計算結(jié)果進(jìn)行“緩存”的方案，對遞歸過程中的中間結(jié)果進(jìn)行緩存，確保相同的情況只會被計算一次的做法，稱為記憶化搜索。代碼如下：intn,maxGet[11];//maxGet[k]表示切割長度為k的木材最大收益intprice[11]={0,1,5,8,9,10,17,20,24,30};intdfsMemory(intrm){if(maxGet[rm]!=-1)//此子問題已解決過returnmaxGet[rm];if(rm==0)return0;for(inti=1;i<=rm;i++)maxGet[rm]=max(maxGet[rm],price[i]+dfs(rm-i));returnmaxGet[rm];}intmain(){cin>>n;memset(maxGet,-1,sizeofmaxGet);maxGet[n]=dfs(n);cout<<”最優(yōu)收益為：”<<maxGet[n]<<endl;}7.2算法原理和步驟做了這樣的改進(jìn)之后，其實(shí)整個求解過程對于每個情況的訪問次數(shù)并沒有發(fā)生改變，只是從“以前的每次訪問都進(jìn)行求解”改進(jìn)為“只有第一次訪問才真正求解”。我們無法直觀確定哪個點(diǎn)的結(jié)果會在什么時候被訪問，被訪問多少次，所以我們不得不使用一個數(shù)組，將所有中間結(jié)果“緩存”起來。換句話說，記憶化搜索解決的是重復(fù)計算的問題，并沒有解決結(jié)果訪問時機(jī)和訪問次數(shù)的不確定問題。這種情況是由于我們采用的是“自頂向下”的解決思路所導(dǎo)致的，如果我們轉(zhuǎn)變思路，從“自頂向下”轉(zhuǎn)換換成“自底向上”，就能明確中間結(jié)果的訪問時機(jī)和訪問次數(shù)，那可以大大降低算法的空間復(fù)雜度，這就是動態(tài)規(guī)劃。動態(tài)規(guī)劃算法采用最優(yōu)化原則來建立遞歸關(guān)系式，在得到最優(yōu)的遞歸式之后，執(zhí)行回溯過程構(gòu)造最優(yōu)解。在這個例子中，得到的最優(yōu)遞歸式為：maxGet[i]=maxGet[i-k]+maxGet[k]代碼如下：intprice[11]={0,1,5,8,9,10,17,17,20,24,30}intdp(intn){intmaxgET[11];//maxGet[k]切割長度為k的木材最大收益memset(maxGet,-1,sizeofmaxGet);maxGet[0]=0;//dpfor(inti=1;i<=n;i++){for(intj=1;j<=n;j++)maxGet[i]=max(maxGet[i],price[j]+maxGet[i-j]);}returnmaxGet[n];}intmain(){intn;cin>>n;cout<<“最優(yōu)收益為：”<<dp(n)<<endl;}7.2算法原理和步驟這樣的解法的時間復(fù)雜度為O(2n)。動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其他的算法。選擇動態(tài)規(guī)劃算法是因?yàn)閯討B(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。從上面的例子可以總結(jié)出動態(tài)規(guī)劃算法解決問題一般分為以下四個步驟：1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2）遞歸的定義最優(yōu)解；3）以自底向上的方式計算出最優(yōu)解；4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。在動態(tài)規(guī)劃算法解決問題過程中，還需考慮以下問題：定義狀態(tài)：根據(jù)具體需解決的問題確定計算過程中每次計算值的含義，在上面的例子中，切割長度為k的木材最大收益就是其的狀態(tài)；狀態(tài)轉(zhuǎn)移：確定每個狀態(tài)之間的關(guān)系，即說明當(dāng)前的狀態(tài)是由之前哪些狀態(tài)計算得到的，在上面的例子中，maxGet[i]=maxGet[i-k]+maxGet[k]就表示了i狀態(tài)是怎么計算得到的；起始值：確定計算過程中哪些狀態(tài)是可以直接得到結(jié)果的，在上面的例子中，maxGet[0]=0是可以直接得到的，是計算的初始值。7.2算法原理和步驟背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。我們先來研究一下背包問題的數(shù)學(xué)模型，給定一組n個物品，每個物品都有自己的重量wi和價值vi，在限定總重量C范圍內(nèi)，選擇其中若干個物品（也即每種物品可以選0個或1個），設(shè)計選擇方案使得物品的總價值最高。問題可以抽象表述為給定正整數(shù){(wi,vi)}1≤i≤n，給定正整數(shù)C，求解0-1規(guī)劃問題：7.30-1背包問題使用動態(tài)規(guī)劃解決背包問題核心是怎么把實(shí)際問題轉(zhuǎn)化成為一個多階段決策問題，找到可重復(fù)計算的子問題，從而找到遞歸定義的問題最優(yōu)解。首先需要根據(jù)題意定義子問題，定義P(i,W)為：在前i個

個物品中挑選總重量不超過W的問題，每種物品至多只能挑選1個，使得總價值最大，這時的最優(yōu)值記作m(i,w)，其中1≤i≤n，1≤w≤C。從集合的角度來理解動態(tài)規(guī)劃問題，動態(tài)規(guī)劃中的每一個狀態(tài)都表示一個集合，背包問題就是所有選法的集合。這時候我們需要考慮在挑選完第i個物品后狀態(tài)發(fā)生的變化，即狀態(tài)轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移抽象后就得到了遞歸定義的問題最優(yōu)解。當(dāng)我們考慮第i個物品時，一共有兩種可能，選擇該物品放入包中，或者不選。7.3.10-1背包問題的多階段決策選擇第i個物品，背包的空余重量變小，背包里面物品價值發(fā)生變化，狀態(tài)發(fā)生變化導(dǎo)致子問題也隨之發(fā)生變化，P(i-1,W-wi)；不選第i個物品，背包的空余重量不變，背包里面物品價值不發(fā)生，狀態(tài)發(fā)生變化導(dǎo)致子問題也隨之發(fā)生變化，P(i-1,W)。問題最優(yōu)解就是比較這兩種方案，哪種最優(yōu)，如圖7-1所示。7.3.10-1背包問題的多階段決策圖7-10-1背包問題狀態(tài)轉(zhuǎn)移過程很顯然這是一個遞推的過程，考慮初始狀態(tài)以及結(jié)束狀態(tài)，整個過程可以用下面方程表示：7.3.10-1背包問題的多階段決策在經(jīng)過動態(tài)規(guī)劃得到遞歸定義的問題最優(yōu)解后，就可以實(shí)現(xiàn)0-1背包問題的算法：7.3.2規(guī)劃方向Input：n，w1，...wn，v1，...vn，C

forW=0toC初始化最優(yōu)值m[0，W]=0

fori=0ton

m[i，0]=0

fori=0ton

forW=1toC

if(wi>W)

m[i，W]=m[i-1，W]

else

m[i，W]=max{m[i-1，W]，vi+m[i-1，W-wi]}

returnm[n，C]在算法中有兩個遍歷維度：物品和背包重量，算法中描述的是先遍歷物品，然后遍歷背包重量，那么先遍歷背包，再遍歷物品行不行呢？想弄清楚這個問題，先要理解遞歸的本質(zhì)和遞推的方向。假設(shè)問題的數(shù)值例子如下：：7.3.2規(guī)劃方向Itemvalueweight111262318542265287其中C=11，之前的例子填表的結(jié)果如下：圖7-20-1背包問題數(shù)值遍歷過程示意圖藍(lán)色的格子表示本行值發(fā)生變化的格子。當(dāng)m[i，W]=vi+m[i-1，W-wi]時才會有“取走第i件物品”發(fā)生，所以所以從表格右下角“往回看”如果是“垂直下降”就是發(fā)生了m[i，W]=m[i-1，W]，而只有“走斜線”才是“取了”物品，如圖7-3所示。7.3.2規(guī)劃方向圖7-30-1背包問題遍歷過程方向示意圖根據(jù)上圖可以發(fā)現(xiàn)，無論是先遍歷物品再遍歷背包，還是先遍歷背包再遍歷物品的過程