matlab图论及最短路径算法

Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Module 00-,*,主讲人：孙云龙,数学建模课件,主讲人：孙云龙,数学建模课件,Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Module 00-,*,主讲人：孙云龙,数学建模课件,主讲人：孙云龙,数学建模课件,Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Module 00-,*,主讲人：孙云龙,数学建模课件,主讲人：孙云龙,数学建模课件,Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Matlab,软件与编程,主讲：孙云龙,MATLAB,通用数学软件,MATLAB：MATrix LABoratory,版本： Matlab:1984 Matlab 4.0:1993, Matlab 6.5:2002 Matlab 2021,特点：,数值计算 编程环境 适应性开放性 工程工具,工具箱80多,安装启动：,MATLAB,一、Matlab根底,超级计算：,+ -,*,/ = |&,标点： ；，：,%,其他：,clc clear vpa,m,文件,命令集,函数,function =filename( ),help,1、根本操作,1,、代数运算,创立矩阵,输入：行 逗号或空格 ，列分号或回车,生成向量：a:t:b linspace(a,b,n),产生矩阵, ,空矩阵,rand(m,n),均匀分布随机阵,zeros(m,n),0,矩阵,randn(m,n),正态分布随机矩阵,eye(m,n),单位矩阵,ones(m,n),1,矩阵,矩阵操作,取值,、赋值、更改、删除,元素,A(i,j),行,A(i,:),列,A(:,j),e01.m,矩阵运算,根本运算,AB A k A*B k * A AB B/A A,对应运算,A.* B A./ B A. B A.B exp log sqrt,复杂运算,det,（,A,）,行列式,rank(A),秩,inv(A),或,A (-1),逆,V,，,D=eig(A),特征值特征向量,size(A),阶数,rref(A),行阶梯最简式,另,：, ,2,、符号运算,定义符号,x =x x =sym(x) syms x y z,定义符号表达式,字符串,f =,符号型,syms x,，,f = ,运算符,f=inline(),M,函数文件,e02.m,4,、统计分析,概率分布,pdf cdf inv stat rnd,unif bino poiss norm exp t chi2 F,描述统计,sort,mean median,var std max min range,kurtosis skewness,corrcoef cov,参数估计,muhat,sigmahat,muci,sigamaci=,分布,+fit(x,alpha),统计绘图,Plot hist Bar Bar3 Pie Pie3 scatter Scatter3,非参数估计,Lillietest Kstest kstest kstest2,ranksum signrank Cdfplot,假设检验,ztest Ttest Ranksum,方差分析,Anova1 multcompare Anova2,回归分析,Regress Rcoplot,Rstool nlinfit nlintool,主成分分析,princomp Pcacov Comp.m,聚类分析,Zscore Pdist Squareform Linkage,Dendrogram Cluster,5,、优化,线性规划,x, fval= linprog (f, A,b,Aeq,beq,lb,ub),无约束,x, fval= fminbnd (f ,a,b),x, fval= fminunc(fun,x0),x, fval= fminsearch(fun,x0),有约束,x, fval= fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon),五、程序设计,1,、程序语句,算法,流程图,语言,if elseif else end,for end,while end,swith,break continue return pause input,2,、案例,某地区12个气象观测站近1979-2021年来各观测站测得的月降水量为data.m中：矩阵B行为月数据、列为12个观测站数据。求：,1各观测站月平均降雨量、标准差。,2月最大、最小降雨量为多少？发生在哪个气象站的哪一月份？,mean std,max min,例,1,例,2,个人所得税：工资、薪金所得适用,级数,全月应纳税所得额,（基数,2000,元）,年终奖,税率,(%),1,（,0,，,500,（,0,，,6000,）,5,2,（,500,，,2000,（,6000,，,24000,）,10,3,（,2000,，,5000,（,24000,，,60000,）,15,4,（,5000,，,20000,（,60000,，,240000,）,20,5,（,20000,，,40000,（,240000,，,480000,）,25,6,（,40000,，,60000,（,480000,，,720000,）,30,7,（,60000,，,80000,（,720000,，,960000,）,35,8,（,80000,，,100000,（,960000,，,1200000,）,40,9,（,100000,，,（,1200000,，,）,45,年奖金有什么问题？,问题,1,、纳税额计算函数,条件判断,程序,t1.m,t2.m,function f=t1(x),t=x-2000;,if t=0,f=0;,elseif t=500,f=t*0.05;,elseif t=2000,f=25+(t-500)*0.1;,else,f=29625+(t-100000)*0.45;,end,级数,月应纳税所得额,（基数,2000,元）,税率,(%),1,（,0,，,500,5,2,（,500,，,2000,10,3,（,2000,，,5000,15,4,（,5000,，,20000,20,9,（,100000,，,45,问题,2,、分配月收入、年奖金,合理避税,为什么,如何分,程序,搜索：定步长,for-end,while -end,纪录最优点,if-end,t3.m,算法,function min,k1 =tax3(x),k=0;,min=t1(x);,k1=0;,while kd1,min=d1;,k1=k;,end,k=k+1;,end,另：程序有问题？,mint,k1=t3(2500),继续：分配月收入、年奖金,非专业,报告,程序,t4.m,算法,循环,计算各种收入分配方式,归类,for i=1:n,A(1,i)=100*i;,A(2,i),A(3,i)=t5(A(1,i);,end,B=A(:,1);k=1;,for j=2:n,if A(3,j)=B(3,k),k=k+1;,B(:,k)=A(:,j);,end,end,B(:,k+1)=A(:,n),月收入,1002500,26003000,31005000,51006000,纳税,0 25,3050,60275,285375,作奖金,0,100500,500,11002000,610011000,1110012000,1210020000,3901225,12401375,13952975,2000,4100 5000,5000,t4.m,分配月收入、年奖金,结果,三、图论,哥尼斯堡七桥问题,问题,:,从某点出发通过每座桥且每桥只通过一次回到起点,.,点,:,陆地 岛屿,边,:,桥,A,B,C,D,D,A,B,C,1,、图的一般理论,一个图G由一个顶点集V和一个边的集E组成。,E中每个元素e是连接顶点集 V中两个顶点u和v的边。,例,:,图,G=:,点集,V = v,1,v,2, .,v,n,边集,E = e,1,e,2, .,e,m,其中,e,k,=v,i,v,j,图,G=:,其中,V = v,1,v,2,v,3,v,4,v,5,E = e,1,e,2,e,3,e,4,e,1,=v,1,v,2,e,2,=v,2,v,4,e,3,=v,1,v,4,e,4,=v,5,v,2,e,1,v,1,v,2,v,3,v,4,v,5,e,2,e,3,e,4,图的图形表示,例,联接,点的位置,边的长度,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,比较: 同构,G1,G2,G3,1,2,3,4,3,4,2,1,3,4,1,2,v,1,v,2,v,3,v,4,v,5,e,2,e,3,e,4,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,邻接矩阵,(,点点,),关联矩阵,(,点边,),例,2,、连通性,邻,接,长,2,通路,:,长,3,长,n-1,连通矩阵,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,l01.m,赋权图G,从点v0到其余结点的通路权和最小,Dijkstra算法思想,按路径长度递增顺序求最短路径算法,两个集合：S已求得最短路径的结点、V-S未确定,每一步：将S 与V-S之间最短路经终点参加S,存储,G：带权邻接矩阵,每点标记 (dj, pj)：至j点最短路径的长度、前一点,3,、单源最短路问题,Dijkstra,Dijkstra,算法流程,赋初值：w，,各点与源点之间：已求Sv0,最短长度d=w(v0,:)、前一点p= v0,u= v0,更新d、p：,假设d(i)d(u) +w(u,i)，那么d(i)=d(u) +w(u,i)，p(i)=u,寻找v：,V-S中使d(i)最小的v： SSv, u= v,假设V-S，重复2，,否那么：结束,v,0,v,u,d(v),d(u),w(u,v),distance,path,pathway= dijkstra(v0,w),最短路的长度、前点、路径 源点 带权邻接矩阵,说明：,Matlab,程序：,dijkstra.m,while kdistance(u)+w(u,i),distance(i)=distance(u)+w(u,i);,path(i)=u;,end,end,求v*:V-S中最小距离点,k=k+1;,s(k)=v;,u=s(k);,end,%,赋初值,s=v0; %,已求得最短路径的结点,distance=w(v0,:);,path=v0*ones(1,n);,u=s(1);,k=1; %s,长,dijkstra.m,求,v*:V-S,中最小距离点,%,求路径,%V-S,中距离,d=distance;,for i=1:n,for j=1:k,if i=s(j),d(i)=inf;,break,end,end,end,%V-S,中最小距离,dmin,v=min(d);,pathway=zeros(n);,pathway(1:n,1:2)=v0*ones(n,1),(1:n);,for i=1:n,q=i;,while path(q)=v0,pathway(i,2:n)=path(q),pathway(i,2:(n-1);,q=path(q);,end,end,例,v,1,v,2,v,3,v,4,v,5,8,6,9,1,5,7,10,3,OK,l02.m,带权邻接矩阵,Floyd,算法思想,带权邻接矩阵,两点之间,插入顶点,缩短距离：构造出个矩阵,D,(1),、,D,(2),、,、,D,(n-1),最后得到距离矩阵,最短路径,递推公式,4,、每对顶点之间的最短路,Floyd,带权,邻接,矩阵,例：,1 2 3,4 5 6 7,8 9 10,1 1,4 1 3 6 2 7,2 3 5 4 1,1 3,2 2,矩阵,两点之间：插入顶点,1 2 3,4 5 6 7,8 9 10,1 1,4 1 3 6 2 7,2 3 5 4 1,1 3,2 2,15,通过,1,点,于是,15,通过,1,点,于是,按,1,、,2,会不会错过一些点？,Matlab,程序：,floyd,.m,%,设初值,D=w;,path=zeros(n);,for i=1:n,for j=1:n,if D(i,j)=inf,path(i,j)=j;,end,end,end,floyd,.m,%,迭代，更新,D path,for k=1:n,for i=1:n,for j=1:n,if D(i,k)+D(k,j)D(i,j),D(i,j)=D(i,k)+D(k,j);,path(i,j)=path(i,k);,end,end,end,end,D,path=floyd(w),最短路的长度、后点 带权邻接矩阵,例,OK,l03.m,得到：,最短路、后点,路径？,1 2 3,4 5 6 7,8 9 10,1 1,4 1 3 6 2 7,2 3 5 4 1,1 3,2 2,求路径,function pathway=road(path,v1,v2),%,求路径：,floyd,的后续指令,pathway=v1;q=v1;k=1;,while path(q,v2)=v2,k=k+1;,pathway(k)=path(q,v2);,q=path(q,v2);,end,pathway(k+1)=v2;,road.m,l03.m,函数,v1,与,v2,之间,路径起点 辅助点 循环变量起点,循环：,q,至,v2,后点不是,v2,循环变量增加,为纪录,路径增加点,辅助点为新点,到终点,v2,结束,路径终点,v2,存在一条通过所有边一次的路线的图：遍历边,Th 假设图 G 为欧拉图 G 连通,且所有结点度数(以此点为端点的边的个数)均为偶数,哥尼斯堡七桥问题,过桥,求解,:,非欧拉图,无解,A,B,C,D,1,、欧拉图,三、遍历问题,介绍,:,中国邮路问题,带权图,:,边加权,最小遍历,:,边 回路,例,:,无欧拉回路 找 权和最小的回路,B,1,30,3,5,1,2,3,50,2,40,60,2,I,A,C,D,E,F,G,H,中国邮路,:,A B C F I H I F E B E H G D E D A,权和,: 208,2,、哈密顿图,周游世界,20,个城市,20,个城市,:,平均分布在世界各地,存在通过每结点一次的路线的图：遍历点,国际难题,目前,:,近似算法,例,介绍,:,旅行商问题,带权图,找通过每一点 权和最小的回路,5,、遍历问题,欧拉图：遍历边不重复,哈密尔顿：遍历点不重复,遍历点可重复：最小生成树,树：无回路的连通图: 树根, 树叶, 树枝,例：,方法：避圈法,1,2,4,8,6,2,2,3,v,1,v,2,v,3,v,4,v,5,v,6,1,2,6,2,2,v,1,v,2,v,3,v,4,v,5,v,6,Kruskal,算法,避圈法,开始：,G,中的边均为白色,在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；,重复：直到有,n-1,条红色边，这,n-1,条红色边便构成最小生成树,T,的边集合,注：如何加边判断不形成圈？,判断两端点是否属于同一子树,子树：用最小标号点纪录,最小生成树,Kruskal,纪录两端点与边权,Matlab,程序：,Kruskal.m,n=size(w,1);,%,求点边矩阵,k=1;,for i=1:(n-1),for j=(i+1):n,if w(i,j)=inf,b(:,k)=i;j;w(i,j);,k=k+1;,end,end,end,m=size(b,2);,b,I=sortrows(b,3),b=b,排序,kruskal.m,树,权和,所在子树的,最小标号点,进入最小树,的边数,for i=1:m,if t(b(1,i)=t(b(2,i),T(1:2,k)=b(1:2,i);,c=c+b(3,i);,tmin=min(t(b(1,i),t(b(2,i);,tmax=max(t(b(1,i),t(b(2,i);,for j=1:n,if t(j)=tmax,t(j)=tmin;,end,end,k=k+1;,end,if k=n,break;,end,end,T=;,c=0;,t=1:n;,k=1;,更新子树,的最小标号点,赋初值,不在同一子树,例,v,1,v,2,v,3,v,4,v,5,8,6,9,1,5,7,10,3,OK,l04.m,带权邻接矩阵,结果,T =1 4 2 2,4 5 3 5,c =17,练习,1、建立m文件，键入：,1保存，文件名为1，执行此文件,2另存为，文件名为m3，执行此文件,问题：,两个文件执行结果是否相同，正确答案为多少？为什么？,2、建立m函数文件，函数为：,并计算,练习,设A= ，B= ，b=,1、求A*B,2、取B的前4列为C，计算A+C，A-C/3,3、求A的行列式，逆矩阵,4、求B的秩,5、求线性方程组BX=b的解,6、求A的特征值、特征向量,一、计算,1、,2、,3、,二、解方程,4、,5、,6、,练习,曲线f(x)=sin2x/x2；,红色，点线，标记x y轴、曲线名,曲面,x y均在-2，2，去掉网格，无刻度,练习,求和 1+2+4+8+1024,求伴随矩阵,分段函数作图x在-3，3，红色，*点线,验证哥德巴赫猜测,1000以内的整数：任何一个大偶数都可以表示成两个素数之和。,练习,练习,某街道如图,画出A点到各顶点的最短道路最短路经生成树,欲建立有线网络连接,画出此街道各顶点均相联的最短道路最优生成树,A,1 3 4,2 1 6 1,2 3 1,4 2 5 6,3 2 1,end,