近似算法.doc

蚁推销员问题近似算法袈莇芄1 插入算法(insertionheuristics)聿插入型算法可按插入规则的不同而分为若干类,其一般思想为:蚇Step1 通过某种插入方式选择插入边(i,j)和插入点k,将k插入i和j之间,形成蒇{⋯,i,k,j,⋯};莁Step2 依次进行直至形成回路解1螁适用范围:对称型△TSP1蒆具体实施中,可以将出发点取遍V中各点而得到多个解,从中选择最好的一个,但此时蒇的时间复杂度增加了n倍1常见的插入型算法有:螂(1)最近插入(nearestinsertion)法艿最坏情况:E=2;时间复杂度:O(n2)1葿(2)最小插入(cheapestinsertion)法薆最坏情况:E=2;时间复杂度:O(n2lgn).膃(3)任意插入(arbitraryinsertion)法羁最坏情况:E=21gn+;时间复杂度:O(n2)1芈(4)最远插入(farthestinsertion)法蚆最坏情况:E=21gn+;时间复杂度:O(n2)1薄(5)凸核插入(convexhullinsertion)法葿最坏情况:E=未知;时间复杂度:O(n2lgn)1肇2 最近邻算法(nearestneighborheuristics)螆Step1 任取一出发点;螁Step2 依次取最近的点加入当前解中直至形成回路解1膁适用范围:对称型△TSP1螆具体实施中,可以将出发点取遍V中各点而得到多个解,从中选择最好的一个,但此时袆的时间复杂度增加了n倍1膂最坏情况:E=(1gn+1)ö2;时间复杂度:O(n2)1薈3 Clark&Wright算法衿Step1 任取一出发点p,计算sij=dpi+dpi-dij;羆Step2 将各sij由大到小排列;薂Step3 将排好后的各(i,j)依次适当联结,形成回路解1莀适用范围:对称型△TSP1薇具体实施中,可将出发点p取遍V中各点而得到多个解,从中选择最好的一个,但此时肆的时间复杂度增加了n倍1羃最坏情况:E=21gnö7+5ö21;时间复杂度:O(n2)1螈4 双生成树算法(doublespanningtreeheuristics)莆Step1 首先求出最小生成树;肆Step2 将树中各边都添一重复边并求出其Euler回路;莄Step3 在Euler回路点序列中去除重复点,形成回路解1蒀适用范围:对称型△TSP1荿最坏情况:E=2;时间复杂度:O(n2)1膆5 Christofides算法蒁Step1 首先求出最小生成树;膂Step2 对树中所有奇顶点解最小权匹配问题;膈Step3 将匹配边添入生成树并求出其Euler回路;芅Step4 在Euler回路点序列中去除重复点,形成回路解1袂适用范围:对称型△TSP1蚀最坏情况:E=3ö2;时间复杂度:O(n3)1羇6 r-opt算法莅该方法是一种局部改进搜索算法,由Lin等人(1965)提出1其思想是对给定的初始回芃路,通过每次交换r条边来改进当前解1对不同的r,优劣次序为:莂2-opt<3-opt<⋯<r-,大量计算发现,3-opt法比2-opt法好,而4-opt、5-opt等却并不比3-opt来蒅得优越,况且r越大,运算时间越长1对于3-opt法,有一个经验公式告诉我们,求得最优蚄解的概率为2-nö10,例如,对于n=50,有p=2-50ö10=,只要随机选取150条初始路线,袀则求得最优解的概率可达01991迄今为止,3-opt法仍是一种相当有效的近似算法1蝿适用范围:对称型△TSP1薅最坏情况:E=2(n≥8,r≤nö4);时间复杂度:O(nr)1袁7 positealgorithm)薁用某个近似算法求得初始解,然后借助一个或若干个r-opt算法对解加以改进1这种蒈混合型的算法往往能获得较好的解,但也很耗时,一般仅在对解有较高要求时采用1蚅8 概率算法(probabilisticalgorithm)芁该算法能对任意给定的E>0,在1+E之内几乎处处解决△TSP1假定G位于单位正方罿形内,函数t(n)映射到正有理数,满足:①t~log2log2n;②对所有n,nöt是完全平方1则有芆Step1 以[t(n)ön]1ö2为尺寸构成网格,将单位正方形分成nöt(n)个子正方形,将G也蚅分成至多nöt(n)个子图;蚂Step2 用动态规划方法求解每个子图的最优回路;螁Step3 将nöt(n)个子图各自收缩为一点,其间距离定义为原子图的最优子回路间最艿短距离,并对新构成的图求最小生成树T;螅Step4 将T∪{各子图的最优子回路}视为一可能有点、边重复的闭回路,根据三角形肃不等式条件,归约重复点或边,得TSP回路1腿适用范围:对称型△TSP1肈最坏情况:E=1+(任意给定正数);时间复杂度:O(nlgn)1袅9