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

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

21 }

22 }

23 if(j==t_len)

24 returni-t_len;//返回下標(biāo)開始比對(duì)的位置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位失配時(shí)，默認(rèn)把T串整體后移一位。但在前一輪的比較中，已經(jīng)知道T的第j位之前的字符段與S中間對(duì)應(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)建一個(gè)next數(shù)組，用來存儲(chǔ)j位置失配時(shí)下次重新匹配的位置next[j]。next[j]中的j表示當(dāng)前失配的位置，next[j]表示下次重新開始匹配時(shí)的位置。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。為了能遍歷完整，首尾重合部分的元素個(gè)數(shù)應(yīng)取到最多，例如“ababa”的首尾重合的字符串是“aba”，而不是“a”，但是也必須小于“ababa”，所以next[j]應(yīng)取盡量大的值，那么求解next[j]的公式如下所示：5.1.2KMP模式匹配圖5-6next數(shù)組的計(jì)算假設(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同時(shí)向前移動(dòng)繼續(xù)匹配j=next[j];//如果匹配不成功，索引i位置不變，下次重新開始匹配的位置為next[j]}5.1.2KMP模式匹配下面就是要求解next數(shù)組。很容易想到的方法，就是把T[0,j-1]的所有后綴子串找出來，依次看看是否能跟T[0,j-1]的前綴子串匹配。很顯然，這個(gè)方法也可以計(jì)算得到next數(shù)組，但是效率非常低。下面的方法可以較為高效地計(jì)算出next數(shù)組。假設(shè)現(xiàn)在要求next[8]，next[8]之前的數(shù)組元素已經(jīng)計(jì)算出結(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ù)組計(jì)算的時(shí)間復(fù)雜度是O(t_len)，匹配過程的時(shí)間復(fù)雜度是O(s_len)，KMP算法的時(shí)間復(fù)雜度是O(t_len+s_len)。樸素模式匹配算法簡單，時(shí)間復(fù)雜度是O(t_len*s_len)，在實(shí)際的軟件開發(fā)中，因?yàn)檫@種算法實(shí)現(xiàn)簡單，對(duì)于處理小規(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ì)算機(jī)內(nèi)數(shù)據(jù)存儲(chǔ)的最大值都是有限的，比如longlong類型是8個(gè)字節(jié)，它能表示的整數(shù)范圍為-9223372036854775808~9223372036854775807。如果需要計(jì)算的數(shù)據(jù)繼續(xù)增大，我們該怎么辦呢？這種問題屬于大數(shù)求和問題。所謂大數(shù)是指數(shù)的位數(shù)超過了計(jì)算機(jī)中基本數(shù)據(jù)類型的表示范圍。大數(shù)運(yùn)算就是大數(shù)進(jìn)行加、減、乘、除等一系列的運(yùn)算。5.2高精度運(yùn)算在小學(xué)我們就學(xué)過通過列豎式求兩個(gè)數(shù)的和。例如，列豎式計(jì)算整數(shù)9223372036854775808+1234的值，參加圖8.3。5.2.1小學(xué)時(shí)候的計(jì)算方法-“列豎式”圖5-9列豎式計(jì)算“9223372036854775808+1234”5.2.1小學(xué)時(shí)候的計(jì)算方法-“列豎式”我們首先需要將被加數(shù)和加數(shù)的數(shù)位靠右對(duì)齊，然后由右至左依次計(jì)算每個(gè)數(shù)位，如果超過10就產(chǎn)生進(jìn)位。如果我們將兩個(gè)整數(shù)逆序書寫，然后列豎式計(jì)算，得到的結(jié)果也是逆序的，參見圖5.4。圖5-10列豎式逆序計(jì)算“9223372036854775808+1234”如果我們把這兩個(gè)整數(shù)的每個(gè)數(shù)位按照字符逆序存儲(chǔ)在兩個(gè)數(shù)組中，然后讓這兩個(gè)數(shù)組對(duì)應(yīng)的數(shù)位進(jìn)行累加計(jì)算，并將結(jié)果存儲(chǔ)在第3個(gè)數(shù)組中，那么逆序輸出第3個(gè)數(shù)組中的字符就可以得到大數(shù)計(jì)算的結(jié)果。例如，分別用字符數(shù)組a，b，c逆序存儲(chǔ)被加數(shù)9223372036854775808、加數(shù)1234、和，參見圖8.5。5.2.1小學(xué)時(shí)候的計(jì)算方法-“列豎式”圖5.11用數(shù)組存儲(chǔ)被加數(shù)、加數(shù)與和數(shù)組c中每個(gè)元素的初始值為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，同時(shí)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，同時(shí)c[1]=1。依次計(jì)算出數(shù)組c中所有元素的值，參見圖5.6。圖5.12用數(shù)組實(shí)現(xiàn)大數(shù)計(jì)算利用數(shù)組來實(shí)現(xiàn)兩個(gè)大數(shù)求和運(yùn)算的方法被稱為數(shù)組法。大數(shù)求和的基本思想是：使用字符數(shù)組來保存用戶的輸入數(shù)字和運(yùn)算結(jié)果，將兩個(gè)大數(shù)的每一位數(shù)字分別存儲(chǔ)在兩個(gè)數(shù)組中，然后模擬人工列豎式算加法的方式，對(duì)兩個(gè)數(shù)組的數(shù)組元素從最低位開始相加，并判斷是否進(jìn)位，一直到最高位結(jié)束。5.2.1小學(xué)時(shí)候的計(jì)算方法-“列豎式”【例5.3】數(shù)組法求兩個(gè)大整數(shù)的和。問題分析：從鍵盤以字符串的方式將兩個(gè)大數(shù)讀入到數(shù)組a和數(shù)組b中。設(shè)計(jì)一個(gè)逆序函數(shù)reverse對(duì)數(shù)組a和數(shù)組b中的字符串進(jìn)行逆序排列。設(shè)計(jì)一個(gè)bigDataSum函數(shù)完成“列豎式”計(jì)算。算法設(shè)計(jì)：算法描述參見圖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)槟嫘颍灰獙⑹孜蚕鄬?duì)應(yīng)位置的數(shù)組元素位置對(duì)調(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ù)組元素按照首尾相對(duì)應(yīng)位置做對(duì)調(diào){temp=a[i];//從首部0開始第i個(gè)元素與從尾部len-1倒數(shù)第i個(gè)元素len-1-i的位置對(duì)調(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中存儲(chǔ)的大數(shù)的字符串長度可能是不同的，也就是說兩個(gè)進(jìn)行計(jì)算的大數(shù)的數(shù)位長度可能是不同的。在“列豎式”計(jì)算的時(shí)候，兩個(gè)數(shù)組元素中的字符數(shù)字需要先轉(zhuǎn)換成整數(shù)，然后再求和，最后判斷是否需要進(jìn)位。另外，兩個(gè)數(shù)組的數(shù)位對(duì)齊后，非對(duì)齊數(shù)位和對(duì)齊數(shù)位的處理方法是不同的，因此需要先判斷數(shù)組a和數(shù)組b中大數(shù)數(shù)位的長短。5.2.2大數(shù)求和的程序?qū)崿F(xiàn)bigDataSum函數(shù)有4個(gè)輸入數(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ù)和的算法階乘的精確計(jì)算：例如輸入不超過1000的正整數(shù)n，輸出的精確結(jié)果。例如輸入30輸出265252859812191058636308480000000當(dāng)輸入1000時(shí)1000的階乘約4*10^(2567)，大概3000位數(shù)字，如果采用普通的階乘算法很明顯溢出：intfun(intn){inti;ints=1;for(i=1;i<=n;i++)s*=i;returns;}//求n的階乘的普通算法5.2.3階乘的精確計(jì)算故需要引入高精度算法。引入一個(gè)大小3000的數(shù)字a_int，讓a_int[0]保留個(gè)位，讓a_int[1]保留十位，讓a_int[2]保留百位……為什么要這么做，可作以下分析：當(dāng)n=1時(shí)，最終結(jié)果1，a_int[0]=1，其他位0即可。當(dāng)n=2時(shí)，最終結(jié)果2，a_int[0]=2，其他位0即可。當(dāng)n=3時(shí)，最終結(jié)果6，a_int[0]=6，其他位0即可。當(dāng)n=4時(shí)，最終結(jié)果24，a_int[0]=24，此時(shí)需要十位和個(gè)位拆開，a_int[0]=4，a_int[1]=2，其他位0即可。當(dāng)n=5時(shí)，最終結(jié)果120，此時(shí)a_int[0]=4，a_int[1]=2，其他位0，即120=24*5，4*5=20的個(gè)位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個(gè)數(shù)據(jù)單元里即i!=a_int[j]a_int[j-1]...a_int[2]a_int[1]a_int[0]，故輸入i+1時(shí)，按照要求：(i+1)，可寫出此時(shí)乘法豎式。5.2.3階乘的精確計(jì)算對(duì)于個(gè)位a_int[0]，a_int[0]*（i+1）所得數(shù)值取其個(gè)位保留在a_int[0]，剩余的位作為進(jìn)位。對(duì)于十位位a_int[1]，a_int[1]*（i+1）所得數(shù)值再加上個(gè)位的進(jìn)位取其個(gè)位保留在a_int[1]，剩余的位作為進(jìn)位。對(duì)于第k位a_int[k-1]，a_int[k-1]*（i+1）所得數(shù)值取其個(gè)位保留在a_int[k-1]，剩余的位作為進(jìn)位。5.2.3階乘的精確計(jì)算應(yīng)用舉例時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述輸入一個(gè)正整數(shù)n，輸出n!的值。 其中n!=1*2*3*…*n。輸入格式 輸入包含一個(gè)正整數(shù)n，n<=1000。輸出格式 輸出n!的準(zhǔn)確值。樣例輸入10樣例輸出36288005.2.3階乘的精確計(jì)算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ù)之前在這個(gè)位置上的數(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ì)算機(jī)技術(shù)應(yīng)用的發(fā)展，海量數(shù)據(jù)的處理需求的出現(xiàn)，使得字符匹配算法越來越重要，通常希望匹配算法越快越好。在網(wǎng)絡(luò)速度迅速發(fā)展的今天，基于字符匹配技術(shù)的網(wǎng)絡(luò)應(yīng)用存在著性能瓶頸，各種各樣的匹配算法不斷出現(xiàn)提高系統(tǒng)的整體性能是研究和設(shè)計(jì)者的主要工作。由于現(xiàn)有計(jì)算編程語言的數(shù)據(jù)類型限制，對(duì)于大數(shù)據(jù)的存儲(chǔ)能力與計(jì)算能力有限。所以進(jìn)行大數(shù)據(jù)運(yùn)算時(shí)，大數(shù)據(jù)計(jì)算的一般思路為：將大數(shù)據(jù)拆分成多個(gè)小數(shù)據(jù)，使用編輯語言能夠計(jì)算的小數(shù)據(jù)進(jìn)行計(jì)算，再將小數(shù)據(jù)合并成大數(shù)據(jù)。。5.3本章小結(jié)算法設(shè)計(jì)實(shí)例教程教學(xué)分析目錄CONCENTS123456789第6章圖論算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第5章字符串和高精度運(yùn)算第7章動(dòng)態(tài)規(guī)劃算法第8章計(jì)算幾何基礎(chǔ)第9章高級(jí)算法圖論〔GraphTheory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖是由若干給定的點(diǎn)及連接兩點(diǎn)的邊所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的邊表示相應(yīng)兩個(gè)事物間具有某種關(guān)系。在計(jì)算機(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)介紹圖論中的最小生成樹、最短路徑、最大匹配等問題使用到的算法等知識(shí)。第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)用價(jià)值，例如用最低的造價(jià)建造公路把n個(gè)城市連接起來、用最低成本的線路將n個(gè)站點(diǎn)連成一個(gè)網(wǎng)絡(luò)，等等。下面介紹求解最小生成樹的經(jīng)典算法--克魯斯克爾(Kruskal)算法，該算法由JosephKruskal在1956年發(fā)表。6.1最小生成樹Kruskal算法簡單直觀，算法的基本思想是：首先將邊的權(quán)值從小到大的排序，然后逐邊將它們放回到所關(guān)聯(lián)的頂點(diǎn)上，每次添加一條邊之前需要檢查添加的這條邊是否會(huì)產(chǎn)生回路。如果產(chǎn)生回路，那么就舍棄這條邊，選擇下一條邊，直至產(chǎn)生一個(gè)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)用于存儲(chǔ)每條邊及其權(quán)值，每條邊可以通過邊的兩個(gè)端點(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)值升序排序。為了判斷添加某邊是否會(huì)產(chǎn)生回路，定義了一個(gè)尋找某節(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è)置計(jì)數(shù)器count用于統(tǒng)計(jì)添加的邊的數(shù)量，初始化father數(shù)組，該數(shù)組用于記錄每個(gè)節(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)，那么就可以把這條邊加入生成樹，計(jì)數(shù)器count加1，設(shè)置father數(shù)組；如果相等，表示如果加入這條邊會(huì)產(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分別對(duì)應(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]，判斷兩個(gè)點(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]，判斷兩個(gè)點(diǎn)的父節(jié)點(diǎn)返回值相等，因此可以判斷加入AB邊會(huì)形成回路，丟棄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í)邊數(shù)等于頂點(diǎn)數(shù)減1，生成樹構(gòu)造完成。6.2最短路徑邊賦權(quán)圖經(jīng)常用來為實(shí)際生活中的網(wǎng)絡(luò)建模，如用邊的權(quán)值表示公路里程、造價(jià)或者通信線路的帶寬、數(shù)據(jù)傳輸時(shí)延等。很多時(shí)候，組成一條路徑的各邊權(quán)值之和具有某種物理意義，例如，代表連接兩個(gè)城市的公路總里程或者總造價(jià)，或者代表兩臺(tái)計(jì)算機(jī)之間的數(shù)據(jù)傳輸總時(shí)延。這時(shí),往往需要找到兩點(diǎn)之間里程(造價(jià)、時(shí)延)最小的那條路徑,這就是最短路徑問題，最短路徑長度稱為源點(diǎn)到終點(diǎn)的距離。最短路徑問題十分復(fù)雜，為簡單起見，首先介紹單源最短路徑問題的Dijkstra算法。6.2.1Dijkstra算法單源最短路徑就是固定一個(gè)節(jié)點(diǎn)為源點(diǎn),求源點(diǎn)到圖中其他各個(gè)節(jié)點(diǎn)的最短路徑。單源最短路徑可構(gòu)成一棵根樹，源點(diǎn)為樹根。Dijkstra算法有個(gè)限制就是只討論邊權(quán)值為正實(shí)數(shù)的圖，下面以邊權(quán)值為正實(shí)數(shù)的有向圖為例，邊權(quán)值為正實(shí)數(shù)的無向圖，可以看成雙向的有向圖。Dijkstra算法描述如下所示：6.2.1Dijkstra算法1．對(duì)每個(gè)頂點(diǎn)進(jìn)行狀態(tài)標(biāo)記，初始化為0，如果已經(jīng)計(jì)算出最短路徑的點(diǎn)那么該點(diǎn)標(biāo)記為1，標(biāo)記為0的點(diǎn)是未確定最短路徑的點(diǎn)；2．使用鄰接矩陣w來描述賦權(quán)圖，一維數(shù)組dis存儲(chǔ)源點(diǎn)s到其它點(diǎn)的邊權(quán)值，初始值是w中的以s為源點(diǎn)的那一行；3．選取最小的數(shù)組中最小元素dis[x]（意味著源點(diǎn)s->x節(jié)點(diǎn)的路徑最短），并將此dis[x]邊對(duì)應(yīng)的點(diǎn)的標(biāo)記設(shè)置為1；4．把x作為中間點(diǎn)，找到與x相鄰的所有的節(jié)點(diǎn)，以相鄰節(jié)點(diǎn)y為例，對(duì)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)都需完成這個(gè)步驟。5.重復(fù)3，4兩步，直到所有的點(diǎn)均標(biāo)記為1，此時(shí)dis中存儲(chǔ)的是源點(diǎn)到每個(gè)節(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，分別計(jì)算AB、AC、AE,首先計(jì)算AB距離，dis[A]+w[A][B]=2，小于dis[B],更新dis[B]為2，以此類推，更新dis[C]為10，dis[E]為6。dis數(shù)組的值如下所示：ABCDEF0210∞6∞此時(shí)以A為中間點(diǎn)得到當(dāng)前到各個(gè)頂點(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,那么分別計(jì)算AD距離和AE距離。首先計(jì)算AD，從A出發(fā)，若經(jīng)過B到達(dá)D，距離是dis[B]+w[B][D]=5，小于dis[D](∞)，那么更新dis[D]為5；再計(jì)算AE,距離是dis[B]+w[B][E]=3，小于dis[E](6),更新dis[E]為3。dis數(shù)組的值如下所示：ABCDEF此時(shí)以B為中間點(diǎn)得到當(dāng)前到各個(gè)頂點(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,那么分別計(jì)算AC距離和AF距離。首先計(jì)算AC,距離是dis[E]+w[E][C]=7，小于dis[C](10)，那么更新dis[C]為7；再計(jì)算AF,距離是dis[E]+w[E][F]=15，小于dis[F](∞),更新dis[F]為15。dis數(shù)組的值如下所示：ABCDEF此時(shí)以E為中間點(diǎn)得到當(dāng)前到各個(gè)頂點(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此時(shí)以D為中間點(diǎn)得到當(dāng)前到各個(gè)頂點(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此時(shí)以C為中間點(diǎn)得到當(dāng)前到各個(gè)頂點(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)，此時(shí)沒有出去的邊，將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，此時(shí)標(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)先隊(duì)列的Dijkstra算法Dijkstra算法有大量時(shí)間都用在通過鄰接矩陣w找邊和搜索當(dāng)前最短路徑中。在搜索最短路徑時(shí)每次需要查找整個(gè)dis數(shù)組找到最小值。為了優(yōu)化算法，可以使用優(yōu)先級(jí)隊(duì)列(priority_queue)來完成查找dis數(shù)組中的最小值，也就是Dijkstra算法描述的第3步，優(yōu)先隊(duì)列是隊(duì)列的一種特殊形式，它滿足隊(duì)列的所有條件，區(qū)別于隊(duì)列的是優(yōu)先隊(duì)列中的元素按照某種特定順序排列，優(yōu)先級(jí)隊(duì)列的插入、刪除操作只需要logv的時(shí)間花費(fèi)，因此降低了不少運(yùn)行時(shí)間，因此使用優(yōu)先隊(duì)列的Dijkstra算法的時(shí)間復(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ù)組初始值及對(duì)應(yīng)的最短路徑如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值0∞∞∞∞∞最短路徑

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

AE（2）對(duì)每條邊第二輪循環(huán)后，dis數(shù)組值如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值02-1053-1最短路徑ABACABDABEACF（3）對(duì)每條邊第三輪循環(huán)后，dis數(shù)組值如下所示：頂點(diǎn)ABCDEFdis數(shù)組的值02-105-1-1最短路徑ABACABDABDEACF（4）對(duì)每條邊第四輪循環(huán)后，頂點(diǎn)ABCDEFdis數(shù)組的值02-105-1-4最短路徑ABACABDABDEABDEF（5）對(duì)每條邊第五輪循環(huán)后，頂點(diǎn)ABCDEFdis數(shù)組的值02-105-1-4最短路徑ABACABDABDEABDEF6.2.3Bellman—Ford算法外循環(huán)需要循環(huán)v-1次，其中v表示頂點(diǎn)的個(gè)數(shù)，需要v-1次循環(huán)的原因是因?yàn)樵袋c(diǎn)到目的點(diǎn)之間的最短路徑最多包含v-1邊，如果超出v-1條邊，那么源點(diǎn)到目的點(diǎn)的路徑中存在有回路。第1輪循環(huán)對(duì)所有的邊進(jìn)行比之后，得到的是從A頂點(diǎn)“只能經(jīng)過一條邊”到達(dá)其余各頂點(diǎn)的最短路徑長度；第2輪對(duì)所有的邊進(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形成了一個(gè)權(quán)值為-2的回路。如何去判斷是否存在負(fù)權(quán)回路呢？其實(shí)只需要在完成核心代碼的雙重循環(huán)后，再次對(duì)所有的邊進(jìn)行循環(huán)，計(jì)算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算法適用于求解每對(duì)頂點(diǎn)之間的最短路徑，也就是多源最短路徑問題，算法采用動(dòng)態(tài)規(guī)劃原理和逐步優(yōu)化技術(shù)，算法容易理解，實(shí)現(xiàn)也較為簡單。由前面的討論，很容易能想到任意節(jié)點(diǎn)i到j(luò)的最短路徑兩種可能：（1）直接從i到j(luò)；（2）從i經(jīng)過若干個(gè)節(jié)點(diǎn)k到j(luò)。Wij表示節(jié)點(diǎn)i到j(luò)最短路徑的距離，對(duì)于每一個(gè)節(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。遍歷每個(gè)k，并作上述的操作。Floyd算法描述：voidFloyd(需要的參數(shù)){inti,j,k;for(i=0;i<v;i++)//v為頂點(diǎn)的個(gè)數(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算法對(duì)于邊權(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矩陣初始化時(shí)，如果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的一個(gè)匹配。M=?時(shí)稱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)時(shí)，(u,v)也稱為交替鏈。求取最大匹配的經(jīng)典算法是匈牙利算法，其算法基本思想就是不斷尋找交替鏈，每找到一條交替鏈即將其中的匹配邊和非匹配邊對(duì)換，從而增加一條匹配邊，直至從初始匹配擴(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個(gè)城市之間建造一個(gè)通信網(wǎng)絡(luò)、高速公路等，常常需要從多個(gè)涉及方案中選出一個(gè)造價(jià)成本最低的方案是最小生成樹問題的應(yīng)用；車站、賓館等公共場所設(shè)置的查詢系統(tǒng)，為網(wǎng)絡(luò)通信尋求最佳路由是最短路徑問題的應(yīng)用；找工作應(yīng)聘崗位，婚介所等涉及到最大匹配問題。這些問題的相關(guān)算法為我們解決實(shí)際問題提供了有力的支撐，因此圖論算法是不可或缺的知識(shí)點(diǎn)。6.4本章小結(jié)算法設(shè)計(jì)實(shí)例教程教學(xué)分析目錄CONCENTS123456789第7章動(dòng)態(tài)規(guī)劃算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第5章字符串和高精度運(yùn)算第6章圖論算法第8章計(jì)算幾何基礎(chǔ)第9章高級(jí)算法動(dòng)態(tài)規(guī)劃（DynamicProgramming，DP）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初，美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動(dòng)化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題等中取得了顯著的效果。本章主要介紹動(dòng)態(tài)規(guī)劃的基本思想和概念、算法的原理和步驟以及常見的背包問題分析和解決方法。第7章動(dòng)態(tài)規(guī)劃算法在現(xiàn)實(shí)生活中，有一類活動(dòng)的過程，由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線。這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個(gè)階段采取的決策，一般來說是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過程為動(dòng)態(tài)規(guī)劃方法(DP，dynamicprogramming)。7.1基本思想和概念雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。通常在求解具有某種最優(yōu)性質(zhì)的問題時(shí)，可能會(huì)有許多可行解，每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。一般來說，只要問題可以劃分為規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解，則可以考慮用動(dòng)態(tài)規(guī)劃解決。7.1基本思想和概念動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。7.1基本思想和概念

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

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

個(gè)物品中挑選總重量不超過W的問題，每種物品至多只能挑選1個(gè)，使得總價(jià)值最大，這時(shí)的最優(yōu)值記作m(i,w)，其中1≤i≤n，1≤w≤C。從集合的角度來理解動(dòng)態(tài)規(guī)劃問題，動(dòng)態(tài)規(guī)劃中的每一個(gè)狀態(tài)都表示一個(gè)集合，背包問題就是所有選法的集合。這時(shí)候我們需要考慮在挑選完第i個(gè)物品后狀態(tài)發(fā)生的變化，即狀態(tài)轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移抽象后就得到了遞歸定義的問題最優(yōu)解。當(dāng)我們考慮第i個(gè)物品時(shí)，一共有兩種可能，選擇該物品放入包中，或者不選。7.3.10-1背包問題的多階段決策選擇第i個(gè)物品，背包的空余重量變小，背包里面物品價(jià)值發(fā)生變化，狀態(tài)發(fā)生變化導(dǎo)致子問題也隨之發(fā)生變化，P(i-1,W-wi)；不選第i個(gè)物品，背包的空余重量不變，背包里面物品價(jià)值不發(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)移過程很顯然這是一個(gè)遞推的過程，考慮初始狀態(tài)以及結(jié)束狀態(tài)，整個(gè)過程可以用下面方程表示：7.3.10-1背包問題的多階段決策在經(jīng)過動(dò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]在算法中有兩個(gè)遍歷維度：物品和背包重量，算法中描述的是先遍歷物品，然后遍歷背包重量，那么先遍歷背包，再遍歷物品行不行呢？想弄清楚這個(gè)問題，先要理解遞歸的本質(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]時(shí)才會(huì)有“取走第i件物品”發(fā)生，所以所以從表格右下角“往回看”如果是“垂直下降”就是發(fā)生了m[i，W]=m[i-1，W]，而只有“走斜線”才是“取了”物品，如圖7-3所示。7.3.2規(guī)劃方向圖7-30-1背包問題遍歷過程方向示意圖根據(jù)上圖可以發(fā)現(xiàn)，無論是先遍歷物品再遍歷背包，還是先遍歷背包再遍歷物品的過程