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

1、圖論實(shí)驗(yàn)三個(gè)案例單源最短路徑問(wèn)題1.1 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è)v是圖中的一個(gè)頂點(diǎn)，記為頂點(diǎn)v到源點(diǎn)v1的最短距離，若，記到的權(quán)。Dijkstra算法： ,；,； ，停止，否則轉(zhuǎn)； ，； 存在，使，； ，轉(zhuǎn)；實(shí)際上，Dijkstra算法也是最優(yōu)化原理的應(yīng)用：如果是從到的最短路徑，則也必然是從到的最優(yōu)路徑。在下面的MATLAB實(shí)現(xiàn)代碼中，我們用到了距離矩陣，矩陣第i行第j行元素表示頂點(diǎn)到的權(quán)，若到無(wú)邊，則，其中realm

2、ax是MATLAB常量，表示最大的實(shí)數(shù)(1.7977e+308)。function re=Dijkstra(ma)%用Dijkstra算法求單源最短路徑%輸入?yún)⒘縨a是距離矩陣%輸出參量是一個(gè)三行n列矩陣，每列表示頂點(diǎn)號(hào)及頂點(diǎn)到源的最短距離和前頂點(diǎn)n=size(ma,1);%得到距離矩陣的維數(shù)s=ones(1,n);s(1)=0;%標(biāo)記集合S和S的補(bǔ)r=zeros(3,n);r(1,:)=1:n;r(2,2:end)=realmax;%初始化for i=2:n;%控制循環(huán)次數(shù)    mm=realmax;    for j=find(

3、s=0);%集合S中的頂點(diǎn)        for k=find(s=1);%集合S補(bǔ)中的頂點(diǎn)            if(r(2,j)+ma(j,k)<r(2,k)                r(2,k)=r(2,j)+ma(j,k);r(3,k)=j;

4、60;           end            if(mm>r(2,k)                mm=r(2,k);t=k;       

5、0;    end        end    end    s(1,t)=0;%找到最小的頂點(diǎn)加入集合Sendre=r;1.2 動(dòng)態(tài)規(guī)劃求解最短路徑動(dòng)態(tài)規(guī)劃是美國(guó)數(shù)學(xué)家Richard Bellman在1951年提出來(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)題，需要依次作出n個(gè)決策，如若這個(gè)決策是最優(yōu)的，對(duì)于任何一個(gè)整

6、數(shù)k，1<k<n，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即也是最優(yōu)的。如圖1，從A1點(diǎn)要鋪設(shè)一條管道到A16點(diǎn)，中間必須要經(jīng)過(guò)5個(gè)中間站，第一站可以在 A2，A3中任選一個(gè)，第二、三、四、五站可供選擇的地點(diǎn)分別是： A4，A5，A6，A7， A8，A9，A10， A11，A12，A13， A14，A15。連接兩地管道的距離用連線上的數(shù)字表示，要求選一條從A1到A16的鋪管線路，使總距離最短。 1A2A1A3A4A5A6A7A8A9A10A13A12A11A14A15A1653136876683533842223335526643圖1

7、可選擇的管道圖 解決此問(wèn)題可以用窮舉法，從A1到A16有48條路徑，只須比較47次，就可得到最短路徑為：A1A2A5A8A12A15A16，最短距離為18。也可以使用Dijkstra算法。這里，我們動(dòng)態(tài)規(guī)劃解決此問(wèn)題。注意到最短路徑有這樣一個(gè)特性，即如果最短路徑的第k站通過(guò)Pk，則這一最短路徑在由Pk出發(fā)到達(dá)終點(diǎn)的那一部分路徑，對(duì)于始點(diǎn)為Pk到終點(diǎn)的所有可能的路徑來(lái)說(shuō)，必定也是距離最短的。根據(jù)最短路徑這一特性，啟發(fā)我們計(jì)算時(shí)從最后一段開(kāi)始，從后向前逐步遞推的方法，求出各點(diǎn)到A16的最短路徑。在算法中，我們用數(shù)組六元數(shù)組ss表示中間車站的個(gè)數(shù)(A1也作為中間車站)，用距離矩陣path表示該圖。為

8、簡(jiǎn)便起見(jiàn)，把該圖看作有向圖，各邊的方向均為從左到右，則path不是對(duì)稱矩陣，如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是車站個(gè)數(shù)n=size(path,1);%結(jié)點(diǎn)個(gè)數(shù)scheme=zeros(3,n);%構(gòu)造結(jié)果矩陣scheme(1,:)=1:n;%

9、設(shè)置結(jié)點(diǎn)序號(hào)scheme(2,1:n-1)=realmax;%預(yù)設(shè)距離值k=n-1;%記錄第一階段結(jié)點(diǎn)最大序號(hào)for i=size(ss,2):-1:1;%控制循環(huán)階段數(shù)    for j=k:-1:(k-ss(i)+1);%當(dāng)前階段結(jié)點(diǎn)循環(huán)        for t=find(path(j,:)>0);%當(dāng)前結(jié)點(diǎn)鄰接結(jié)點(diǎn)            if path(j,t)+schem

10、e(2,t)<scheme(2,j)                scheme(2,j)=path(j,t)+scheme(2,t);                scheme(3,j)=t;        &

11、#160;   end        end    end    k=k-ss(i);移入下一階段end先在MATLAB命令窗口中構(gòu)造距離矩陣path，再輸入：>> ShortestPath(path,ss)得到以下結(jié)果：1234567891011121314151618131613109127687594302568891012121214151516160將該結(jié)果表示為圖，即為圖1粗線所示。棋盤覆蓋問(wèn)題1.1 問(wèn)題的提出圖1 當(dāng)k

12、=3時(shí)的特殊棋盤在一個(gè)個(gè)方格組成的棋盤中，若恰有一個(gè)方格與其他方格不同，則稱該方格為一特殊方格，且稱該棋盤為一特殊的棋盤。如圖1就是當(dāng)時(shí)的特殊棋盤。棋盤覆蓋問(wèn)題中，我們要用圖2所示4種不同形態(tài)的L形骨牌覆蓋一個(gè)特殊棋盤，且任何2個(gè)L型不得重疊覆蓋。圖2 4種不同形態(tài)的L型骨牌(a)(b)(c)(d)  1.2 問(wèn)題的分析易知，用到的L型骨牌個(gè)數(shù)恰為。利用分治策略，我們可以設(shè)計(jì)出解棋盤覆蓋問(wèn)題的一個(gè)簡(jiǎn)捷的算法。當(dāng)k>0時(shí)，我們將棋盤分割為4個(gè)子棋盤如圖3兩粗實(shí)線所示。圖4 關(guān)鍵結(jié)點(diǎn)123圖3 棋盤分割      

13、0; 特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無(wú)特殊方格。為了將這3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，我們可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如圖4中央L型骨牌所示，這3個(gè)子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的特殊方格，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤。1.3 算法的MATLAB實(shí)現(xiàn)首先特殊方格在棋盤中的位置可以用一個(gè)的數(shù)組sp表示；對(duì)于圖2所示的4種L型骨牌，可用數(shù)字1,2,3,4表示；對(duì)于特殊棋盤的骨牌覆蓋表示，只須注意到圖4所示的關(guān)鍵點(diǎn)，對(duì)每個(gè)關(guān)鍵點(diǎn)，給定一種L型骨牌，就能覆蓋整個(gè)棋盤，所以對(duì)于的

14、特殊棋盤的骨牌覆蓋，可用一個(gè)的矩陣表示。按照這種思想，圖4的矩陣表示為：k=4，特殊方格位置為：1,4，覆蓋矩陣為：下面是在MATLAB中的棋盤覆蓋實(shí)現(xiàn)程序。function re = chesscover(k,sp)%解決棋盤的覆蓋問(wèn)題%棋盤為2k*2k，sp為特殊方格的棋盤位置global covermatrixcovermatrix=zeros(2k-1,2k-1);even1=floor(sp(1,1)/2)*2=sp(1,1);%判斷水平位置是否是偶數(shù)even2=floor(sp(1,2)/2)*2=sp(1,2);%判斷豎直位置是否是偶數(shù)if even1=1&&ev

15、en2=0%找出找出特殊方格相對(duì)關(guān)鍵結(jié)點(diǎn)的位置    i=4;else    i=even1+even2+1;endtempfun(1,1,k,sp(1,1)-even1,sp(1,2)-even2,i);re=covermatrix; function tempfun(top,left,k,tp)%子函數(shù),tp為轉(zhuǎn)換后特殊方格在棋盤網(wǎng)絡(luò)的相對(duì)位置global covermatrixif k=1    switch tp(1,3)     

16、60;  case 1            covermatrix(tp(1,1),tp(1,2)=3;        case 2            covermatrix(tp(1,1),tp(1,2)=4;       

17、; case 3            covermatrix(tp(1,1),tp(1,2)=1;        case 4            covermatrix(tp(1,1),tp(1,2)=2;    endelse    half

18、=2(k-1);i=top+half-1;j=left+half-1;    if tp(1,1)<i        if tp(1,2)<j%特殊方格在左上            covermatrix(i,j)=3; %添加類型為3的L型骨牌           

19、 tempfun(top,left,k-1,tp);            tempfun(top,left+half,k-1,i-1,j+1,4);            tempfun(top+half,left+half,k-1,i+1,j+1,1);          &

20、#160; tempfun(top+half,left,k-1,i+1,j-1,2);        else %特殊方格在右上            covermatrix(i,j)=4;%添加類型為4的L型骨牌            tempfun(top,left,k-1,i-1,j-1,3);

21、0;           tempfun(top,left+half,k-1,tp);            tempfun(top+half,left+half,k-1,i+1,j+1,1);            tempfun(top+half,left,k-1,i+1,j

22、-1,2);        end    else        if tp(1,2)>j%特殊方格在右下            covermatrix(i,j)=1;%添加類型為3的L型骨牌          &

23、#160; tempfun(top,left,k-1,i-1,j-1,3);            tempfun(top,left+half,k-1,i-1,j+1,4);            tempfun(top+half,left+half,k-1,tp);         &#

24、160;  tempfun(top+half,left,k-1,i+1,j-1,2);        else %特殊方格在左下            covermatrix(i,j)=2;%添加類型為4的L型骨牌            tempfun(top,left,k-1,i-1,j-1,3)

25、;            tempfun(top,left+half,k-1,i-1,j+1,4);            tempfun(top+half,left+half,k-1,i+1,j+1,1);            tempfun(top+half,le

26、ft,k-1,tp);        end    endend在MATLAB命令窗口中輸入指令    chesscover(3,1,4)將會(huì)得到如上面矩陣一樣的結(jié)果。   結(jié)合VC+，利用MATLAB引擎庫(kù)函數(shù)，可以給出了棋盤覆蓋的圖形最優(yōu)樹(shù)的應(yīng)用實(shí)例1.1 問(wèn)題的提出已知某通信系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)一種編碼，使得信息包長(zhǎng)度達(dá)到最小。

27、1.2 問(wèn)題的分析ASCII碼是用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á)到19.6%，這種編碼稱為哈夫曼編碼。當(dāng)然也可用其它方式壓縮數(shù)據(jù)，例如上面字符串寫成4A

28、3B3A4B6C3B，而達(dá)到壓縮數(shù)據(jù)的目的。1.3 哈夫曼樹(shù)的構(gòu)造要構(gòu)造哈夫曼編碼，需要構(gòu)造哈夫曼樹(shù)（即最優(yōu)樹(shù)）。哈夫曼最早給出了一個(gè)帶有一般規(guī)律的算法，俗稱哈夫曼算法?，F(xiàn)敘述如下： 根據(jù)給定的n個(gè)概率（或頻率）構(gòu)造一個(gè)集合，同時(shí)這n個(gè)值對(duì)應(yīng)樹(shù)T的n個(gè)結(jié)點(diǎn)，置。 在集合F中選擇兩個(gè)最小的值求和作為加入集合F中；在樹(shù)T中構(gòu)造一結(jié)點(diǎn)，使得該結(jié)點(diǎn)是兩最小值對(duì)應(yīng)結(jié)點(diǎn)的父結(jié)點(diǎn)。 在集合F中刪除兩最小值，并置。 重復(fù)和，直到或集合F只有一個(gè)元素為止。這樣形成的一棵樹(shù)就是哈夫曼樹(shù)（最優(yōu)樹(shù)）。上面所提到的字符串和題目給出的概率所形成的哈夫曼樹(shù)分別如圖1和圖2(為方便起見(jiàn)，每個(gè)概率值乘上了100)。538111

29、92342781514292958100圖20000000111111167131023CAB圖10011          1.4 用MATLAB實(shí)現(xiàn)哈夫曼算法在MATLAB中實(shí)現(xiàn)哈夫曼算法，可用一個(gè)的矩陣來(lái)表示哈夫曼樹(shù)，該矩陣的含義如表6-3-3所示。表1 哈夫曼算法數(shù)據(jù)結(jié)構(gòu)字符序號(hào)123452n-1概率       父結(jié)點(diǎn)序號(hào)      左右子樹(shù)標(biāo)志0表示左子樹(shù)1表示右子

30、樹(shù)     是否在集合F1在集合F0不在集合F     下面給出哈夫曼樹(shù)的生成算法：function htree = 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)tree(1,:)=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ì)順序for i

31、=(n+1):(2*n-1);%循環(huán)控制    l,r=findminval(tree);%找到集合中兩個(gè)最小的值的序號(hào)    tree(2,i)=tree(2,l)+tree(2,r);%得到父結(jié)點(diǎn)概率值    tree(5,i)=1;%設(shè)置新構(gòu)造結(jié)點(diǎn)在集合中    tree(3,l)=i;tree(3,r)=i;%設(shè)置父結(jié)點(diǎn)序號(hào)    tree(4,l)=0;tree(4,r)=1;%設(shè)置左右標(biāo)志    tree(5,l)=0;tree(5,r)=0;%設(shè)置不在集合中    tree(6,l)=i-n;tree(6,r)=i-n;%記錄該次刪除的結(jié)點(diǎn)對(duì)順序endhtree=tree; function l,r=findminval(tree)s=find(tree(5,:)=1);if size(s,2)<2    error('Error input!');endfirval=realmax;secval=realmax;for i=s;