实验4 动态规划算法设计

1、算法分析与设计实验报告实验四动态规划算法设计姓名 xxxxxxx 学号 xxxxxxxx 班级 xxxxxxxx时间：xxxxxx地点：xxxx同组人：无指导教师：xxxxxx实验目的掌握动态规划法算法设计的一般原理和方法。理解动态规划向前处理和向后处理的思想，掌握递推公式的求解方法。掌握多段图、每对结点之间最短路径的计算算法。能用动态规划法设计算法求解一般问题。实验内容设计求解多段图问题的动态规划程序，上机调试通过。设计求解每对结点之间最短路径问题的动态规划程序，上机调试通过。准备几个多段图和几个道路交通图的数据。输入求解多段图问题的动态规划程序，并用准备的数据调试通过。输入每对结点之间最短

2、路径问题的动态规划程序，并用准备的数据调试通过。实验环境硬件：Intel(R) Pentium(R) CPU RAM:4G软件：Myeclipse2013编程语言：Java实验前准备1、算法设计:一、多段图问题与其向前处理法V2VI9732V3V4V5331011411552一个5段图的例子FGRAPH(E, k, n, P) 多段图的向前处理算法/real COST(n), integer D(n-1),P(k), r, j, k, nCOST(n)0forlineprocedure4设r是一个这样的结点，j,rE且使取最小值。5COST (j)c(j, r)+COST(r)6D(j) r7

3、repeat8P(1) 1;P(k) n9for j2 to k-1 do10P(j) D(P(j-1)11repeat12endFGRAPHjnT to 1 by -1 doc(j, r)+COST(r)123456789101112二、求每对结点之间最短路径长度问题的算法lineprocedure ALL-PATHS(COST, A, n) integer i, j, k, n; real COST(n, n), A(n, n) for i1 to n dofor j 1 to n doA(i,j) COST(i,j) repeat repeat for k1 to n do for i

4、1 to n do for j 1 to n doA k(i,j) minA k-1(i,j), A k-1(i,k)+A k-1(k,j) repeat repeat repeat13 endALL-PATHS1、程序设计：见附1实验步骤1、准备实验数据。准备几个多段图和几个道路交通图的数据。多段图的实验数据和道路交通图的数据均可利用程序生成 (ReadEdgeData.java 的 randMultGraph 和 radomDirectedGraph)；其中多段图的生成原则是n个结点分为k段，且每段大约为4到5个结点， 第一个和最后一个结点要和相邻段所有结点相连，中间段的结点与相邻段的结点

5、 至少要有一个结点相邻，每条边的成本随机生成。道路交通图至少则是生成有图的方式，n个结点有(n*n)*4/5使边数不至 于多，也不至于少。将生成的边以数对的形式存于文本文件中，如下图，其中第一行分别为结点 数和边数。剩下的若干行表示每条表的两个结点和成本。在需要的时间通过读取 文本文件来获取数据。Mu tGraohLtxt -记事本回2文件旧宏辑(E)格式。查者凹帮助(H)24 645 61 2 11 4 101 3 9 TOC o 1-5 h z 6 78 32 7 112 10 59 109 98 84 10 64 7 24 11 119 78 69 108 515 212 67 14 1

6、116 114 312 98 15 28 13 616 1116 313 12、多段图问题的动态规划程序根据算法设计的多段图向前处理法的sparks语言，写出相应的java程序，并调试验证通过。其中边是以邻接表的形式表现出来更方便显示点之间的邻接关系。/*=1 j)(int minCost=Graph.MAXCOSTint r=1LinkedLi costList= G.getCostList()jfor (Edge edge : costList) /找到U j 之后的一个点 r， 使 edge.cost+COSTr取最小值，并将最小值赋给minCostint v=edge.v /edge.

7、cost 代表 j 至U v 的权值 if(vj &edge.cost+COSTvminCost)=v rminC=dtge . cost+COST vCOT=minCost 将从j到最后一个结点的最短路径的权值赋给COSTj D=r1=1 /第一个结点?k=n /最后一个结点for (int j=2 jk j+) / /找路径上的第j个结点j=DPj 1将课本上的实验数据进行计算得到结果如下，其结果与书的最短路径一致。3、最短路径问题的动态规划程序根据最短路径问题的动态规划程序算法的sparks语言写出对应的java程序， 并调试验证通过，对比相同数据下的用求单源点最短路径算法求解每对结点之

8、间最短路径得出的结果相同/*计算每对结点之间的最短路径长度param COST r个结点的邻接矩阵param A Aij是从i到j的最短路径的成本param n结点个数*/public static void ALL_PATHS(int COST, int A, int n) for (int i = 0 i = n i+) /将 COSTij 复制到 Aij中 for (int j = 0 j = n j+) i j = COSTijfor (int k = 1 k = n k+) /对最高下标为k的结点的路径 for (int i = 1 i = n i+) /对于所有可能的结点对for

9、(int j = 1 j (Aik + Akj)ij = Aik + Akj 输出结点如下图，且结果与实验三得到的单源最短路径一致JiJ| AllPaths.java 风 JZ1 Fgraph.java | JT Rea d E d g eData J a va| JT| Graph.java TOC o 1-5 h z -*/J .L-_l l_ _1l_1for (int j = 0； j = n; j+) Aij = COSTij;7172_ for (int k = 1; k = n; k+) /对最高下标为k的结点的路径Problems JavadocI 凰 Declaration

10、l莽 Project Migration 田Console 3terminatedAllPaths Java Application C:UsersXTAppDataLocalMyEclipse Professionslbinarycom.sunava.jdk.win32.x86_64_1.6.0.u43binjavaw.exe (0123456789101012995001000124724004311364682730333227036131541CO314474114042201131500545647430340051126271462250205251575635113260CO39

11、108414439144g000297924g224420g3235030101351644464234380/*计算后所有对结点的最短路径* * * * /01234567891010120851597642401979148610331516017131524173144781401217111451151062060201451965116210095747562281060111198891511318120679242522262037322502844、（附加3 ）最短路径问题的动态规划的最短路径根据短路径问题的动态规划程序，添加一个AllParent数组用来记录每个结点的最短路径

12、的父结点，最后通过入栈和出栈的方式输出每个结点的路径/*计算每对结点之间的最短路径长度，并将最短路径记录下来param COSTparam Aparam nparam AllParent*/public static void ALL_PATHS(int COST, int A, int n, int AllParent) for (int i = 0 i = n i+) /将 COSTij复制到 Aij中，将将 所有结点的父结点设为自身for (int j = 0 j = n j+) i j = COSTij AllParentij = ifor (int k = 1 k = n k+) /

13、对最高下标为k的结点的路径 for (int i = 1 i = n i+) /对于所有可能的结点对for (int j = 1 j (Aik + Akj) ij = Aik + AkjAllParentij = k 屈 疫筮L3 彝, Q 必,4,密何.5 21 AllPaths.javaFgraph.javaI J7 ReadEdgeData.java| JJ Graph.java W |for (int j = 0； j = n； j+) | SunFaFenXi/src/test/exp4/Graph.java Aij = COSTij; 1：7172, for (int k = 1;

14、 k AllPaths Java Application C:UsersXTAppDataLocaKMyEclipse Professionalbinarycom.sun.java.jdk.win32.x86 64 1.5.0.u43binjavaw.exe (2014-5-恿 Problems I Javadoc 凰 Declaration Project Migration Console 洛651162100957475622810601111988915113181206792425222620373225028101216461610370/*到其它 点 的单源最路径* * /1=2

15、:11=2=10=3：201=2=10=4:81=5:51=2=7=6:151=2=7:91=2=10=8:71=5=9:61=2=10:4/*2 到其它点的单源最路径* * j2=1。=1：42=10=3:192=1。=4:72=10=5:92=7=6:142=7:8实验结果及其分析1、多段图的向前处理法实验中取100000次运行的数据结点数n1224364860728496108120100000次运行所用时间576399147199324391438494578题该问题根据课上的理论分析知为时间复杂度为O(n+e)，其中e为边数，似 于线性与图有所区别这可以是由于数据量太少和计算和复杂造

16、成的噪声干扰, 但总体来看其趋势仍接近线性;2、最短路径问题的动态规划程序最短路径问题的动态规划程序实现结果n102030405060708090100所用时间4223192825084594778212126175982460633810实验结果通过添加趋势线可能符合理论分析结果;它与贪心方法的时间复杂度一 样，但成本上比贪心方法弱些且计算简单，容易理解。附加3是对上题添加路径，只是在计算过程中记录每个结点的上个结点，以 树的形式保存下来，再通过先入栈再出栈的方式将每对结点的路径输出出来。4、总结动态规划是将一个问题的活动分为若干个阶段，而且每个阶段在任一阶段后 的行为都仅信赖于i阶段的过程

17、状态它指出无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最伟决策序列，这便是最优性原理。动态规划和贪心算法一样都是求最短路径问题,通过最优性原理求僻出最优 策略，可以快速准确的救出多段图问题和每对结点的最短路径问附：源代码1、多段图的向前处理法 Fgraph.javaimport java.io.Fileimport java.util.LinkedListpublic class Fgraph (/*多段图的向前处理算法* param args*/public static void main(String args) (int Z = 10/数据个数

18、int tp = 0 /文件的初始编号long D = new long Z2 /记录数据量和运行时间的数组String surDi = E:我的文档大三下算法分析与设计实验实验4动 态规划算法设计datafor (int t = 0 t 10 t+) String fileNam= MultGraph + t + .txtFile su= new File(surDir, fileName)Graph = null/从文件中读取图的有关信息if (G = ReadEdgeData.readEdges(sur, true) = null) Sys .emit. println (读取错误，请检

19、查！)return).GnitCostList()int k = 5 + t / 段数int n = G.n / 结点数int P = new intk + 1/循环计算MM次计算其运行时间long time = 0, T1, T2int MM = 100000T= System.currentTimeMillis()for (int j = 0 j MM j+) FGR (P3, k, n, P)T= System.currentTimeMillis() tim= T2T1t0 = n /将结点和对应的计算时间加入数组便于输出t1 = time/*for (int i = 1; i P.le

20、ngth; i+) ( System.out.print(Pi + t); System.out.println();*/ /输出结点和对应的运行时间for (int k = 0 k Z k+) Syst.mut.print(Dk0 + t) Syste.nout. println ()for (int k = 0 k Z k+) Syst.mut.print(Dk1 + t) Syste.nout. println ()/* 火输入是按段的顺序给结点编号的，G表示图，并且用邻接表的访求来表示边集，最后得 到的是最小成本路径P*paramG*图*paramk*段图*paramn*个结点*par

21、amP*最小成本路径*/public static void FGRAPH(Graph G, int k, int n, int P) int COST = new int n + 1 /用来记录从j到最后一个结点的最小权值int D = new int n / Dj用来表示j到最后一个结点最短路径上的后续 一个结点for (int j = n 1 j = 1 j)int minCost = Graph.MAXCOSTint r = 1LinkedLi costList = G.getCostList()jfor (Edge edge : costList) / 找到1j 之后的一个点 r，

22、使 edge.cost+COSTr取最小值，并将最小值赋给minCostint v = edge . v / edge.cost 代表 j 至U v 的权值if (v j & edge.cost + COSTv minCost) =rvminCo=tedge.cost + COSTvCOT = minCost /将从j到最后一个结点的最短路径的权值赋给 COSTj) = r1 = 1 /第一个结点?k = n /最后一个结点for (int j = 2 j k j+) /找路径上的第j个结点p = DPj 12、最短路径问题AllPaths.javaimport java.io.File pu

23、blic class AllPaths /*每对结点之前的最短路径长度 * param args*/ public static void main(String args) int Z = 10/数据个数int tp = 21 /文件的初始编号long D = new long Z2 /记录数据量和运行时间的数组String surDi = E:我的文档大三下算法分析与设计实验实验4动 态规划算法设计datafor (int t = 0 t 10 t+) String fileName= Edges+(tp+t)+.txt File sur= new File(surDir, fileNam

24、e) Graph G= null/从文件中读取图的有关信息if (G = ReadEdgeData.readEdges(sur, true) = null) Syst .mut .println (读取错误，请检查！) returnint n = G.getN()int COST = G.getCost() /*for (int i = 0; i = n; i+) ( for (int j = 0; j = n; j+) (if (COSTij = Graph.MAXCOST) ( System.out.print(8t); else ( System.out.print(COSTij + t

25、);System.out.println();*/int A = new intn + 1n + 1int AllParent=new intn+1n+1/*形如计mmmmmmmm*/*ALL_PATHS(COST, A, n);*/循环计算MM次计算其运行时间 long time = 0, T1, T2 int MM = 10000T1= System.currentTimeMillis()for (int j = 0 j MM j+) ALL_PAT(COST, A, n,AllParent)T2= System.currentTimeMillis ()time= T2T1北0 = n /

26、将结点和对应的计算时间加入数组便于输出 北1 = time/*计算结束*/System.out.println(/*计算后所有对结点的最短路径 */);/*for (int i = 0; i = n; i+) (for (int j = 0; j = n; j+) (if (Aij = Graph.MAXCOST) (System.out.print(8t); else (System.out.print(Aij + t);System.out.println();displayPath(AllParent,A,n);*/输出结点和对应的运行时间for (int k = 0 k Z k+) S

27、yscteunt .print (D k0 + t)Sys .emit. println ()for (int k = 0 k Z k+) Syscout.print(Dk1 + t) Sys .emit. println ()/*计算每对结点之间的最短路径长度param COST n个结点的邻接矩阵param A Aij是从i到j的最短路径的成本param n结点个数*/public static void ALL_PATHS(int COST, int A, int n) for (int i = 0 i = n i+) /将 COSTij 复制到 Aij中 for (int j = 0

28、j = n j+) i j = COSTijfor (int k = 1 k = n k+) /对最高下标为k的结点的路径 for (int i = 1 i = n i+) /对于所有可能的结点对for (int j = 1 j (Aik + Akj)ij = Aik + Akj /*计算每对结点之间的最短路径长度，并将最短路径记录下来param COSTparam Aparam nparam AllParent*/public static void ALL_PATHS(int COST, int A, int n, int AllParent) for (int i = 0 i = n i

29、+) /将 COSTij复制到 Aij中，将将 所有结点的父结点设为自身for (int j = 0 j = n j+) i j = COSTijAllPar ri j = ifor (int k = 1 k = n k+) /对最高下标为k的结点的路径 for (int i = 1 i = n i+) /对于所有可能的结点对for (int j = 1 j (Aik + Akj) ij = Aik + AkjAllPa i j = k/*用来输出单源点路径param vparam parentparam DISTparam n*/public static void displayPath(

30、int v, int parent, int DIST, int n) int stack = new intnfor (int i = 1 i 1) /依次出栈并输出 Sysc(euit .print (stack top) if (top 0) Sy .bent .print (=)topif (DIST i Graph.MAXCOST) Sysc(euit .println (: + DIST i) else Sys count. println (:Infinity)/*火用来输出所有点的最短路径param AllParentparam ALLDISTparam n*/public s

31、tatic void displayPath( int AllParent, int ALLDIST, int n)for(int i=1 i=n i+)Syst.mut.println(/*+i+ 到其它点的单源最路径 */)displayPa(h,AllParenti,ALLDISTi,n)3、图和边类Graph.javapackage test.exp4 import java.util.LinkedList public class Graph int n 点的个数 int m 边的个数 Edg edge /m=edge.length+1，边从 1 开始到U m 止 int costL

32、inkedLis costList public LinkedList getCostList () return costList public void setCostList(LinkedList costList) this.costList = costListboolean isDirected=falsepublic static int MAXCOST = Integer .MAX_VALUE /表示无穷大 static int MINCOST = Integer.MIN_VALUE /表示无穷大 public Graph()public Graph(int n,int m,E

33、dge edge,boolean isDirected) this .m=mthis .n=nthis.edge=edgethis.isDirected=isDirectedthis.initCost()public Graph (int n,int m,Edge edge)(this.m=mthis .n=nthis.edge=edgeisDirecte=falsethis.initCost ()/*初始化邻接矩阵*勺将COST0j和COSTi0设为列编号和行编号COSTii将 0T连通则将COSTij设为无穷大 */public void initCost()int COST = new

34、intn + 1n + 1for(int j=0 j=n j+)CO0j=jfor (int i = 1 i = n i+) /将所有边设为无穷大 CO i0=ifor (int j = 1 j = n j+) if(i=j)CDSj=0elseCDSj=MAXCOSTfor (int k = 1 k edge. length k+) /为邻接矩阵赋初值 CO edgek.uedgek.v = edgek.costif (! this . isDirected) /当为无向图时，只赋一边 CO edgek.vedgek.u = edgek.costthis.cost=COSTpublic vo

35、id initCostList()costLis=new LinkedListn+1for(int i=0 icostList.length i+) costLii=new LinkedList()for(int i=1 iedge.length i+) int u=edgei.u int v=edgei.v int cost=edgei.costEdge e=new Edge(u,v,cost) Edge e=new Edge(v,u,cost) costLi U.add(edl) costLiV.add(ed2) public int getN() return npublic void

36、setN(int n) this.n = n public int getM () return m public void setM(int m) this.m = m public Edge getEdge () return edge public void setEdge(Edge edge) this.edge = edge public int getCost () return cost public void setCost (int cost) this.cost = cost public boolean isDirected () return isDirected pu

37、blic void setDirected(boolean isDirected) this.isDirected = isDirected /*边类* author XTI*/class Edge int uint vint costpublic Edge()public Edge(int u,int v,int cost)this .u=uthis .v=v,4、图的生成与读取ReadEdgeData.javapackage test.exp4 import java.io.BufferedReader import java.io.BufferedWriter import java.i

38、o.Fileimport java.io.FileReader import java.io.FileWriter import java.io.IOException import java.util.LinkedList class ReadEdgeData/*isDirected为true时表示读取有向边param surparam isDirectedreturn Graph */public static Graph readEdges(File sur,boolean isDirected) File dat=surif(! date.exists()|!date.isFile()

39、Syst .mut .println (文件不存在或有误，请检查！) return nullFileReader inReadertry(inRead=new FileReader (date) /相对于项目目录，仓4建一个文件字符读 取流，和文件接上catch (lOException e)(Syst.mut.println(File cant be found or File creates error.)return nullBufferedReader inStrea=new BufferedReader( inReader)/缓存输入流String str /每次读取一行临时存入在此

40、Strin strAry /将str分割成字符串存入的数组int n=0 存放结点数int m=0 /存放边数Edg edge=nullGraph grap=nulltry if(str=inStream.readLine()!=null)str =str.split(s|t)=Integer.parseInt(strAry0)=mteger.parseInt(strAry1)e =new Edgem+1 int i=1while(str=inStream.readLine()!=null&i=m)str=syr.split(s|t)Edge=new Edge ().u=Integer.par

41、seInt(strAry 0).v=Integer.parseInt(strAry1).(e(dst=Integer . parseInt (strAry 2 )etg=ed+ igr =new Graph(n,m,edge,isDirected)inStr .aarLose ()inRea .eclose () catch (IOException e) / TODO Auto-generated catch block.printStackTrace()return graph /*火读取无向边param surreturn*/public static Graph readEdges(F

42、ile sur)(return readEdges(sur,false) public static Graph readEdges(String sur)(File surFil=new File(sur)return readEdges(surFile,false) /*火读取边param surreturn*/public static Graph readEdges(String sur,boolean isDirected)File surFil=new File(sur)return readEdges(surFile,isDirected) public static File

43、writeEdges(String destString,Graph g)File des=nulltry des= new File(destString)return writeEdges(dest, g) catch (Exception e) / TODO Auto-generated catch block.printStackTrace ()return null public static File writeEdges(File dest,Graph g)FileWriter outWritertry(outWrit =new FileWriter (dest) /相对于项 目

44、目录，创建一个文件字符 读取流，和文件接上catch (lOException e)(Syst.mut.println(File cant be found or File creates error.)return nullBufferedWriter outStrea=new BufferedWriter(outWriter)/缓存输入流try int n=g.n,m=g.moutStre .mrite(g.n+ +g.m+rn) /向文件中写入点和边数for(int i=1 in*n*(n 1)/2)/m大于n个结点所能连接的边的无向边的个数Syst .mut .println (边的条

45、数过大)return nullGraph =new Graph ()gsetN (n)gsetM (m)LinkedLis le=new LinkedList()for (int i=1 i=n i+) / /将所可能的n*n*(n-1)/2条边放入链表for(int j=i+1 j=n j+)Edg =new Edge().u=i.v=j.laeid (e)Edg ge=new Edgem+1for(int i=1 in*(n 1) / /m大于n个结点所能连接的边的有向边的个数Syst .mut .println (边的条数过大)return nullGraph =new Graph ()

46、gsetN (n)gsetM (m)LinkedLis le=new LinkedList()for (int i=1 i=n i+) / /将所可能的n*n*(n-1)/2条边放入链表for(int j=1 j=n j+) if(i!=j)Edg =new Edge().u=i.v=j.laeid (e)Edg ge=new Edgem+1for(int i=1 i=m i+)int s=le.size()int r=(int)(Math. random()*s) /在链表中随机取一条边并删除 Edge=le . remove (r)int eCost=(int)(Math.random()*(maxCost minCost)+minCost) .eost=eCosti=egsetEdge (ge)return g/*随机生成一个多段图，n个结点顺序编号，1为起点n为终点，共k段*param n结点数*param k分段数* param minCost 边的最大值*param maxCost 边的最小值*/public static Graph randMultGraph(int n,int k,int minCost,int maxCost)if(n=k)Syst .mut .println (分段数