下载

1下载券

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 算法论文:旅行商问题的求解方法(动态规划法和贪心法)

算法论文:旅行商问题的求解方法(动态规划法和贪心法).doc

算法论文:旅行商问题的求解方法(动态规划法和贪心法)

小耗子在发现
2013-10-02 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《算法论文:旅行商问题的求解方法(动态规划法和贪心法)doc》,可适用于工程科技领域

旅行商问题的求解方法摘要旅行商问题(TSP问题)时是指旅行家要旅行n个城市然后回到出发城市要求各个城市经历且仅经历一次并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题是图问题中最广为人知的问题。本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题其中重点讨论动态规划法和贪心法并给出相应求解程序。关键字:旅行商问题动态规划法贪心法分支限界法引言旅行商问题(TSP)是组合优化问题中典型的NP完全问题是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到这促使人们长期以来不断地探索并积累了大量的算法。归纳起来目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为:最优解算法和近似方法。最优解算法虽然可以得到精确解但计算时间无法忍受因此就产生了各种近似方法这些近似算法虽然可以较快地求得接近最优解的可行解但其接近最优解的程度不能令人满意。但限于所学知识和时间限制本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法并对蛮力法做简单介绍用以比较。正文蛮力法蛮力法的设计思想蛮力法所依赖的基本技术是扫描技术即采用一定的策略将待求解问题的所有元素一次处理一次从而找出问题的解。一次处理所有元素的是蛮力法的关键为了避免陷入重复试探应保证处理过的元素不再被处理。在基本的数据结构中一次处理每个元素的方法是遍历。算法讨论用蛮力法解决TSP问题可以找出所有可能的旅行路线从中选取路径长度最短的简单回路。如对于图我们求解过程如下:()路径:>>>>路径长度:()路径:>>>>路径长度:()路径:>>>>路径长度:()路径:>>>>路径长度:()路径:>>>>路径长度:()路径:>>>>路径长度:从中我们可以知道路径()和()路径长度最短。我们还应注意到图中有对不同的路径对每对路径来说不同只是路径的方向因此可以将这个数量减半则可能的解有(n)!个。这是一个非常大的数随着n的增长TSP问题的可能解也在迅速增长。如:一个城市的TSP问题有大约有,个可能解。一个城市的TSP问题有大约有,,,,,个可能解。一个城市的TSP问题有大约个可能解而一个行星上也只有升水。因此我们可以知道用蛮力法求解TSP问题只能解决问题规模很小的实例。动态规划法动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题每个子问题对应决策过程的一个阶段一般来说子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中将子问题的解求解一次并填入表中当需要再次求解此子问题时可以通过查表获得该子问题的解而不用再次求解从而避免了大量重复计算。TSP问题的动态规划函数假设从顶点i出发令表示从顶点i出发经过中各个顶点一次且仅一次最后回到出发点i的最短路径长度开始时于是TSP问题的动态规划函数为:算法讨论()for(i=i<Ni)初始化第列di=ci()for(j=j<j)for(i=i<ni)依次进行第i次迭代if(子集Vj中不包含i)对Vj中的每个元素k计算Vm==Vjkdij=min(cikdkm)()对V中的每一个元素k计算Vm==Vkd=min(ckdkm)()输出最短路径长度d时间复杂性和蛮力法相比动态规划法求解TSP问题把原来的时间复杂性是O(n!)的排列问题转化为组合问题从而降低了算法的时间复杂性但它仍需要指数时间。贪心法贪心法的设计思想贪心法在解决问题的策略上目光短浅只根据当前已有的信息就做出选择而且一旦做出了选择不管将来有什么结果这个选择都不会改变。换言之贪心法并不是从整体最优考虑它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解但通常能获得近似最优解。最近邻点策略求解TSP问题贪心法求解TSP问题的贪心策略是显然的至少有两种贪心策略是合理的:最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。最近邻点策略:从任意城市出发每次在没有到过的城市中选择距离已选择的城市中最近的一个直到经过了所有的城市最后回到出发城市。算法讨论.P={}.V=V{u}u=u从顶点u出发.循环直到集合P中包含n条边查找与顶点u邻接的最小代价边(u,v)并且v属于集合VP=P{(u,v)}V=V{v}u=v从顶点v出发继续求解时间复杂性但需注意用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。当图中顶点个数较多并且各边的代价值分布比较均匀时最近邻点策略可以给出较好的近似解不过这个近似解以何种程度近似于最优解却难以保证。分支限界法分支限界法的设计思想假设求解最大化问题解向量为其中的取值范围为某个有穷集合。在使用分支限界法搜索问题的解空间树时首先根据限界函数估算目标函数的界down,up然后从根结点出发扩展根结点的个孩子结点从而构成分量的种可能的取值方式。对这个孩子结点分别估算可能取得的目标函数值其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于也就是部分解应满足:本文本欲详细讨论该算法但无奈在编程问题中尚有问题有待解决时间所限不得已放弃。本人编程过程中所用算法思想与老师课上所教略有不同在寻找下界时是首先把每个结点所能到达的各个结点及其可能的路径算出来并添加到PT表中但最后不知是何原因在还有一个城市尚未加入时PT表的添加出现了问题思忖良久仍未解决时间所限迫不得已留待以后有时间再另行研究本文就只给出动态规划法和贪心法的具体求解过程。结论本文主要重点讨论了动态规划法和贪心法求解TSP问题算法并附录给出了相应程序。动态规划法思想动态规划法中对于顶点元素生成的子集本文中用字符串形式存储然后再用递归方法按照子集中元素个数从小到大开始赋值。因为后面元素个数较多的子集与前面比其元素个数少的子集间有一定对应关系所以用递归方式可以简便很多。个人觉得这算本文的一大特色。另在计算dij=min(cikdkj)时获得dkj的过程比较困难运用字符串后我们就可以首先找到指定字符然后去掉该字符返回剩余字符串在与V逐个比较找到与其相等的V中元素对应下标此下标即为j具体求解过程可参考附录源程序有详细说明。在求解最佳路径所经过城市顺序时本文是通过边查找dij边记录路径的这样可以省掉很多麻烦另路径也是采用字符串形式的数组数组规模与存储城市间距离的c数组相同由于很多元素均不需赋值这样做可能会浪费内存空间但是目前还没找到更好地求解方法。贪心法思想贪心法中由于贪心法相对动态规划法要简单很多每次在查找最近城市时所得的顶点均为最后该法最佳路径所经过的城市编号规模相对较小容易确定操作相对简单所以本文用数组V存放最佳路径所经过的城市编号顺序相对来说方便很多。另外本文用path整型数组存放所经路径的长度最后相加即可得最短路径。两者比较动态规划法相对贪心法来说虽然要精确些但代码相对繁杂很多对时间和空间要求很多仅适用于城市数量较小的情况。贪心法虽然比较简单实现起来比较容易但不是很精确当图中顶点个数较多并且各边的代价值分布比较均匀时贪心法可以给出较好的近似解不过这个近似解以何种程度近似于最优解却难以保证。另外动态规划法有一个明显的缺点就是出发城市只能是第个城市(城市从开始编号)若出发城市改变则必须以该城市为第个城市顺序给其他城市编号输入城市间距离。由于若出发城市任意编码的难度大大增加所以最后不得已放弃但这大大地限制了程序的通用性。而对于贪心法本文很好地避免了这个问题一旦城市编号确定可以从任意城市出发这也是本文中贪心法优于动态规划法的一点。优点本文程序优点各个子函数功能分隔很明显没有大量集中在一个函数里面而是分成了几个不同功能的小函数这样程序可阅读性提高。另外程序中有详细注释程序中变量取名都是根据变量的性质和所代表的含义命名的也相应提高了程序的可读性。对于动态规划法城市个数可以在算法时间允许的范围内任意于这点来说通用性较好对于贪心法出发城市可以任意城市个数也可以任意通用性较好。建议当城市个数较少时用动态规划法求出最优解当城市个数较多并且各边的代价值分布比较均匀时贪心法可以给出较好的近似解。参考文献()《计算机算法分析与设计》第二版王晓东编著电子工业出版社()Java语言与面向对象程序设计(第版)印旻、王行言编著清华大学出版社()求解TSP算法周康、强小利、同小军、许进计算机工程与应用附录动态规划法源代码packageexpimportjavautilScannerpublicclassTSPDynamic{StringV顶点生成的子集这里把每一个子集用一个字符串表示intc顶点间距离intd存放迭代结果intN城市个数Stringpath用于存放每种选择下经过的城市staticintIFINITE=无穷大距离表示城市自己到达自己时距离无穷大不作为考虑因素构造函数publicTSPDynamic(){initialC()initialV()}初始化数组c即顶点间距离publicvoidinitialC(){Scannerin=newScanner(Systemin)Systemoutprintln("请输入城市个数:(注意根据实际情况城市个数不可小于!)")N=innextInt()if(N<=){Systemoutprintln("不符合要求请认真核对!")Systemexit()输入错误结束!}Systemoutprintln("请输入城市相邻城市间距离(城市从开始编号且出发城市为第个城市!):")c=newintNN为c分配空间for(inti=i<Ni)for(intj=j<Nj){cij=innextInt()输入时按城市编号从小到大如若两城市间没有公路相连则距离为无穷大。本城市与本城市间距离也为无穷大。}}初始化顶点生成的子集的对外调用函数publicvoidinitialV(){V=newString(int)Mathpow(,N)为V分配空间initialV(,)}具体的初始化顶点生成的子集本程序使用递归调用方法初始化V并按照数字大小顺序排序。。另子集使用字符型形式存放的我们是按照子集中元素个数从小到大逐个添加的后面的子集是前面对应子集加上一个元素组成的故用递归publicvoidinitialV(intm,intlen){m代表下一个即将初始化的V数组的元素的下标len是最后一个初始化的元素的长度if(m>(int)Mathpow(,N))return如果全部顶点已初始化完成则返回。if(m==)Vm=""初始化出发顶点即Velse{inti=mwhile(i>=Vilength()==len)找与最后一个初始化的Vm子集内元素个数相同的集合把指针i指向满足条件的集合ii把指针i指向满足条件的第一个集合while(i<m){intch用于表示下一个即将加入子集的数字if(i==)ch=如果i指向V中第一个元素else{StringchStr=""VicharAt(Vilength())找出Vi中最后一个数字ch=IntegerparseInt(chStr)转换成整型}比ch大而又比N(因为这里顶点是从开始的)小的数字应该加在子集中while(ch<N)Vm=Vi(ch)i对已存在的自己逐个扫描添加}}initialV(m,Vmlength())递归调用}判断自己Vj中是否存在指定元素即行号ibooleanexclude(inti,intj){Stringstr=""i把i转换成字符串if(Vjcontains(str)){Systemoutprintln(i"i")returnfalse如若存在则返回falseelsereturntrue}获得子集Vj中除指定元素k外的元素用字符串形式表示publicStringgetSubString(intk,intj){if(Vjlength()==)return""如果子集中只有一个元素则返回空串else{if(k==)returnVjsubstring(,Vjlength())如果k是第一个元素则返回其后面的元素elseif(k==Vjlength())returnVjsubstring(,Vjlength())如果k是最后一个元素则返回其前面的元素elsereturn(Vjsubstring(,k)Vjsubstring(k,Vjlength()))返回除k外的元素}}找出V中与str相同元素的下标号,即找出上一个子集publicintstringEqual(Stringstr){if(strequals(""))returninti=while(i<Vlength){if(Viequals(str))returnii}return如若没找到则返回错误符号}求最小距离publicintmin(inti,intj){intk=用于记录Vj中元素个数StringvStr=""VjcharAt(k)铭记VjcharAt(k)得到的是字符型转换成整形后是字母对应的ASC码!!!!intv=IntegerparseInt(vStr)把位置k处的字符转换成整形Stringstr=getSubString(k,j)获得Vj中除位置k处外的字符串Systemoutprintln("min"strstringEqual(str)v)if(stringEqual(str)==)Systemexit()intmin=civdvstringEqual(str)先把最小的距离赋值给从Vj中第一个顶点出发的距离Systemoutprintln(min)stringEqual(str)表示返回与上面获得的字符串相同的V中元素的下标即找上一个子集pathij=pathvstringEqual(str)ik寻找最小距离while(k<Vjlength()){vStr=""VjcharAt(k)v=IntegerparseInt(vStr)str=getSubString(k,j)if(min>civdvstringEqual(str)){min=civdvstringEqual(str)pathij=pathvstringEqual(str)i}k}Vjsubstring(beginIndex,endIndex)Systemoutprintln(pathij)returnmin返回最小值}处理函数publicvoiddynamic(){d=newintN(int)Mathpow(,N)分配空间path=newStringN(int)Mathpow(,N)for(inti=i<Ni){初始化第一列di=cipathi=""i初始化第一个元素即为出发城市顶点Systemoutprint(di"")}初始化后面的元素intj=for(j<(int)Mathpow(,N)j)for(inti=i<Ni){if(exclude(i,j))判断V子集中是否包含当前顶点即Vj中是否包含i{Systemoutprintln("done!"i""j)dij=min(i,j)寻找最小距离}}dj=min(,j)初始化组后一列}输出中间结果各个数组用于调试程序publicvoidprint(){for(inti=i<(int)Mathpow(,N)i)Systemoutprint(Vi"")for(inti=i<clength)Systemoutprintln()for(inti=i<Ni){for(intj=j<Nj)Systemoutprint(cij"")Systemoutprintln()}for(inti=i<Ni){for(intj=j<(int)Mathpow(,N)j)Systemoutprint(dij"")Systemoutprintln()}}输出最短路径publicvoidprintShortestPath(){输出所经城市Systemoutprint("经过城市:")Stringstr=path(int)Mathpow(,N)Systemoutprintln(str)Systemoutprint(strcharAt(strlength()))for(inti=strlength()i>=i){Systemoutprint(">"strcharAt(i))}Systemoutprintln("会有最短路径")Systemoutprintln("最短路径为:"d(int)Mathpow(,N))}主函数publicstaticvoidmain(Stringargs){TSPDynamicTSP=newTSPDynamic()TSPdynamic()求最短路径TSPprint()TSPprintShortestPath()输出最短路径}}测试数据**结果()()()()贪心法源代码packageexpimportjavautilScannerpublicclassTSPGreedNode{intV存放旅行所经过的城市顶点intc存放每两座城市间的距离注意:若路径不存在或同一城市间距离为无穷大intpath存放旅行所经过的每两座城市间的距离intN城市个数intshortestPath表示最短路径intu出发城市编号staticintIFINITE=无穷大距离表示城市自己到达自己时距离无穷大不作为考虑因素publicTSPGreedNode(){initialC()}得到最短路径publicintgetShortestPath(){for(inti=i<Ni){shortestPath=pathi}returnshortestPath}初始化数组c即顶点间距离publicvoidinitialC(){Scannerin=newScanner(Systemin)Systemoutprintln("请输入城市个数:(注意根据实际情况城市个数不可小于!)")N=innextInt()if(N<=){Systemoutprintln("不符合要求请认真核对!")Systemexit()输入错误结束!}Systemoutprintln("请输入城市相邻城市间距离(城市从开始编号且出发城市为第个城市!):")c=newintNN为c分配空间for(inti=i<Ni)for(intj=j<Nj){cij=innextInt()输入时按城市编号从小到大如若两城市间没有公路相连则距离为无穷大。本城市与本城市间距离也为无穷大。}}publicvoidtspGreedNode(){Scannerin=newScanner(Systemin)Systemoutprintln("请输入出发城市编号(注意城市从开始编号请按照输入城市间距离即初始化c时顺序计算):")u=innextInt()V=newintNpath=newintNintk=Vk=uwhile(k<N){intmin=IFINITEkfor(inti=i<Ni){intmark=for(intj=j<kj)if(Vj==i)mark=if(mark==cVki<min){min=cVkiVk=i}}pathk=min}Vk=upathk=cVkVk}输出最短路径下所经城市两城市间距离和最短路径publicvoidprint(){shortestPath=Systemoutprintln("按照下列方式旅游会使所走路程最短:")for(inti=i<Ni){Systemoutprintln("从"Vi">"Vi",所经路程为:"pathi)shortestPath=pathi}Systemoutprintln("总路程为:"shortestPath)}***paramargs*publicstaticvoidmain(Stringargs){TODOAutogeneratedmethodstubTSPGreedNodegd=newTSPGreedNode()gdtspGreedNode()gdprint()}}**结果()()()()unknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknown

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/15

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利