(完整word版)图论算法及matlab程序的三个案例.docx

1、图论实验三个案例单源最短路径问题1.1 Dijks tra 算法Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一 个顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。设 v是图中的一个顶点，记】)为顶点v到源点VI的最短距离,v,v V (v , v ) E v v wi ,若 J ，记，到j的权勺Dijks tra算法:S v l(v ) 0 v 一1 ； ，停止，否则转； l(v) minl(v), d (Vj, v) , Vj存在1，使此)minl(v) S SUv|> -S S 1,V vj 1 (v

2、) J s V (vV s ；i i b转;Vi V。L v t v v v实际上，Dykstra算法也是最优化原理的应用：如果1 2" “是从到n的最短路径，则V2L Vn I也必然是从匕到Vn1的最优路径。实现代码中，我们用到了距离矩阵，矩阵第 i行第j行元 在下面的MATLAB素.表示顶点V到七的权"，若V到Vj无边，则"realmax,其中reaimax是MATLAB常量，表示最大的实数(1.7977e+308)。function re=Dijkstra(ma)%用Dykstra算法求单源最短路径%输入参量ma是距禺矩阵%输出参量是一个三行n列矩阵，每列表

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

4、ends(l,t)=O;% 找到最小的顶点加入集合Send re=r;1.2 动态规划求解最短路径动态规划是美国数学家Richard Bellman在1951年提出来的分析一类多阶段 决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控制工 程等方面均有着广泛的应用。动态规划应用了最佳原理：假设为了解决某一 优化问题，需要依次作出 n个决策Di，D2，L'D"，如若这个决策是最优的，对于 任何一个整数k, l<k<n,不论前面k个决策是怎样的，以后的最优决策只取决 于由前面决策所确定的当前状态，即 Dk 1，D卜2，L D也是最优的。如图1,从Ai

5、点要铺设一条管道到 A6点，中间必须要经过5个中间站，第一站可以在A2, A中任选一个，第二、三、四、五站可供选择的地点分别是：A4, As, A6, Av , As, Av, Ao, All, A12, A13), A14, A15 o 连接两地管道 的距离用连线上的数字表示，要求选一条从A.到A.6的铺管线路，使总距离最短。图1可选择的管道图解决此问题可以用穷举法，从 A.到Ak有48条路径，只须比较47次，就可 得到最短路径为：A|f A2fA5fAs f A12fAi5fAi6,最短距曷为18。也可以使用Dijkstra 算法。这里，我们动态规划解决此问题。注意到最短k站通过“则这一最

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

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

8、结点循环for t=find(path(j,:)>0);%当前结点邻接结点if path(j,t)4-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)得到以下结果：1234567891011121314151618131613109127687594302568891012121214151516160将该结果表示为图，

9、即为图1粗线所示。棋盘覆盖问题1.1问题的提出在一个2k2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称k该7格为二好歹格,且称巧棋盘为一特殊的棋盘。如图 1就是当 3时的特 殊根盘|。问电中|,胧们要用图2所示4种不同形态的L形骨牌覆盖一个第糜 刈乱印7车/不得重叠覆盖。1 Az图1当k=3时的特殊棋盘总金"vy 产(a)图21.2问题的分析易知，用到的L型骨牌个数恰为qk D/3出解棋盘覆盖问题的一个简捷的算法。(b)(c)(d)4种不同形态的L型骨牌O利用分治策略，我们可以设计当k>0时，我们将2k 2k棋盘分割为4个2kl 2kl子棋盘如图3两粗实线所zj O

10、图3棋盘分割123图4关键结点特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了 将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图4中央L型骨牌所示，这3个子棋盘上被L型骨 牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋 盘覆盖问题。递归地使用这种分割，直至棋盘简化为1 1棋盘。1.3 算法的MATLAB实现首先特殊方格在棋盘中的位置可以用一个1 2的数组sp表示；对于图2所示的 4种L型骨牌，可用数字1,2,3,4表示；对于特殊棋盘的骨牌覆盖表示，只须注意到图4所示的关键点，对每个关键点，给定一种L型

11、骨牌，就能覆盖整个棋盘，所以对于2k 2k的特殊棋盘的骨牌覆盖，可用一个(2k 1)(2k1)的矩阵表示。按照这种思想，图4的矩阵表示为:k ,特殊方格位置为：，覆盖矩阵为:=41,4104010400040302000301040304000403040 22 00 30 00 23 00 3下面是在MATLAB中的棋盘覆盖实现程序。function re = chesscover(k,sp)%解决棋盘的覆盖问题%棋盘为2Ak*2Ak ， sp为特殊方格的棋盘位置global covermatrixcoverma trix=ze ro s (2 Ak-1,2 Ak-1);evenl=floo

12、r(sp(l ,l)/2)*2=sp(l,l);%判断水平位置是否是偶数even2=floor(sp(l,2)/2)M2=sp(l,2);%判断竖直位置是否是偶数if evenl=l &&e ve n2=0%找出找出特殊方格相对关键结点的位置i=4;elsei=evenl+even2+l;end tempfun(l,l ,k,sp(l/)-evenl ,sp(l,2)-even2,i);re=cove rmatrix;function tempfon(top,left,k,tp)% 子函数,tp为转换后特殊方格在棋盘网 络的相对位置global covermatrixifk=l

13、switch tp(l,3)case 1cove rmatrix(tp(l ,l),tp(l,2)=3;case 2cove rmatrix(tp(l ,l),tp(l,2)=4;case 3co ve rma trix(tp(l ,l),tp(l ,2)=1;case 4cove rma trix(tp( 1,1 ),tp(l ,2)=2;endelsehalf=2A(k-l);i=top+half-l ;j=left+half-l;iftp(l,l)<iif tp(l ,2)<j% 特殊方格在左上covermatrix(i,j)=3; %添加类型为3的L型骨牌tempfun(t

14、op,left,k-l,tp);tempfun(top,left+half,k-l ,i-l ,j+l ,4);tempfun(top+half,left4-half,k-l ,i+l ,j+l ,1 )；tempfun(top+half,left,k-l,i+l ,j-l ,2);else %特殊方格在右上c o ve rm a trix(i,j)=4; %添加类型为4的L型骨牌tempfun(top,left,k-l ,i-l ,j-l ,3)；tempfun(top,left+half,k-l,tp);tempfun(top+half,left4-half,k-l ,i+l ,j+l ,

15、1 )；tempfun(top+half,left,k-l ,i+l ,j-l ,2);endelseiftp(l,2)>j% 特殊方格在右下covermatrix(i,j)=l;% 添加类型为3的L型骨牌tempfun(top,left,k-l ,i-l ,j-l ,3)；tempfun(top,left+half,k-l ,i-l ,j+l ,4);tempfun(top+half,left4-half,k-l ,tp);tempfun(top+half,left,k-l ,i+l ,j-l ,2);else %特殊方格在左下cove rm a trix(i,j)=2; %添加类型为

16、4的L型骨牌tempfun(top,left,k-l ,i-ltempfun(top,left+half,k-l ,i-l ,j+l ,4);tempfun(top+half,left4-half,k-l ,i+l ,j+l ,1 )；tempftin(top+half,left,k-l ,tp);endendend在MATLAB命令窗口中输入指令 chess co ver(3,l ,4)将会得到如上面矩阵一样的结果。结合VC+,利用MATLAB引擎库函数，可以给出了棋盘覆盖的图形最优树的应用实例1.1 问题的提出已知某通信系统在通信联络中只可能出现8种字符，其概率分别为0.05 ,0.29

17、, 0.07 , 0.08 , 0.14 , 0.23 , 0.03 , 0.11 ,试设计一种编码，使得信息包长 度达到最小。1.2 问题的分析ASCn码是用8位（一个字节）表示一个字符，这种表示方法方便，易于理解， 是计算机系统中常用的字符表示方法。在信息传输领域，可能有些字符出现的频率 非常高，而有些字符出现的频率很低，若依然用此方法表示数据，则显得过于庞大, 如果用不定长编码表示字符，频率出现高的字符用较短的编码表示，频率出现低的 字符用较长的编码表示，则可以使得数据量大大减少。比如 AAAABBBAAABBBBCCCCCCBBB,用 ASCH 码表示占用 184 位，若用 00 表示

18、 C, 01表示A, 1表示B,则该字串占用位数为36,压缩率达到19.6%,这种编码称为 哈夫曼编码。当然也可用其它方式压缩数据，例如上面字符串写成 4A3B3A4B6C3B,而达到压缩数据的目的。1.3 哈夫曼树的构造要构造哈夫曼编码，需要构造哈夫曼树（即最优树）。哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法。现叙述如下:根据给定的n个概率（或频率）构造一个集合 F f|2，L,fn ,同时这n个值对应树T的n个结点，置i n 1。f在集合F中选择两个最小的值求和作为i加入集合F中；在树T中构造一 结点，使得该结点是两最小值对应结点的父结点。 在集合F中删除两最小值，并置I】。

19、r 重复和，直到1或集合F只有一个元素为止。这样形成的一棵树就是哈夫曼树（最优树）。上面所提到的字符串和题目给出的概率所形成的哈夫曼树分别如图1和图 2（为方便起见，每个概率值乘上了 100）。图1图21.4用MATLAB哈夫曼算法在MATLAB中 哈夫曼算法，可用一个5 Q 11 1)的矩来表示哈夫曼,矩的 含如表6-3-3所示。表1哈夫曼算法数据构字符序号123452n-1概率父点序号左右子志0表示左子1表示右子是否在集合F1在集合F0不在集合F下面出哈夫曼的生成算法：function htree = HuffmanTree(pro)%构造哈夫曼%pro 一概率向量n=size(pro,2

20、);%得到字符个数tree=ones(6,2*n-l);% 构造 数据 构tree(l,:)=l:(2%-l);% 填充 点序号tree(5,(n-l-l):end)=0;% 置点是否在集合tree(2,l:n)=pro;% 设置概率tre e(6,l:e nd)=O;% 记录查找的结点对顺序for i=(n+l):(2*n-l);%循环控制1, r=fin d m in va 1( tre e); %找到集合中两个最小的值的序号tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值tree(5,i)=l;% 设置新构造结点在集合中tre e (3,l)=i;tre e (3 ,r)=i;%设置父结点序号tre e (4,1)=0; tre e (4, r)= 1; %设置左右标