《现代优化技术-靳志宏》du-现代优化技术

《《现代优化技术-靳志宏》du-现代优化技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、现代优化技术期末作业交通运输规划与管理杜剑1120140359作业1:Dijkstra最短路径算法一Matlab实现问题描述Dijkstra最短路算法用于寻找路网中两点间权数最小的路径，最短路问题的实际应用包括：设备更新、工厂布局、运输路径选择、线路安排等。Matlab是处理矩阵运算的有效工具，此处采用Matlab进行求解。Matlab编码a)数值输入与参数设计：输入路网矩阵G,计算路网中节点数N=size(G,l)。设置vl为临时标号阵列，vO为永久标号阵列，当某节点转为永久编号时其数值由1变为0,节点加入vO。编码：vl=ones(1,N);vO=l;vl(vO)=0;输出为：vO=1vl

2、=01111111b)算法终止条件：算法循环使用while语句，考虑路网不存在最短路、及最多循环N次两个终止情况，设置终止条件，编码如下：ifsize(vOz2)==N,break;end脚匕出while循环ifisinf(Dmin),error,end报错c)forj=l:N%设置两层循环，加两条判断语句。ifvl(j)fori=l:Nifvl(i)==0D(j)=min(D(j),D(i)+G(i,j));endD(j)=min(D(j),G(vO(1)Ai)+G(i,j));endendend外层中ifvl(j),表明j为临时编号点时进入第二层循环，为永久编号点Wj=j+lo内层循环是在

3、j为临吋编号点条件下，确定通过其他各个点到达j点的最短路D(j)oifvl(i)==0D(j)=min(D(j),D(i)+G(i,j))；endD(j)=min(D(j),G(vO(1),i)4-G(i,j));其中，D(j)、D(i)指起点到达ji点的最短路长度；G(i,j)为路网中第i行j列，即由i点到j点的直线距离；vO为永久编号阵列；vl为临时编号阵列,ifvl(i)==0用于判断i点是否为永久编号点。a)fork=1:N,通过求minD(k),确定下一个永久编号点。D=G(vO,:;DT=D;fori=l:Nifvl(i)==0%对匚是否为永久编号做判断DT(i)=inf;end

4、end[Dminid]=min(DT);v0=[vOid];记录最短路径长度，修改永久编号阵列。算例输入参数G,vO(1)如下:G=[inf2infinfinfinf;inf1infinfinf;inf7inf512inf;infinf9inf;inf15infinf3inf8;infinf1inf3inf46；infinf29inf4inf3；infinfinfinf863inf];Workspace0-CommandWindow0NewtoMATLAB?WatchthissmPernororreadGettigfx»£cl«>x9clcG«(inf281infmfinfxM・2xrrf63

5、1infmfinf:xnfinf9infmf15mfinf3inf8・xnfinf1inf3inf46.infin£29inf4inf3;infmfinfinf863infl.気路网lUsizeC^,1):■节QJtvO«l；■乜点出码・vO为倉久vl>on«sU9X>•VH为vl(vO)xO.驚緣去WcSJ&mW,永久HI号值为0・Xg注；while1DSD・forisl:NifvKD^O別定为永久■号$D2(i)«inf;从驚永久Ul号不■ndtndD2:"■处正网SH(Dainid)Bain(D2):ifisxnf(Dam),error*end壮如*Daui为无穷•耒明it处无直8t・箱

6、出运行程序:Name*田DB&2BCwinLCommand卜■■W“disp(DvOl：G=(iiv2urfinfIinfi:inf1:inftclc血"MewCommandWindow0・■b—Inf11A»—D-♦ndDn

7、=0DT(k)=inf;endend[Dminid]=min(DT);ifisinf(Dmin),error,endv0=[vOid];vl(id)=0;ifsize(vO,2)==N,break;endid=0;forj=l:Nifvl(j)fori=l:Nifvl(i)==0D(j)=min(D(j)zD(i)+G(izj));endD(j)=min(D(j),G(vO(1),i)+G(i,j