近似算法.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)12 最近邻算法(nearestneighborheuristics)Step1 任取一出发点;Step2 依次取最近的点加入当前解中直至形成回路解1适用范围:对称型△TSP1具体实施中,可以将出发点取遍V中各点而得到多个解,从中选择最好的一个,但此时的时间复杂度增加了n倍1最坏情况:E=(1gn+1)ö2;时间复杂度:O(n2)13 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)14 双生成树算法(doublespanningtreeheuristics)Step1 首先求出最小生成树;Step2 将树中各边都添一重复边并求出其Euler回路;Step3 在Euler回路点序列中去除重复点,形成回路解1适用范围:对称型△TSP1最坏情况:E=2;时间复杂度:O(n2)15 Christofides算法Step1 首先求出最小生成树;Step2 对树中所有奇顶点解最小权匹配问题;Step3 将匹配边添入生成树并求出其Euler回路;Step4 在Euler回路点序列中去除重复点,形成回路解1适用范围:对称型△TSP1最坏情况:E=3ö2;时间复杂度:O(n3)16 r-opt算法该方法是一种局部改进搜索算法,由Lin等人(1965)提出1其思想是对给定的初始回路,通过每次交换r条边来改进当前解1对不同的r,优劣次序为:2-opt<3-opt<⋯<r-opt. 但是,大量计算发现,3-opt法比2-opt法好,而4-opt、5-opt等却并不比3-opt来文档来自于网络搜索得优越,况且r越大,运算时间越长1对于3-opt法,有一个经验公式告诉我们,求得最优文档来自于网络搜索解的概率为2-nö10,例如,对于n=50,有p=2-50ö10=,只要随机选取150条初始路线,文档来自