图论算法及matlab程序的三个标准规定样式分析

1、图论实验三个案例单源最短路径问题1.1 Dijkstra 算法Dijkstra算法是解单源最短路径问题的一个贪心算法.其根本思想是,设置一个顶点集合S并不断地作贪心选择来扩充这个集合.一个顶点属于集合 S当 且仅当从源到该顶点的最短路径长度.设 v是图中的一个顶点,记l(v)为顶 点v到源点vi的最短距离,Vi,Vj V,假设(Vi,Vj) E,记,到"的权Wij oDijkstra 算法： S M,l(vi) 0. v V vi ,l(v) ,i 1,S V vi；S,停止,否那么转； l(v) min l(v),d(vj,v)vj S v S .存在 vi 使 l(vii)min

2、l(v) , v S. S SUvi o, S S vii, i i i,转；实际上,Dijkstra算法也是最优化原理的应用：如果viv2Wvnivn是从M到vn的 最短路径,那么v1V2 口vn1也必然是从vi到vn1的最优路径.在下面的MATLAB实现代码中,我们用到了距离矩阵,矩阵第i行第j行元 素表示顶点Vi到Vj的权Wj,假设Vi到Vj无边,那么Wij realmax ,其中realmax是MATLAB常量,表示最大的实数(1.7977e+308).function re=Dijkstra(ma)%用Dijkstra算法求单源最短路径%输入参量ma是距离矩阵%输出参量是一个三行n列

3、矩阵,每列表示顶点号及顶点到源的最短距离和 前顶点n=size(ma,1);% 得到距离矩阵的维数s=ones(1,n);s(1)=0;% 标记集合 S 和 S 的补r=zeros(3,n);r(1,:)=1:n;r(2,2:end)=realmax;% 初始化for i=2:n;%限制循环次数mm=realmax;for j=find(s=0);% 集合S中的顶点for k=find(s=1);% 集合S补中的顶点if(r(2,j)+ma(j,k)<r(2,k)r(2,k)=r(2,j)+ma(j,k);r(3,k)=j;end if(mm>r(2,k)mm=r(2,k);t=k

4、;endendends(1,t)=0;%找到最小的顶点参加集合Sendre=r;1.2 动态规划求解最短路径动态规划是美国数学家Richard Bellman在1951年提出来的分析一类多阶 段决策过程的最优化方法,在工程技术、工业生产、经济治理、军事及现代化控 制工程等方面均有着广泛的应用.动态规划应用了最正确原理：假设为了解决某一 优化问题,需要依次作出n个决策Di,D2J?Dn,如假设这个决策是最优的,对于 任何一个整数k, 1<k<n,不管前面k个决策是怎样的,以后的最优决策只取决 于由前面决策所确定的当前状态,即 Dk1,Dk2Dn也是最优的.如图1 ,从Ai点要铺设一条

5、管道到A16点,中间必须要经过5个中间站, 第一站可以在 A2, A3中任选一个,第二、三、四、五站可供选择的地点分别是： A4, A5, A6, A7, A8, A9, A10, A11, A12 , A13, A14 , A15.连接两地管道的距离用连线上的数字表示,要求选一条从Ai到A16的铺管线路,使总距离最短.解决此问题可以用穷举法,从 Ai到Ai6有48条路径,只须比拟47次,就 可得到最短路径为：Ai-A2-A5-A8-A12-A15-Ai6 ,最短距离为18.也可以使用Dijkstra算法.这里,我们动态规划解决此问题.注意到最短路 径有这样一个特性,即如果最短路径的第 k站通

6、过Pk,那么这一最短路径在由Pk 出发到达终点的那一局部路径,对于始点为Pk到终点的所有可能的路径来说,必定也是距离最短的.根据最短路径这一特性,启发我们计算时从最后一段开始, 从后向前逐步递推的方法,求出各点到 A16的最短路径.在算法中,我们用数组六元数组 ss表示中间车站的个数(Ai也作为中间车 站),用距离矩阵path表示该图.为简便起见,把该图看作有向图,各边的方向 均为从左到右,那么path不是对称矩阵,如path(12,14)=5 ,而path(14,12)=0(用0表示不通道路).用316矩P$ spath表示算法结果,第一行表示结点序号,第 二行表示该结点到终点的最短距离,第

7、三行表示该结点到终点的最短路径上的下 一结点序号.下面给出MATLAB实现算法.function scheme = ShortestPath(path,ss)%利用动态规划求最短路径%path是距离矩阵,ss是车站个数n=size(path,1);% 结点个数scheme=zeros(3,n);% 构造结果矩阵scheme(1,:)=1:n;% 设置结点序号scheme(2,1:n-1)=realmax;% 预设距离值k=n-1;%记录第一阶段结点最大序号for i=size(ss,2):-1:1;% 限制循环阶段数for j=k:-1:(k-ss(i)+1);% 当前阶段结点循环for t=

8、find(path(j,:)>0);% 当前结点邻接结点if path(j,t)+scheme(2,t)<scheme(2,j)scheme(2,j)=path(j,t)+scheme(2,t);scheme(3,j)=t;endendendk=k-ss(i);移入下一阶段end先在MATLAB命令窗口中构造距离矩阵path ,再输入:>> ShortestPath(path,ss)得到以下结果：123418 13 16 1325685678109127891012910 1112687512 12 14 1513 14 15 16943015 16 16 0将该结果表

9、示为图,即为图1粗线所示棋盘覆盖问题1.1问题的提出在一个2k 2k个方格组成的棋盘中,假设恰有一个方格与其他方格不同,那么称图2 4种不同形态的L型骨牌1.2问题的分析k易知,用到的L型骨牌个数恰为(4 1)/3o利用分治策略,我们可以设计出解棋盘覆盖问题的一个简捷的算法._k _k _ _k 1 _k 1 当k>0时,我们将2 2棋盘分割为4个22子棋盘如图3两粗实线所示.特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格.为 了将这3个无特殊方格的子棋盘转化为特殊棋盘,我们可以用一个L型骨牌覆盖 这3个较小棋盘的会合处,如图4中央L型骨牌所示,这3个子棋盘上被L型骨牌覆

10、盖的方格就成为该棋盘上的特殊方格,从而将原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为1 1棋盘.1.3 算法的MATLAB实现首先特殊方格在棋盘中的位置可以用一个1 2的数组sp表示；对于图2所示的4种L型骨牌,可用数字1,2,3,4表示；对于特殊棋盘的骨牌覆盖表示,只 须注意到图4所示的关键点,对每个关键点,给定一种L型骨牌,就能覆盖整个一 k ,、 一 k ,、棋盘,所以对于2 2的特殊棋盘的骨牌覆盖,可用一个2 12 1的矩阵表示.根据这种思想,图4的矩阵表示为：104010204000204030203000300010403020400030k=4 ,特

11、殊方格位置为：1,4,覆盖矩阵为:4030403卜面是在MATLAB中的棋盘覆盖实现程序function re = chesscoverk,sp%解决棋盘的覆盖问题%棋盘为2Ak*2Ak , sp为特殊方格的棋盘位置global covermatrixcovermatrix=zeros(2Ak-1,2Ak-1);even1=floor(sp(1,1)*2=sp(1,1);%判断水平位置是否是偶数even2=floor(sp(1,2)/2)*2=sp(1,2);%判断竖直位置是否是偶数if even1=1&&even2=0%找出找出特殊方格相对关键结点的位置i=4;elsei=e

12、ven1+even2+1;endtempfun(1,1,k,sp(1,1)-even1,sp(1,2)-even2,i);re=covermatrix;function tempfun(top,left,k,tp)% 子函数,tp为转换后特殊方格在棋盘网络的相对位置global covermatrixif k=1switch tp(1,3)case 1covermatrix(tp(1,1),tp(1,2)=3;case 2covermatrix(tp(1,1),tp(1,2)=4;case 3covermatrix(tp(1,1),tp(1,2)=1;case 4covermatrix(tp(

13、1,1),tp(1,2)=2;endelsehalf=2A(k-1);i=top+half-1;j=left+half-1;if tp(1,1)<iif tp(1,2)<j%特殊方格在左上covermatrix(i,j)=3; %添加类型为3的L型骨牌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);tempfun(top+half,left,k-1,i+1,j-1,2);else %特殊方格在右上covermatrix(i,

14、j)=4;% 添加类型为4的L型骨牌tempfun(top,left,k-1,i-1,j-1,3);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-1,2);endelseif tp(1,2)>j%特殊方格在右下covermatrix(i,j)=1;% 添加类型为3的L型骨牌tempfun(top,left,k-1,i-1,j-1,3);tempfun(top,left+half,k-1,i-1,j+1,4);tempfun(to

15、p+half,left+half,k-1,tp);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);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,left,k-1,tp);endendend在MATLAB命令窗口中输入指令chesscover(3,1,4)将会得到如上面矩阵一

16、样的结果.结合VC+ ,利用MATLAB引擎库函数,可以给出了棋盘覆盖的图形最优树的应用实例1.1 问题的提出某通信系统在通信联络中只可能出现 8种字符,其概率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11 ,试设计一种编码,使得信息包长 度到达最小.1.2 问题的分析ASCII码是用8位一个字节表示一个字符,这种表示方法方便,易于理解, 是计算机系统中常用的字符表示方法. 在信息传输领域,可能有些字符出现的频 率非常高,而有些字符出现的频率很低,假设依然用此方法表示数据,那么显得过于 庞大,如果用不定长编码表示字符,频率出现高的字符用较短的

17、编码表示, 频率 出现低的字符用较长的编码表示,那么可以使得数据量大大减少.比方 AAAABBBAAABBBBCCCCCCBBB ,用 ASCII 码表示占用 184 位,假设用 00 表 示C, 01表示A, 1表示B,那么该字用占用位数为36 ,压缩率到达19.6% ,这 种编码称为哈夫曼编码.当然也可用其它方式压缩数据,例如上面字符串写成 4A3B3A4B6C3B ,而到达压缩数据的目的.1.3 哈夫曼树的构造要构造哈夫曼编码,需要构造哈夫曼树即最优树.哈夫曼最早给出了一 个带有一般规律的算法,俗称哈夫曼算法.现表达如下： 根据给定的n个概率或频率构造一个集合F fl,f2,lll, f

18、n,同时这 n个值对应树T的n个结点,置i n 1.在集合F中选择两个最小的值求和作为 力参加集合F中；在树T中构造 一结点,使得该结点是两最小值对应结点的父结点. 在集合F中删除两最小值,并置i i 1.重复和,直到i 2n 1或集合F只有一个元素为止.这样形成的一 棵树就是哈夫曼树最优树.上面所提到的字符串和题目给出的概率所形成的哈夫曼树分别如图1和图2为方便起见,每个概率值乘上了 100.图1图21.4用MATLAB实现哈夫曼算法在MATLAB中实现哈夫曼算法,可用一个5 (2n 1)的矩阵来表示哈夫曼树, 该矩阵的含义如表6-3-3所示.表1哈夫曼算法数据结构字符序号123452n-1

19、概率父结点厅P左右子树标志0表示左子树1 表示右子树是否在集合F1在集合F0不在集合F卜面给出哈夫曼树的生成算法:function htree = HuffmanTree(pro)%构造哈夫曼树%pro为一概率向量n=size(pro,2);%得到字符个数tree=ones(6,2*n-1);%构造树数据结构tree(1,:)=1:(2*n-1);%填充结点序号tree(5,(n+1):end)=0;%设置结点是否在集合tree(2,1:n)=pro;% 设置概率tree(6,1:end)=0;% 记录查找的结点对顺序for i=(n+1):(2*n-1);%循环限制l,r=findminva

20、l(tree);% 找到集合中两个最小的值的序号tree(2,i)=tree(2,l)+tree(2,r);% 得到父结点概率值tree(5,i)=1;%设置新构造结点在集合中tree(3,l)=i;tree(3,r)=i;%设置父结点序号tree(4,l)=0;tree(4,r)=1;%设置左右标志tree(5,l)=0;tree(5,r)=0;%设置不在集合中tree(6,l)=i-n;tree(6,r)=i-n;%记录该次删除的结点对顺序endhtree=tree;function l,r=findminval(tree)s=find(tree(5,:)=1);if size(s,2)<2error('Error input!');endfirval=realmax;secval=realmax;for i=s;if firval>tree(2,i)if secval>firvalsecond=first;secval=firval;endfirst=i;firval=tr