139
§19. 利用Matlab 编程计算最短路径及中
位点选址
1、最短路问题
两个指定顶点之间的最短路径。
例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。
以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。
求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。
(ii) 对每个i S v ∈（i i S V S \=），用
)}
()(),({min uv w u l v l i
S u +∈
代替)(v l 。计算)}({min v l i
S v ∈，把达到这个最小值的一个顶点记为1+i u ，令
140
}
{11++=i i i u S S 。
(iii). 若1||-=V i ，停止；若1||- 算法结束时，从0u 到各顶点v 的距离由v 的最后一次的标号)(v l 给出。在v 进入i S 之前的标号)(v l 叫T 标号，v 进入i S 时的标号)(v l 叫P 标号。算法就是不断修改各项点的T 标号，直至获得P 标号。若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u 至各项点的最短路也在图上标示出来了。 例1： 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票 价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ???????? ??????????∞ ∞∞∞∞∞055 25 25 10 550102025251001020402010015252015050102540500 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、 2 index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路 的值。其中分量 ?? ?=顶点未标号 当第顶点已标号当第i i i pb 0 1 )(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； d存放由始点到第i点最短通路的值。 (i ) 求第一个城市到其它城市的最短路径的Matlab程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;d(1:length(a))=M;d(1)=0;temp=1; while sum(pb) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; end d 运行输出，第一个城市到其它城市的最短路径长度，即： d = 0 35 45 35 25 10 2、选址问题－以中位点选址为例 中位点选址问题的质量判据为：使最佳选址为止所在的定点到网络图中其他顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。 例2：某县下属七个乡镇，各乡镇所拥有的人口数a(v i)（i=1，2，…，7），以及各乡镇之间的距离w ij（i，j=1，2，…，7）如图所示。现在需要设立一个中心邮局，为全县所辖的七个乡镇共同服务。试问该中心邮局应该设在哪一个乡镇 141 142 （图中的哪一个顶点）？ 图9.2.3 第一步，用标号法求出每一个顶点vi 至其它各个顶点vj 的最短路径长度d ij （i ，j ＝ 1，2，…，7），并将其写成如下距离矩阵： ?? ????? ??? ? ??=7776 75 74 73 72 71 6766656463626157 56555453525147464544434241 37363534333231 2726252423222117161514131211 d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d D 第二步，以各顶点的载荷（人口数）加权，求每一个顶点至其它各个顶点的最短路径长度的加权和，可在Matlab 环境下用矩阵运算求得： 定义各顶点的载荷矩阵： ] 4.1. 5.1.7.2,3[)](),(),(),(),(),(),([7654321==v a v a v a v a v a v a v a A A D v S v S v S v S v S v S v S S *)](),(),(),(),(),(),([7654321== 输出结果：S 第三步，判断 )} ( { min i i v S 计算如下： 第一步： clear; clc; M=10000; for i=1:length(a) pb(1:length(a))=0;pb(i)=1; d(1:length(a))=M;d(i)=0;temp=i; while sum(pb) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; end; ShortPath(i,:)=d; end; ShortPath; 运行后输出最短距离矩阵，即ShortPath ShortPath = 0 3.0000 5.0000 6.3000 9.3000 4.5000 6.0000 3.0000 0 2.0000 3.3000 6.3000 1.5000 3.0000 5.0000 2.0000 0 2.0000 5.0000 3.5000 5.0000 6.3000 3.3000 2.0000 0 3.0000 1.8000 3.3000 9.3000 6.3000 5.0000 3.0000 0 4.8000 6.3000 4.5000 1.5000 3.5000 1.8000 4.8000 0 1.5000 6.0000 3.0000 5.0000 3.3000 6.3000 1.5000 0 第二步： A=[3 2 7 1 5 1 4]; S= ShortPath * A'; 143 144 运行后输出S ，即每一个顶点至其它各个顶点的最短路径长度的加权和： S = 122.3000 71.3000 69.5000 69.5000 108.5000 72.8000 95.3000 第三步： min(S) 运行后输出S 的最小值： ans = 69.5000 判断：因为5.69)}({min )()(43===i i v S v S v S 。所以，v 3和v 4都是图9.2.3 的中位点。也就是说，中心邮局设在v 3或v 4都是可行的。 课题一： 连续时间信号和系统时域分析及MATLAB实现 课题要求： 深入研究连续时间信号和系统时域分析的理论知识。利用MATLAB强大的图形处理功能、符号运算功能以及数值计算功能，实现连续时间信号和系统时域分析的仿真波形。 课题内容： 一、用MATLAB实现常用连续时间信号的时域波形（通过改变参数，分析其时域特性）。 1、单位阶跃信号， 2、单位冲激信号， 3、正弦信号， 4、实指数信号， 5、虚指数信号， 6、复指数信号。 二、用MATLAB实现信号的时域运算 1、相加， 2、相乘， 3、数乘， 4、微分， 5、积分 三、用MATLAB实现信号的时域变换（参数变化，分析波形变化） 1、反转， 2、使移（超时，延时）， 3、展缩， 4、倒相， 5、综合变化 四、用MATLAB实现信号简单的时域分解 1、信号的交直流分解， 2、信号的奇偶分解 五、用MATLAB实现连续时间系统的卷积积分的仿真波形 给出几个典型例子，对每个例子，要求画出对应波形。 六、用MATLAB实现连续时间系统的冲激响应、阶跃响应的仿真波形。 给出几个典型例子，四种调用格式。 七、利用MATLAB实现连续时间系统对正弦信号、实指数信号的零状态响应的仿真波形。 给出几个典型例子，要求可以改变激励的参数，分析波形的变化。 课题二： 离散时间信号和系统时域分析及MATLAB实现。 课题要求： 深入研究离散时间信号和系统时域分析的理论知识。利用MATLAB强大的图 形处理功能、符号运算功能以及数值计算功能，实现离散时间信号和系统时域分析的仿真波形。 课题内容： 一、用MATLAB绘制常用信号的时域波形（通过改变参数分析其时域特性） 1、单位序列， 2、单位阶跃序列， 3、正弦序列， 4、离散时间实指数序列， 5、离散时间虚指数序列， 6、离散时间复指数序列。 二、用MATLAB实现信号的时域运算 1、相加， 2、相乘， 3、数乘。 三、用MATLAB实现信号的时域变换（参数变化，分析波形的变化） 1、反转， 2、时移（超时，延时）， 3、展缩， 4、倒相。 四、用MATLAB实现离散时间系统卷积和仿真波形 给出几个典型例子，对每个例子要求画出e(k)，h(k)，e(i)，h(i)，h(-i)，Rzs(k)波形。 五、用MATLAB实现离散时间系统的单位响应，阶跃响应的仿真波形 给出几个典型例子，四中调用格式。 六、用MATLAB实现离散时间系统对实指数序列信号的零状态响应的仿真波形 给出几个典型例子，要求可以改变激励的参数，分析波形的变化。 课题三： 连续时间信号傅里叶级数分析及MATLAB实现。 课题要求： 深入研究连续时间信号傅里叶级数分析的理论知识，利用MATLAB强大的图形处理功能，符号运算功能以及数值计算功能，实现连续时间周期信号频域分析的仿真波形。 课题内容： 一、用MATLAB实现周期信号的傅里叶级数分解与综合 以周期矩形波信号为例，绘出包含不同谐波次数的合成波形，观察合成波形与原矩形 波形之间的关系及吉布斯现象。 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )}()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- 课程设计任务书 学生姓名：董航专业班级：电信1006班 指导教师：阙大顺，李景松工作单位：信息工程学院 课程设计名称：Matlab应用课程设计 课程设计题目：Matlab运算与应用设计5 初始条件： 1.Matlab6.5以上版本软件； 2.课程设计辅导资料：“Matlab语言基础及使用入门”、“Matlab及在电子信息课程中的应 用”、线性代数及相关书籍等； 3.先修课程：高等数学、线性代数、电路、Matlab应用实践及信号处理类相关课程等。 要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1.课程设计内容：根据指导老师给定的7套题目，按规定选择其中1套完成； 2.本课程设计统一技术要求：研读辅导资料对应章节，对选定的设计题目进行理论分析， 针对具体设计部分的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码（含注释），上机调试运行程序，记录实验结果（含计算结果和图表），并对实验结果进行分析和总结。具体设计要求包括： ①初步了解Matlab、熟悉Matlab界面、进行简单操作； ②MATLAB的数值计算：创建矩阵矩阵运算、多项式运算、线性方程组、数值统计； ③基本绘图函数：plot, plot3, mesh, surf等，要求掌握以上绘图函数的用法、简单图形 标注、简单颜色设定等； ④使用文本编辑器编辑m文件，函数调用； ⑤能进行简单的信号处理Matlab编程； ⑥按要求参加课程设计实验演示和答辩等。 3.课程设计说明书按学校“课程设计工作规范”中的“统一书写格式”撰写，具体包括： ①目录； ②与设计题目相关的理论分析、归纳和总结； ③与设计内容相关的原理分析、建模、推导、可行性分析； ④程序设计框图、程序代码（含注释）、程序运行结果和图表、实验结果分析和总结； ⑤课程设计的心得体会（至少500字）； ⑥参考文献（不少于5篇）； ⑦其它必要内容等。 时间安排：1.5周（分散进行） 参考文献： [1](美)穆尔,高会生,刘童娜,李聪聪．MA TLAB实用教程(第二版) . 电子工业出版社,2010. [2]王正林,刘明．精通MATLAB(升级版) .电子工业出版社,2011. [3]陈杰. MA TLAB宝典(第3版) . 电子工业出版社,2011. [4]刘保柱,苏彦华,张宏林. MATLAB 7.0从入门到精通(修订版) . 人民邮电出版社,2010. 指导教师签名：年月日 系主任（或责任教师）签名：年月日 硕士生考查课程考试试卷 考试科目：MATLAB教程 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：20 年月日午时至时 《MATLAB教程》试题： A、利用MATLAB设计遗传算法程序，寻找下图11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。 a c d e f h i k 1 2 1 6 8 3 1 7 9 4 6 7 2 9 4 2 1 1 B、设计遗传算法求解f(x)极小值，具体表达式如下： 要求必须使用m函数方式设计程序。 C、利用MATLAB编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D、结合自己的研究方向选择合适的问题，利用MATLAB进行实验。 以上四题任选一题进行实验，并写出实验报告。 选择题目： A 一、问题分析（10分） 1 2 3 4 5 6 8 9 10 11 1 2 1 6 8 3 1 7 9 4 6 7 2 9 4 2 1 1 如图如示，将节点编号，依次为 1.2.3.4.5.6.7.8.9.10.11，由图论知识，则可写出其带权邻接矩阵为： 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0 注：为避免计算时无穷大数吃掉小数，此处为令inf=500。 问题要求求出任意两点间的最短路径，Floyd算法采用的是在两点间尝试插入顶点，比较距离长短的方法。我思考后认为，用遗传算法很难找到一个可以统一表示最短路径的函数，但是可以对每一对点分别计算，然后加入for循环，可将相互之间的所有情况解出。观察本题可发现，所有节点都是可双向行走，则可只计算i到j的路径与距离，然后将矩阵按主对角线翻折即可得到全部数据。二、实验原理与数学模型（20分） 实现原理为遗传算法原理： 按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使得适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。 数学模型如下： 设图由非空点集合和边集合组成，其中 又设的值为，故可表示为一个三元组 则求最短路径的数学模型可以描述为： 自控系统仿真软件课程设计报告 MATLAB 设计题目：牛顿摆球 姓名： 学号： 院系： 班级：1203 指导教师： 2014年12月20日 一．课程设计目的 1、熟悉课程设计的基本流程； 2、掌握MATLAB语法结构及调试方法； 3、熟悉MATLAB函数调用，熟练二维画图; 4、掌握MATLAB语言在控制方面的运用； 5、学会用MATLAB进行基本仿真； 6、掌握MATLAB编程技巧，提高编程水平。 二．系统分析 1.题目的描述： （1）牛顿摆球原理描述 五个质量相同的球体由吊绳固定，彼此紧密排列。当摆动最右侧的球并在回摆时碰撞紧密排列的另外四个球，最左边的球将被弹出，并仅有最左边的球被弹出。当然此过程也是可逆的，当摆动最左侧的球撞击其它球时，最右侧的球会被弹出。当最右侧的两个球同时摆动并撞击其他球时，最左侧的两个球会被弹出。同理相反方向同样可行，并适用于更多的球。 为了更接近现实，在这里我将考虑重力及空气阻力的影响，摆球将不会永无止境的运动下去，由于外界因素的影响，摆球运动一段时间后将回归静止状态。（2）通过MATLAB动画程序制作软件，实现下述过程 当运行程序时，把最右边的小球拉到一定的高度放下，让其碰撞其余四个小球，仅让最左边的小球被弹出，当最左边小球回摆碰撞其它球时，最右边小球又被弹出，如此循环。由于是非理想条件下，摆球的摆动幅度会随摆动次数的增加越来越小，直到静止。 时间停顿两秒，把右边两小球一起拉到一定高度放下，让其碰撞其余三个球，同样仅让左边两球被弹出，当球回摆再次碰撞时，最右边两球又被同时弹出，如此循环，因为外界因素的影响，最终五个球都会静止下来。 （3）整个实验看似简单，但要在MATLAB上完成这样一个动画过程，还是需要下点功夫，克服困难的。经过自己的努力，终于实现了整个过程，这也是一种不小的收获。 2.设计要求： （1）能够实现有阻尼摆动，即摆幅随摆动次数增加越来越小，直到静止。（2）能够让摆球弧线摆动。 三．系统设计 1.系统设计过程 （1）通过函数axis建立坐标系 （2）在坐标系范围内通过函数line画各个支架 （3）通过函数title添加标题“动量守恒实验”、函数text添加标注“牛顿摆球” （4）通过函数line画出五个球，并设定其初始位置，颜色,大小,线条的擦拭方式 算法描述： 输入图G，源点v0，输出源点到各点的最短距离D 中间变量v0保存当前已经处理到的顶点集合，v1保存剩余的集合 1.初始化v1,D 2.计算v0到v1各点的最短距离，保存到D for each i in v0;D(j)=min[D(j),G(v0(1),i)+G(i,j)] ,where j in v1 3.将D中最小的那一项加入到v0，并且从v1删除这一项。 4.转到2，直到v0包含所有顶点。 %dijsk最短路径算法 clear,clc G=[ inf inf 10 inf 30 100; inf inf 5 inf inf inf; inf 5 inf 50 inf inf; inf inf inf inf inf 10; inf inf inf 20 inf 60; inf inf inf inf inf inf; ]; %邻接矩阵 N=size(G,1); %顶点数 v0=1; %源点 v1=ones(1,N); %除去原点后的集合 v1(v0)=0; %计算和源点最近的点 D=G(v0,:); while 1 D2=D; for i=1:N if v1(i)==0 D2(i)=inf; end end D2 [Dmin id]=min(D2); if isinf(Dmin),error,end v0=[v0 id] %将最近的点加入v0集合，并从v1集合中删除 v1(id)=0; if size(v0,2)==N,break;end %计算v0（1）到v1各点的最近距离 fprintf('计算v0（1）到v1各点的最近距离\n');v0,v1 id=0; for j=1:N %计算到j的最近距离 if v1(j) TRANSPOWORLD 2009 No.12 (Jun) 104前言 在现实生活中，我们经常遇到最短路问题，例如寻找两点之间总长度最短或者费用最低的路径。在运输、物流、设施选址以及人员调度问题中，最短路径是很常见的问题。解决最短路问题的方法有很多，例如迪杰斯特拉算法、福特算法。在这里我们介绍基于遗传算法的最短路径问题的解决方案。 模型 遗传算法基本模型 遗传算法是模仿生物进化过程，针对复杂问题开发出来的非常有效的方 基于遗传算法的最短路径问题及其MATLAB 实现 文/张书源 郭 聪 法。根据生物进化过程中的选择机制，在问题的解空间中进行选择，实现“物竞天择，适者生存”。在遗传算法中，一条染色体代表问题的一个可行解，该染色体的适应值即为对应于该可行解的函数值。一般来说，遗传算法包括以下几个主要组成部分。编码 即将问题的解表示成一个编码串（染色体），每一染色体对应问题的一 个解。遗传过程 对染色体进行操作，以产生新的染色体，通常有不同染色体之间的交叉 操作以及一条染色体的变异操作。评价与选择 对每条染色体计算其适应值，用以评价染色体的优劣，从而从父代和子代中选择较优的染色体，进入下一代的繁殖。 初试种群的创建方法 其作为问题可行解的集合。初始种群中染色体个数称为种群规模。 遗传算法的流程图如图1所示。算法过程如下: 第一步初始化种群p(t)；第二步对种群进行评价； 第三步利用交叉和变异重组p(t)以产生c(t) 第四步评价c(t)，从p(t)和c(t)选择出p(t+1)，令t=t+1；若达到繁殖代数，转第五步；否则，回第四步； 第五步返回结果。 问题描述 在图2所示的算例中，我们要找到从节点①到节点⑨的最短路径。基于优先权的编码方式 例如，一条可能的染色体如表1。路径生长 路径生长即为根据一条染色体来得到其对应的一条路。在表1的例子中，路径生长的过程如下： 初试路径上只有节点①； 与①相连且不在当前路径上的节点有②和③，其中节点③的权较大，为6，将节点③加入当前路径，当前路径变为：①—③； 与③相连且不在当前路径上的节 点有④和⑤，其中节点⑤的权较大，为 图2 C OLUMNS 特别企划 第一类：单位转换 1.长度单位换算的设计与实现 2.面积单位换算的设计与实现 3.体积单位换算的设计与实现 4.容积单位换算的设计与实现 5.质量单位换算的设计与实现 6.时间单位换算的设计与实现 7.温度单位换算的设计与实现 7.压强单位换算的设计与实现 8.角度单位换算的设计与实现 8.功率单位换算的设计与实现 第二类：曲线绘制 1.直线的自动绘制和相关计算 2.椭圆的自动绘制和相关计算 3.双曲线的自动绘制和相关计算 4.抛物线的自动绘制和相关计算 5.心脏线的自动绘制和相关计算 6.渐开线的自动绘制和相关计算 7.滚圆线的自动绘制和相关计算 8.三叶玫瑰线的自动绘制和相关计算9.四叶玫瑰线的自动绘制和相关计 10.阿基米德螺线的自动绘制和相关计算第三类：曲面绘制 1.球面的自动绘制和相关计算 2.椭球面的自动绘制和相关计算 3.单叶双曲面的自动绘制和相关计算 4.双叶双曲面的自动绘制和相关计算 5.抛物面的自动绘制和相关计算 6.双曲抛物面的自动绘制和相关计算 7.双曲柱面的自动绘制和相关计算 8.椭圆柱面的自动绘制和相关计算 9.抛物柱面的自动绘制和相关计算 10.圆锥面的自动绘制和相关计算 第四类：线性回归 1.男士身高体重相关计算经验公式 2.女士身高体重相关计算经验公式 3.男士胖瘦等级的确定 4.女士胖瘦等级的确定 5.男士身高脚长相关计算经验公式 6.女士身高脚长相关计算经验公式 7.父子身高相关性研究 8.母子身高相关性研究 9.父女身高相关性研究 10.母女身高相关性研究 第五类：学习成绩 1.期末总评自动计算的设计与实现 2.成绩等级自动评定的设计与实现 3.成绩分段自动统计的设计与实现 4.成绩分布折线自动绘制的设计与实现 5.成绩自动统计分析的设计与实现 6.试卷分布自动分析的设计与实现 7.试卷难度自动分析的设计与实现 8.考试成绩名次自动生成的设计与实现 最短路径法射线追踪的MATLAB 实现 李志辉 刘争平 （西南交通大学土木工程学院 成都 610031） 摘 要：本文探讨了在MA TLAB 环境中实现最短路径射线追踪的方法和步骤，并通过数值模拟演示了所编程序在射线追踪正演计算中的应用。 关键词：最短路径法 射线追踪 MATLAB 数值模拟 利用地震初至波确定近地表介质结构，在矿产资源的勘探开发及工程建设中有重要作用。地震射线追踪方法是研究地震波传播的有效工具，目前常用的方法主要有有限差分解程函方程法和最小路径法。最短路径方法起源于网络理论，首次由Nakanishi 和Yamaguchi 应用域地震射线追踪中。Moser 以及Klimes 和Kvasnicha 对最短路径方法进行了详细研究。通过科技人员的不断研究，最短路径方法目前已发展较为成熟，其基本算法的计算程序也较为固定。 被称作是第四代计算机语言的MA TLAB 语言，利用其丰富的函数资源把编程人员从繁琐的程序代码中解放出来。MA TLAB 用更直观的、符合人们思维习惯的代码，为用户提供了直观、简洁的程序开发环境。本文介绍运用Matlab 实现最短路径法的方法和步骤，便于科研院校教学中讲授、演示和理解最短路径方法及其应用。 1 最短路径法射线追踪方法原理 最短路径法的基础是Fermat 原理及图论中的最短路径理论。其基本思路是，对实际介质进行离散化，将这个介质剖分成一系列小单元，在单元边界上设置若干节点，并将彼此向量的节点相连构成一个网络。网络中，速度场分布在离散的节点上。相邻节点之间的旅行时为他们之间欧氏距离与其平均慢度之积。将波阵面看成式由有限个离散点次级源组成，对于某个次级源（即某个网格节点），选取与其所有相邻的点（邻域点）组成计算网格点；由一个源点出发，计算出从源点到计算网格点的透射走时、射线路径、和射线长度；然后把除震源之外的所有网格点相继当作次级源，选取该节点相应的计算网格点，计算出从次级源点到计算网格点的透射走时、射线路径、和射线长度；将每次计算出来的走时加上从震源到次级源的走时，作为震源点到该网格节点的走时，记录下相应的射线路径位置及射线长度。 图1 离散化模型（星点表示震源或次级震源，空心点为对应计算网格点） 根据Fermat 原理逐步计算最小走时及射线方向。设Ω为已知走时点q 的集合，p 为与其相邻的未知走时点，tq 分别和p 点的最小走时，tqp 为q 至p 最小走时。r 为p 的次级源位置，则 )}(min :{qp q P t t t q r q +==Ω ∈ 根据Huygens 原理，q 只需遍历Q 的边界（即波前点），当所有波前邻点的最小走时都求出时，这些点又成为新的波前点。应用网络理论中的最短路径算法，可以同时求出从震源点传至所有节点之间的连线近似地震射线路径。 2 最短路径法射线追踪基本算法步骤 把网格上的所有节点分成集合p 和q ，p 为已知最小旅行时的结点总数集合，q 为未知最小旅行时的节点的集合。若节点总数为n ，经过n 次迭代后可为求出所有节点的最小旅行时。过程如下： 1) 初始时 q 集合包含所有节点，除震源s 的旅行时已知为ts ＝0外，其余所有节点的旅行时均为ti ＝（i 属于Q 但不 等于s ）。P 集合为空集。 2) 在Q 中找一个旅行时最小的节点i ，它的旅行时为ti ； 3) 确定与节点i 相连的所有节点的集合V ； 4) 求节点j （j 属于V 且j 不属于P ）与节点i 连线的旅行时dtij ； 5) 求节点j （）的新旅行时tj （取原有旅行时tj 与tj ＋dtij 的最小值）； 6) 将i 点从Q 集合转到P 集合； 7) 若P 集合中的节点个数小于总节点数N ，转2，否则结束旅行时追踪； 8) 从接收点开始倒推出各道从源点道接收点的射线路径，只要每个节点记下使它形成最小旅行时的前一个节点号， Matalab课后作业 学院：电气信息工程及其自动化 班级： 学号： 姓名： 完成日期： 2012年12月23日 1、 matlab 软件主要功能是什么？电气工程及其自动化专业本科生主要用到哪 些工具箱，各有什么功能？ 答：（1）主要功能：工业研究与开发； 数学教学，特别是线性代数；数值分析和科学计算方面的教学与研究；电子学、控制理论和物理学等工程和科学学科方面的教学与研究； 经济学、化学和生物学等计算问题的所有其他领域中的教学与研究；符号计算功能；优化工具；数据分析和可视化功能；“活”笔记本功能；工具箱；非线性动态系统建模和仿真功能。 （2）常用工具箱： （a ） MATLAB 主工具箱：扩充matlab 的数值计算、符号运算功能、图形建模仿真功能、文字处理功能以及与硬件实时交互功能。 （b ）符号数学工具箱：符号表达式、符号矩阵的创建；符号可变精度求解；因式分解、展开和简化；符号代数方程求解；符号微积分；符号微分方程。 （c ） SIMULINK 仿真工具箱： Simulink 是用于动态系统和嵌入式系统的多领域仿真和基于模型的设计工具。对各种时变系统，包括通讯、控制、信号处理、视频处理和图像处理系统，Simulink 提供了交互式图形化环境和可定制模块库来对其进行设计、仿真、执行和测试。 （d ）信号处理工具箱：数字和模拟滤波器设计、应用及仿真；谱分析和估计；FFT 、DCT 等 变换；参数化模型。 （e ）控制系统工具箱：连续系统设计和离散系统设计；状态空间和传递函数以及模型转换；时域响应（脉冲响应、阶跃响应、斜坡响应）；频域响应（Bode 图、Nyquist 图）；根轨迹、极点配置。 2、设y=23e t 4-sin(43t+3 ),要求以0.01秒为间隔，求出y 的151个点，并求出其导数的值和曲线。 程序如下： clc clear x=0:0.01:1.5; y=sqrt(3)/2*exp(-4*x).*sin(4*sqrt(3)*x+pi/3); y1=diff(y); subplot(2,1,1) plot(x,y) subplot(2,1,2) plot(x(1:150),y1) 曲线如下图所示： 用ACO 算法求解机器人路径优化问题 4.1 问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士在文献[30]中给出改进模型（ACS），文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示，AE 之间有 课程设计任务书 学生姓名：专业班级：电信 指导教师：工作单位：信息工程学院 题目:MATLAB运算与应用设计2 初始条件： 1.MATLAB6.5以上版本软件； 2.课程设计辅导资料：“MATLAB语言基础及使用入门”、“MATLAB及在电子信息课程中的 应用”等； 3.先修课程：信号与系统、数字信号处理、MATLAB应用实践及信号处理类课程等。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说 明书撰写等具体要求） （1）选择一本《MATLAB教程》，学习该教程的全部内容，包括使用方法、数组运算、矩阵运算、数学运算、程序设计、符号计算、图形绘制、GUI设计等内容； （2）对该套综合题的10道题，进行理论分析，针对具体设计部分的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码（含注释），上机调试运行程序，记录实验结果（含计算结果和图表）。 （3）对实验结果进行分析和总结； （4）要求阅读相关参考文献不少于5篇； （5）根据课程设计有关规范，按时、独立完成课程设计说明书。 时间安排: (1) 布置课程设计任务,查阅资料,学习《MATLAB教程》十周； (2) 进行编程设计一周； (3) 完成课程设计报告书一周； 指导教师签名：年月日 系主任（或责任教师）签名：年月日 目录 1 MATLAB概述 (3) 1.1MATLAB简介 (4) 1.2MATLAB的功能 (4) 1.3MATLAB 的典型应用 (6) 2设计题目：MATLAB运算与应用设计套题二 (6) 3设计内容 (8) 3.1 题一 (8) 3.2 题二 (8) 3.3 题三 (9) 3.4 题四 (10) 3.5 题五 (15) 3.6 题六 (15) 3.7 题七 (15) 3.8 题八 (16) 3.9 题九 (17) 3.10题十 (18) 4 课程设计心得 (20) 5参考文献 (21) 6 本科生课程设计成绩评定表 (22) 蚁群算法最短路径通用Matlab程序（附图） function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/897571526.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 1. 已知矩阵????????????????=5432141097539108627810715675A ，矩阵????? ?? ?????????=60151403514436136349624B ，解线性方程X ，使得A.X=B ，并将矩阵A 的右下角2×3子矩阵赋给矩阵C 。 程序：A=sym([5,7,6,5,1;7,10,8,7,2;6,8,10,9,3;5,7,9,10,4;1,2,3,4,5]); B=sym([24,96;34,136;36,144;35,140;15,60]); X=A\B C=A([4,5],[3,4,5]) 运行结果：X = [ 1, 4] [ 1, 4] [ 1, 4] [ 1, 4] [ 1, 4] C = [ 9, 10, 4] [ 3, 4, 5] 2. 根据下面两个矩阵 ???? ??????=??????????=987654321,136782078451220124B A 执行下列的矩阵运算命令，并回答有关的问题 （1） A+5*B 和A-B+I 分别是多少（其中I 为单位矩阵）？ （2） A.*B 和 A*B 将分别给出什么结果，它们是否相同，为什么？ 得出A.^B 、A/B 及A\B 的结果，并分别解释它们的物理意义。 程序：A=[4,12,20;12,45,78;20,78,136]; B=[1,2,3;4,5,6;7,8,9]; I=[1,0,0;0,1,0;0,0,1]; C=A+5*B D=A-B+I E=A.*B F=A*B G=A.^B H=A/B J=A\B A=sym([4 12 20;12 45 78;20 78 136])； B=sym([1 2 3;4 5 6;7 8 9])； I=sym([1 0 0;0 1 0; 0 0 1])； A+5*B A-B+I A.*B %A.为A的共轭矩阵，本式为A的共轭矩阵和B相乘 A*B %A直接和矩阵B相乘，结果与上面显然不同 A.^B %A的共轭矩阵的B次方 A/B %右除解XB=A A\B %左除解AX=B 运行结果： ans = [ 9, 22, 35] [ 32, 70, 108] [ 55, 118, 181] ans = [ 4, 10, 17] [ 8, 41, 72] [ 13, 70, 128] ans = [ 4, 24, 60] [ 48, 225, 468] [ 140, 624, 1224] ans = [ 192, 228, 264] [ 738, 873, 1008] [ 1284, 1518, 1752] 《MATLAB》课程设计球面的自动绘制与相关计算 院（系）名称信息工程学院 专业班级09普本信计1班 学号090111011 学生姓名张云迪 指导教师马艳琴 2011年6月6日 MATLAB课程设计评阅书 题目球面的自动绘制与相关计算 学生姓名张云迪学号090111011 指导教师评语及成绩 指导教师签名： 年月日答辩评语及成绩 答辩教师签名： 年月日教研室意见 总成绩： 教研室主任签名： 年月日 课程设计任务书 2010—2011学年第二学期 专业班级：09普本信计1班学号：090111011姓名：张云迪 课程设计名称： MATLAB 设计题目：球面的自动绘制与相关计算 完成期限：自2011年06月06日至2011年06月12日共1周 一、设计目的 由于在平时人工绘制的三维图形比较复杂，而且立体效果不好，运用MATLAB绘制图形简单而且可以实现图像的可视化。运用MATLAB绘制三维图像，实现对球面的自动绘制，熟练掌握绘制球面的绘图命令。对球面进行相关的计算，例如体积、表面积。 二、设计要求 1、运用MATLAB等工具。 2、对球相关的计算。 3、按照格式要求写出3000字文档。 三、参考文献 [1]曹弋.MATLAB教程及实训[M].北京：机械工业出版社，2010，8. [2]王正林，刘明.精通MATLAB7[M].大陆：电子工业出版社，2006. [3]高尚华.数学分析第三版[M].北京：高等教育出版社，2008，4. 计划答辩时间：2011 年 6 月 12日 工作任务与工作量要求：查阅文献资料不少于3篇，课程设计报告1篇不少于3000字 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 MATLAB课程设计 设计题目：应用图像处理 班级： 学号： 姓名： 指导老师： 设计时间：2013年4月8号-4月14号 摘要 21世纪是一个充满信息的时代，图像作为人类感知世界的视觉基础，是人类获取信息、表达信息和传递信息的重要手段。图像处理，是用计算机对图像进行分析，以达到所需结果的技术。又称影像处理。基本内容图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组，该数组的元素称为像素，其值为一整数，称为灰度值。图像处理技术的主要内容包括图像压缩，增强和复原，匹配、描述和识别3个部分。常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。图像处理一般指数字图像处理。所谓数字图像处理[7]就是利用计算机对图像信息进行加工以满足人的视觉心理或者应用需求的行为。实质上是一段能够被计算机还原显示和输出为一幅图像的数字码。 关键词：DCT变换；图像压缩；真色彩增强；平滑；锐化；直方图均衡； 灰度变换；滤波；M文件的使用 目录 摘要………………………………………………………………I 1 概述……………………………………………………………II 2 课程设计任务及要求...............................III 设计任务 设计要求 3 系统设计原理 (Ⅳ) DCT图像压缩原理 真彩色增强 平滑 锐化 灰度变换（直方图均衡化） 图像滤波 中值滤波器 维纳滤波器 4 程序代码及实验结果与分析 (Ⅵ) DCT图像压缩 程序代码 实验结果 结果分析 真彩色增强 平滑程序代码 实验结果 结果分析 锐化程序代码 实验结果 结果分析 灰度变换（直方图均衡化） 程序代码 实验结果 结果分析 图像滤波 程序代码 实验结果 结果分析 5 收获体会 (Ⅶ) 6 参考文献 (Ⅷ) 概述 计算机仿真期末作业 姓名：吴隐奎 班级：04601 学号：041751 日期：2007-6-15 题目：Floyd 算法实现和分析 内容：用MATLAB 仿真工具实现Floyd 算法，求任意两端间的最短路径。 要求：尽可能用M 函数分别实现算法的关键部分，用M 脚本来进行算法结果验证；分别用以下两个图（用初始距离矩阵表示）进行算法验证： 图一：(0)0 100 100 1.2 9.2 100 0.5100 0 100 5 100 3.1 2100 100 0 100 100 4 1.51.2 5 100 0 6.7 100 1009.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 1000.5 2 1.5 100 100 100 0]W ??????????=???????????? 图二：(0) 0 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.11.5 100 100 0 100 100 4100 1.2 5 100 0 6.7 100100 9.2 100 100 6.7 0 15.6100 100 3.1 4 100 15.6 0W ??????????=???????????? 算法：给定图G 及其边(,)i j 的权,(1,1)i j w i n j n ≤≤≤ ≤ F0：初始化距离矩阵(0)W 和路由矩阵(0)R 。其中： (0)0ij ij ij ij w e E w e E i j ∈??=∞???=? 若（有边） 若（无边） 若(对角线元素) (0)(0)w 0,ij ij j r ?≠∞=?? 若 其它 F1：已求得(-1)k W 和(-1)k R ，依据下面的迭代求()k W 和()k R ()(1)(1)(-1),,,,min(,)k k k k i j i j i k k j w w w w --=+ 一、课程目的 初步学会使用MATLAB软件，掌握MATLAB基本的函数的使 用，熟练MATLAB编程，以便为今后数字信号的处理打下基础。 二、课程内容 实验一 MATLAB语言基础 实验目的：基本掌握 MATLAB 向量、矩阵、数组的生成及其基本运算(区分数组运算和矩阵运算)、常用的数学函数。了解字符串的操作。 实验内容: 1、创建以下矩阵：A为3×4的全 1 矩阵、B为3×3的0矩阵、C 为3×3的单位阵、D为3×3的魔方阵、E由C和D纵向拼接而成、F抽取E的2～5行元素生成、G由F经变形为3×4的矩阵而得、以G为子矩阵用复制函数(repmat)生成6×8的大矩阵H。 源程序： A=ones(3,4)% A为3×4的全 1 矩阵 B=zeros(3)% B为3×3的0矩阵 C=eye(3)% C为3×3的单位阵 D=magic(3)% D为3×3的魔方阵 E=cat(1,C,D)% E由C和D纵向拼接而成 F=E(2:5,:)% F抽取E的2～5行元素生 G=reshape(F,3,4)% G由F经变形为3×4的矩阵而得 H=repmat(G,2,2) %以G为子矩阵用复制函数(repmat)生成6×8的大矩阵H 运行结果： A = 1 1 1 1 1 1 1 1 1 1 1 1 B = 0 0 0 0 0 0 0 0 0 C = 1 0 0 0 1 0 0 0 1 D = 8 1 6 3 5 7 4 9 2 E = 1 0 0 0 1 0 0 0 1 8 1 6 3 5 7 4 9 2 F = 0 1 0 0 0 1 8 1 6 3 5 7 G = 0 3 1 1 0 1 5 6 8 0 0 7 H = 0 3 1 1 0 3 1 1 0 1 5 6 0 1 5 6 8 0 0 7 8 0 0 7 0 3 1 1 0 3 1 1 0 1 5 6 0 1 5 6 8 0 0 7 8 0 0 7 2、（1）用矩阵除法求下列方程组的解 x=[x 1；x 2；x 3]； ?? ? ??-=---=++-=++7 3847523436321321321x x x x x x x x x (2) 求矩阵的秩； (3) 求矩阵的特征值与特征向量； (4) 矩阵的乘幂与开方； (5) 矩阵的指数与对数； (6) 矩阵的提取与翻转。 源程序： a=[6,3,4;-2,5,7;8,-1,-3]%系数矩阵 默认是Dijkstra 算法 是有权的, 我想如果把权都赋1的话, 就相当于没权的了 参数是带权的稀疏矩阵及结点 看看这两个例子(一个有向一个无向), 或许你能找到你想知道的 % Create a directed graph with 6 nodes and 11 edges W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; %这是权 DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W) %有权的有向图 h = view(biograph(DG,[],'ShowWeights','on')) %画图, 这个好玩 % Find shortest path from 1 to 6 [dist,path,pred] = graphshortestpath(DG,1,6) %找顶点1到6的最短路径 % Mark the nodes and edges of the shortest path set(h.Nodes(path),'Color',[1 0.4 0.4]) %上色 edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); set(edges,'LineColor',[1 0 0]) %上色 set(edges,'LineWidth',1.5) %上色 下面是无向图的例子 % % Solving the previous problem for an undirected graph % UG = tril(DG + DG') % h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on')) % % Find the shortest path between node 1 and 6 % [dist,path,pred] = graphshortestpath(UG,1,6,'directed',false) % % Mark the nodes and edges of the shortest path % set(h.Nodes(path),'Color',[1 0.4 0.4]) % fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); % revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID')); % edges = [fowEdges;revEdges]; % set(edges,'LineColor',[1 0 0]) % set(edges,'LineWidth',1.5) clc;close all; clear; load data; % global quyu; quyu = [2,3];%一片区域 z_jl = lxjl(jdxx,lxxh);%计算路线的距离 z = qyxz(jdxx,quyu,z_jl); % 根据节点信息，从z中将y区域的节点和路线选出所有点的信息 hzlx(z); %绘制Z的图像matlab课程设计题目
最短路径的Dijkstra算法及Matlab程序
MATLAB课设报告
MATLAB实验报告-遗传算法解最短路径以及函数最小值问题
Matlab课程设计报告
最短路径算法_matlab程序[1]
基于遗传算法的最短路径问题及其MATLAB实现
matlab课程设计拟定题目
最短路径法射线追踪的MATLAB实现
matlab课程设计题目全
matlab 蚁群算法 机器人路径优化问题
MATLAB课程设计任务书
蚁群算法最短路径通用Matlab程序(附图)
matlab习题(课程设计)
MATLAB课程设计
MATLAB课程设计-图像处理完整版
最短路径matlab计算机仿真
MATLAB课程设计
MATLAB解决最短路径问题代码
相关主题
文本预览