圖論算法及matlab程序的三個(gè)案例

圖論實(shí)驗(yàn)三個(gè)案例單源最短路徑問(wèn)題Dijkstra算法Dijkstra算法是解單源最短路徑問(wèn)題的一個(gè)貪心算法。其基本思想是，設(shè)置一個(gè)頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。設(shè)卜是圖中的一個(gè)頂點(diǎn)，記/(”為頂點(diǎn)/到源點(diǎn)看的最短距離，7匕，匕￡丫，若(斗，匕)右石，記匕到與的權(quán)%=8。Dijkstra算法：①S={匕}/(匕)=0；Vv^V-fvJ/(v)=ooy=i5=V-{v1}.②停止，否則轉(zhuǎn)③；③/(v)=nun{/(v),J(vpv)} Vv€J.④存在心］,使"％)=n1m"")},vg5.⑤s=sU{%i},s=s-{匕+j,j=j+i,轉(zhuǎn)②；實(shí)際上，Dijkstra算法也是最優(yōu)化原理的應(yīng)用：如果匕匕…匕是從匕到匕的最短路徑，則匕匕…匕t也必然是從匕到匕t的最優(yōu)路徑。在下面的MATLAB實(shí)現(xiàn)代碼中，我們用到了距離矩陣，矩陣第/行第/行元素表示頂點(diǎn)匕到與的權(quán)％,若匕到「無(wú)邊，則％=?lmax,其中小它是MATLAB常量，表示最大的實(shí)數(shù)+308)。functionre=Dijkstra(ma)%用Dijkstra算法求單源最短路徑睛俞入?yún)⒘縨a是距離矩陣睛俞出參量是一個(gè)三行n歹豚巨陣，每列表示頂點(diǎn)號(hào)及頂點(diǎn)到源的最短距離和前頂點(diǎn)"size(ma,1);%得到距離矩陣的維數(shù)s=ones(1fn);s(1)=0;%標(biāo)記集合S和S的補(bǔ)r=zeros(3,n);r(1,:)=1:n;r(2,2:end)二realmax;%初始化fori=2:n;%控制循環(huán)次數(shù)mm=reaImax;forj:find(s=0);%集合S中的頂點(diǎn)fork二吊次($二二1);%集合5補(bǔ)中的頂點(diǎn)if(r(2,j)+ma(jFk)<r(2,k))r(2,k)=r(2,j)+ma(j,k);r(3,k)=j;endif(mm>r(2,k))mm=r(2,k);t=k;endendends(1,t)=0;%找到最小的頂點(diǎn)加入集合Sendre=r;動(dòng)態(tài)規(guī)劃求解最短路徑動(dòng)態(tài)規(guī)劃是美國(guó)數(shù)學(xué)家RichardBelIman在1951年提出來(lái)的分析一類(lèi)多階段決策過(guò)程的最優(yōu)化方法，在工程技術(shù)、工業(yè)生產(chǎn)、經(jīng)濟(jì)管理、軍事及現(xiàn)代化控制工程等方面均有著廣泛的應(yīng)用。動(dòng)態(tài)規(guī)劃應(yīng)用了最佳原理：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出"個(gè)決策如若這個(gè)決策是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)4,1＜依〃，不論前面〃個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即也是最優(yōu)的。如圖1,從4點(diǎn)要鋪設(shè)一條管道到七點(diǎn)，中間必須要經(jīng)過(guò)5個(gè)中間站，第一站可以在｛4,4｝中任選一個(gè)，第二、三、四、五站可供選擇的地點(diǎn)分別是:(4,4,4,福，(4,4,4。｝,14,4，4｝,(人，4J。連接兩地管道的距離用連線上的數(shù)字表示，要求選一條從4到46的鋪管線路，使總距離最短。囪1BT*堪的笞潛囪解決此問(wèn)題可以用窮舉法，從4到公有48條路徑，只須比較47次，就可得到最短路徑為：4T4T4T4T42T45T4外最短距離為18。也可以使用Dijkstra算法。這里，我們動(dòng)態(tài)規(guī)劃解決此問(wèn)題。注意到最短路徑有這樣一個(gè)特性，即如果最短路徑的第〃站通過(guò)P*,則這一最短路徑在由P,出發(fā)到達(dá)終點(diǎn)的那一部分路徑，對(duì)于始點(diǎn)為P*到終點(diǎn)的所有可能的路徑來(lái)說(shuō),必定也是距離最短的。根據(jù)最短路徑這一特性,啟發(fā)我們計(jì)算時(shí)從最后一段開(kāi)始,從后向前逐步遞推的方法，求出各點(diǎn)到人的最短路徑。在算法中，我們用數(shù)組六元數(shù)組ss表示中間車(chē)站的個(gè)數(shù)(4也作為中間車(chē)站)，用距離矩陣path表示該圖。為簡(jiǎn)便起見(jiàn)，把該圖看作有向圖，各邊的方向均為從左到右，則path不是對(duì)稱(chēng)矩陣,如path(12,14)=5,而path(14,12)=0(用0表示不通道路)。用3，16矩陣spath表示算法結(jié)果，第一行表示結(jié)點(diǎn)序號(hào)，第二行表示該結(jié)點(diǎn)到終點(diǎn)的最短距離，第三行表示該結(jié)點(diǎn)到終點(diǎn)的最短路徑上的下一結(jié)點(diǎn)序號(hào)。下面給出MATLAB實(shí)現(xiàn)算法。function[scheme]二ShortestPath(path,ss)%利用動(dòng)態(tài)規(guī)劃求最短路徑%path是距離矩陣,ss是車(chē)站個(gè)數(shù)n=size(path,1);%結(jié)點(diǎn)個(gè)數(shù)scheme二zeros(3,n);先構(gòu)造結(jié)果矩陣scheme。，：)=1:n;%設(shè)置結(jié)點(diǎn)序號(hào)scheme(2,1:n-1)=reaImax;%預(yù)設(shè)距離值k=n-1;*記錄第一階段結(jié)點(diǎn)最大序號(hào)fori=size(ss,2) :1;%控制循環(huán)階段數(shù)forj=k：-1:(k-ss(i)+1)；%當(dāng)前階段結(jié)點(diǎn)循環(huán)fort=find(path。，：)>0);%當(dāng)前結(jié)點(diǎn)鄰接結(jié)點(diǎn)ifpath(jrt)+scheme(2rt)<scheme(2rj)scheme(2,j)=path(j,t)+scheme(2,t);scheme(3,j)=t;endendendk二k-ss(i);移入下一階段end先在MATLAB命令窗口中構(gòu)造距離矩陣path,再輸入：?ShortestPath(path,ss)得到以下結(jié)果：1 2 3 4 5 6 7 8 9 1011121314151618131613109 127 6 8 7 5 9 4 3 0

2 5 6 8 8 9 1012121214151516160將該結(jié)果表示為圖，即為圖1粗線所示。棋盤(pán)覆蓋問(wèn)題問(wèn)題的提出在一個(gè)》、2人?個(gè)方格組成的棋盤(pán)中，若恰有一個(gè)方格與其他方格不同，則稱(chēng)該方格為一特殊方格，且稱(chēng)該棋盤(pán)為一特殊的棋盤(pán)。如圖1就是當(dāng)攵=3時(shí)的特〔■IIIb們要用圖2所示4種不同形態(tài)的L形骨牌覆蓋一個(gè)不得重疊覆蓋。圖1當(dāng)仁3時(shí)的特殊棋盤(pán)(b)(c)圖1當(dāng)仁3時(shí)的特殊棋盤(pán)(b)(c)(d)囹24種不同形木的L型曾相問(wèn)題的分析易知，用到的L型骨牌個(gè)數(shù)恰為（邛-1）/3。利用分治策略，我們可以設(shè)計(jì)出解棋盤(pán)覆蓋問(wèn)題的一個(gè)簡(jiǎn)捷的算法。當(dāng)%>0時(shí)，我們將2*x2人棋盤(pán)分割為4個(gè)2^x21子棋盤(pán)如圖3兩粗實(shí)線所7J\o圖3棋盤(pán)分割7J\o圖3棋盤(pán)分割圖4關(guān)鍵結(jié)點(diǎn)特殊方格必位于4個(gè)較小子棋盤(pán)之一中，其余3個(gè)子棋盤(pán)中無(wú)特殊方格。為了將這3個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，我們可以用一個(gè)L型骨牌覆蓋

這3個(gè)較小棋盤(pán)的會(huì)合處，如圖4中央L型骨牌所示，這3個(gè)子棋盤(pán)上被L型骨牌覆蓋的方格就成為該棋盤(pán)上的特殊方格，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤(pán)簡(jiǎn)化為1x1棋盤(pán)。算法的MATLAB實(shí)現(xiàn)首先特殊方格在棋盤(pán)中的位置可以用一個(gè)1x2的數(shù)組sp表示；對(duì)于圖2所示的4種L型骨牌，可用數(shù)字1,2,3,4表示；對(duì)于特殊棋盤(pán)的骨牌覆蓋表示，只須注意到圖4所示的關(guān)鍵點(diǎn)，對(duì)每個(gè)關(guān)鍵點(diǎn)，給定一種L型骨牌，就能覆蓋整個(gè)棋盤(pán)，所以對(duì)于丁x2人的特殊棋盤(pán)的骨牌覆蓋，可用一個(gè)（2"-1）”2'-1）的矩陣表示。按照這種思想，圖4的矩陣表示為：仁4,特殊方格位置為：[1,4]覆蓋矩陣為:1仁4,特殊方格位置為：[1,4]覆蓋矩陣為:1040104044003000440030100020203000300030402030203下面是在MATLAB中的棋盤(pán)覆蓋實(shí)現(xiàn)程序。functionre=chesscover(k,sp)%解決棋盤(pán)的覆蓋問(wèn)題%棋盤(pán)為2、*2為，sp為特殊方格的棋盤(pán)位置globaIcovermatrixcovermatrix=zeros(2'k"1,2'k-1);evenl:floor(sp(1,1)/2)*2=sp(1,1);%判斷水平位置是否是偶數(shù)even2=floor(sp(1,2)/2)*2==sp(1,2);%判斷豎直位置是否是偶數(shù)ifeven1=1&&even2=0%找出找出特殊方格相對(duì)關(guān)鍵結(jié)點(diǎn)的位置i=4;eIsei=even1+even2+1;endtempfun(1f1rkr[sp(1,1)-evenl,sp(1,2)-even2,i]);re=covermatrix;functiontempfun(top,Ieft,k,tp)%子函數(shù),tp為轉(zhuǎn)換后特殊方格在棋盤(pán)網(wǎng)絡(luò)的相對(duì)位置globaIcovermatrixifk=1switchtp(1,3)covermatrix(tp(1,1)ftp(1r2))=3;covermatrix(tp(1f1)Ttp(1r2))=4;covermatrix(tp(1T1)Ttp(1r2))=1;covermatrix(tp(1T1)Ttp(1r2))=2;endeIsehaIf=2"(k-1);i=top+haIf-1;j=Ieft+haIf-1;iftp(UXiiftp(1,2)<j%特殊方格在左上covermatrix(i,j)=3;%添加類(lèi)型為3的L型骨牌tempfun(top,Ieft,k-1,tp);tempfun(top,Ieft+haIfrk-1,[iT,j+1,4]);tempfun(top+haIf,Ieft+haIf,k-1r[i+1,j+1,1]);tempfun(top+haIftleft,k-1,[i+1rj-1,2]);else%特殊方格在右上covermatrix(i,j)=4;%添加類(lèi)型為4的L型骨牌10tempfun(top,Ieft,k-1,[iT,jT,3]);tempfun(top,Ieft+haIf,k-1,tp);tempfun(top+haIftIeft+haIf,k-1r[i+1,j+1r1]);tempfun(top+haIftleft,k-1,[i+1rj-1,2]);endeIseif 特殊方格在右下covermatrix(i,j)=1;%添加類(lèi)型為3的L型骨牌tempfun(top,Ieft,k-1,[i-1,j-1,3]);tempfun(top,Ieft+haIfrk-1,[iT,j+1,4]);tempfun(top+haIf,Ieft+haIf,k-1,tp);tempfun(top+haIftleft,k-1,[i+1rj-1,2]);eIse%特殊方格在左下covermatrix(i,j)=2;%添加類(lèi)型為4的L型骨牌tempfun(top,Ieft,k-1,[i-1,j-1,3]);tempfun(top,Ieft+haIf,k-1,[iT,j+1,4]);11tempfun(top+haIf,left+haIf,k-1r[i+1,j+1,1]);tempfun(top+haIf,Ieft,k-1,tp);endendend在MATLAB命令窗口中輸入指令chesscover(3,[1,4])將會(huì)得到如上面矩陣一樣的結(jié)果。結(jié)合VC++,利用MATLAB引擎庫(kù)函數(shù)，可以給出了棋盤(pán)覆蓋的圖形最優(yōu)樹(shù)的應(yīng)用實(shí)例問(wèn)題的提出已知某通信系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別為，，，，，，,試設(shè)計(jì)一種編碼，使得信息包長(zhǎng)度達(dá)到最小。問(wèn)題的分析12ASCII碼是用8位（一個(gè)字節(jié)）表示一個(gè)字符，這種表示方法方便，易于理解,是計(jì)算機(jī)系統(tǒng)中常用的字符表示方法。在信息傳輸領(lǐng)域，可能有些字符出現(xiàn)的頻率非常高，而有些字符出現(xiàn)的頻率很低，若依然用此方法表示數(shù)據(jù)，則顯得過(guò)于龐大，如果用不定長(zhǎng)編碼表示字符，頻率出現(xiàn)高的字符用較短的編碼表示，頻率出現(xiàn)低的字符用較長(zhǎng)的編碼表示，則可以使得數(shù)據(jù)量大大減少。比如AAAABBBAAABBBBCCCCCCBBB,用ASCII碼表示占用184位,若用00表示C,01表示A,1表示B,則該字串占用位數(shù)為36,壓縮率達(dá)到%,這種編碼稱(chēng)為哈夫曼編碼。當(dāng)然也可用其它方式壓縮數(shù)據(jù)，例如上面字符串寫(xiě)成4A3B3A4B6c3B,而達(dá)到壓縮數(shù)據(jù)的目的。哈夫曼樹(shù)的構(gòu)造要構(gòu)造哈夫曼編碼，需要構(gòu)造哈夫曼樹(shù)（即最優(yōu)樹(shù)）。哈夫曼最早給出了一個(gè)帶有一般規(guī)律的算法，俗稱(chēng)哈夫曼算法?，F(xiàn)敘述如下：①根據(jù)給定的〃個(gè)概率（或頻率）構(gòu)造一個(gè)集合/川"人同時(shí)這〃個(gè)值對(duì)應(yīng)樹(shù)T的"個(gè)結(jié)點(diǎn)，置，=〃+1。②在集合廠中選擇兩個(gè)最小的值求和作為力加入集合廠中；在樹(shù)T中構(gòu)造一結(jié)點(diǎn)，使得該結(jié)點(diǎn)是兩最小值對(duì)應(yīng)結(jié)點(diǎn)的父結(jié)點(diǎn)。③在集合片中刪除兩最小值，并置i=i+④重復(fù)②和③，直到或集合廠只有一個(gè)元素為止。這樣形成的一棵樹(shù)就是哈夫曼樹(shù)（最優(yōu)樹(shù)）。上面所提到的字符串和題目給出的概率所形成的哈夫曼樹(shù)分別如圖1和圖2（為方便起見(jiàn)，每個(gè)概率值乘上了100）。13

A用MATLAB實(shí)現(xiàn)哈夫曼算法在A用MATLAB實(shí)現(xiàn)哈夫曼算法在MATLAB中實(shí)現(xiàn)哈夫曼算法,可用一個(gè)5xQ〃-1）的矩陣來(lái)表示哈夫曼樹(shù),該矩陣的含義如表6-3-3所示。表1哈夫曼算法數(shù)據(jù)結(jié)構(gòu)字符123452個(gè)1序號(hào)概率14父結(jié)點(diǎn)序號(hào)左右子樹(shù)標(biāo)志0表示左子樹(shù)1表示右子樹(shù)是否在集合尸1在集合尸0不在集合尸下面給出哈夫曼樹(shù)的生成算法：functionhtree=HuffmanTree(pro)舟構(gòu)造哈夫曼樹(shù)%pro為一概率向量n=size(pro,2);先得到字符個(gè)數(shù)tree=ones(6,2*n-1);%構(gòu)造樹(shù)數(shù)據(jù)結(jié)構(gòu)treed,:)=1:(2*n-1);%填充結(jié)點(diǎn)序號(hào)tree(5,(n+1):end)=0;%設(shè)置結(jié)點(diǎn)是否在集合tree(2,1:n)=pro;%設(shè)置概率tree(6,1:end)=0;%記錄查找的結(jié)點(diǎn)對(duì)順序fori=(n+1):(2*n-1);%循環(huán)控制[I,r]=findminval(tree);%找到集合中兩個(gè)最小的值的序號(hào)tree(2,i)=tree(2,l)+tree(2,r);%得到父結(jié)點(diǎn)概率值tree⑸i)=1;%設(shè)置新構(gòu)造結(jié)點(diǎn)在集合中15tree(3,I)=i;tree⑶r)=i;%設(shè)置父結(jié)點(diǎn)序號(hào)tree(4,I)=0;tree(4,r)=1;%設(shè)置左右標(biāo)志tree(5,I)=0;tree⑸r)=0;%設(shè)置不在集合中tree(6,l)=i-n;tree(6,r)=i-n;%記錄該次刪除的結(jié)點(diǎn)對(duì)順序endhtree=tree;function[Irr]=findminvaI(tree)s=find(tree⑸：)二二1);ifsize(s,2)<2error('Errorinput!1);endfirval=reaImax;secval=reaImax;fori=s;iffirval>tree(2,i)ifsecvaI>firvaIsecond=first;s