TSP问题导引解析.ppt

旅行商问题入门IntroductiontoTravelingSalesmanProblems,東京大学工学部計数工学科松井知己,旅行商问题(TravelingSalesmanProblem),定式化是困难的问题因为报道而成为有名的问题各种求解方法的尝试,旅行商问题,旅行商每个城市都经过一次,又回到出发地。搜索出旅行商所经过的最短路径。个城市将会有,5!/2=5432/2=60条路。个城市有,（-1）!/2条路。近年来,研究报告和科学杂志上纷纷登载使得这一问题变得有名起来。TSP（TravelingSalesmanProblem）原型：哈密尔顿回路问题,钻孔规划问题,决定在电路板上钻孔（为焊入部件）順序问题。钻孔机总移动距离最小化=单位时间内生产量最大化。,不对称旅行商问题,每个城市都经过一次,又回到出发地。搜索出经过的最短路径。但是，城市间的走行时间会随走行的方向不同而有不同。（走行时间的非对称性）实际的道路路网，参见右图的情况。,机械行程安排问题,铁板滚轧规划需要根据零件来设定切刀的位置。变更切刀设置的费用,依据部件种类不同而有所不同。（宽度很窄就比较困难）。变更切刀设置的费用最小化回到非对称TSP城市=生产的零部件旅行商=滚轧机械距离=变更切刀设置的费用,旅行商问题的变化,城市间距离非对称TSP城市间距离与方向有关一般对称TSP城市间距离与方向无关平面TSP城市是平面上的点,城市间距离是2点間的直线距离特殊其他情况m人TSPm人从出发点出发遍历所有城市刚好通过各城市1次通过1次以上通过各边1次以上=中国邮递员问题(ChinesePostmanProblem),Hamilton闭合回路问题,旅行商问题模型困难的根源,图,图：頂点及其与顶点相连的边称为图頂点：,边：a,b,c,d,e,fa=1,2,b=2,3,。,a,b,c,d,e,Hamilton回路问题,Hamilton闭合回路：正好一次连续通过所有的顶点,又回到出发点的路径(回路)。下面的图中有Hamilton回路吗？YES:有Hamilton回路NO:没有Hamilton回路,Hamilton,WilliamRowanHamilton(1805-1865)因发现Hamilton元数成名的英国数学家。IcosianGame:寻找刚好一次通过所有正12面体的頂点（20个），又回到原点的路线，2人玩的游戏。Hamilton将付给胜者25英镑。第一人：指定最初4歩（5个頂点）。第二人：探索5歩以后的路线。刚好一次通过所有正12面体的頂点（20个），又回到原点。找到的话，胜利。,20,参考书目,参考书目,TheTravelingSalesmanProblem,E.L.Lawler,J.K.Lenstra,A.H.G.RinnooyKan,andD.B.Shmoys,Wiley,1985。,参考书目,通向旅行商问题的邀请,山本芳嗣,久保幹雄,朝倉書店。,参考书目,整数规划法与組合最优化,今野浩,鈴木久敏,日科技連。,组合数的爆炸（巨大的计算量）,旅行商问题的难度计算量,组合最优化的难度,（对称）TSP：n个城市的情况,(n1)!2条路。組合的数量虽然有限，但是数量巨大,所以很难找到最优解。组合锁(CombinationLock)：組合虽然有限,但是要找到最优的解（打开锁）是很困难的。知道锁的性质,有效的开锁。因为要在有限时间内求解问题，所以对求解所花的时间讨论是最基本的讨论。,計算量,比較：这5个基本的演算全部可以一步执行。(实际上,比更花时间。实际上是连加）Q1.求a1,an2倍的和。(1)2a1+2an,2n-1stepsO(n)算法。(2)2(a1+an),nstepsO(n)算法。Q2.a1b1+anbn的計算。2n-1stepsO(n)算法。Q3.2个矩阵的乘法。按定义计算n2(2n-1)stepsO(n3)算法。注:Strassen算法是O(n2.7)。,算法的速度,算法的运行时间，很大程度上依赖于输入的数。最坏値评价：最不利情况下估计所用的时间。:O(n)O(nlogn)多項式时间算法O(n2)polynomialtimealgorithmO(n3):O(2n)指数时间算法O(n!)exponentialtimealgorithm,O(nlog2n)=O(nlog10n),組合爆炸,（对称）TSP：n个城市时,(n1)!2条路线。100MIPS(megainstructionspersecond)1秒进行100万次计算1次/10-6秒光速3.01010cm/秒(10-6秒前进300m)n101001,00010,000n10-5秒10-4秒10-4秒0.001秒n210-4秒0.01秒1秒100秒n30.001秒1秒16.6分277小时2n0.001秒1014世紀10284世紀n!0.036秒10141世紀102551世紀自己体会吧!宇宙年龄1.5108世紀（亿年）,计算机速度与组合爆炸,计算机速度不快的的话，差别将会有多么大！10秒可以进行的計算量是？100MIPS10倍100倍1000倍n1071081091010n23千1万3万10万n32154621千2千2n23273033n!101112131000倍一步的时间是10-9秒10-9秒光只可以前进30cm5mm的芯片：光要走1.71011秒。,如果把計算機并联的话,5mm四方芯片：光要走5mm的话需要1.71011秒,也就是1步需要花1.71011秒时间。地球表面全部覆盖上述芯片，需要：2.01019個。与100MIPS的計算機相比，哪个更快？n1001,0002n1014世紀0.85秒10284世紀10263世紀n!10141世紀10120世紀102551世紀102530世紀因为是在有限数里面求解,实质上就是讨论計算的速度。,计算的复杂度(ComputationalComplexity),存在判断问题的困难,什么是判断存在的问题：用YES和NO回答，但是回答的难易不同。全部的乌鸦是黑色的有不黒的乌鸦吗？YES：（簡単）举出这样的乌鸦。（举出反例）NO：（困難）检查所有的乌鸦？有宇宙人吗？YES:（簡単）发现有宇宙人。NO：（困難）搜索所有宇宙？計算的可能性与反証可能性也是如此,Hamiton回路问题,Hamilton回路：正好一次连续通过所有的顶点,又回到出发点的路径(回路)。存在Hamilton或回路吗？YES:Hamilton回路有NO:Hamilton回路無证据是？,指派问题,4个工作分配给4台机器。,YES,指派问题(NO例）,不存在分配(NO!)不存在的证据是？,2n頂点：需要O(n2.5)的时间检查是否存在。,NP完全(NP-complete),決定问题：可以回答YES-NO的问题NP等级：有回答YES证据的问题的等级co-NP等级：有回答NO证据的问题的等级P：多項式时间算法可求解问题的等级NP完全：有多項式时间算法，但几乎无法求解的问题的等级,NP-完全,P,Hamilton回路问题,指派问题,最小包围圆问题,最小包围圆问题：包含给定点集合,求半径最小的圆。不是是n点：有O(n)时间算法。,平面TSP,给定的路线是最优解(最短)？不是是？如果不是最优解，有更优解的证据是？是最优解的証据是？,求解TSP的算法,严格算法近似算法启发算法,TSP算法的种类,严格算法(exactalgorithm)：求出1个最优解的算法。近似算法(approximationalgorithm)：保証求解（一定）精度。启发算法(heuristicalgorithm)：搜索认为是好的解的算法。解的精度无法保証。,严格算法,分枝切割法分边定界法組合的多面体論,严格算法历史（平面TSP),1954:49城市：切除平面法Dantzig,FulkersonandJohnson1971:65城市：拉各朗日双对法HeldandKarp1980:318城市:分枝切割法ChristofidesandPadberg1991:666城市：分枝切割法GrotschelandHolland1991:2,392城市：分枝切割法PadbergandRinaldi1993:4,461城市：並行計算机分枝切割法Applegate,Bixby,ChvatalandCook1994:7,397城市：並行計算机分枝切割法Applegate,Bixby,ChvatalandCook,近似算法,近似的困難簡単的个近似算法,近似的困难,定理：对于给定任意正数M，以下成立。给定（对称）TSP，最短路径的长度的M倍以下的路径存在否？这样的问题就是NP完全的。求最优解的M倍以内的近似解，与原问题（TSP)的难易程度相同。三角不等式成立时，就有近似算法。,旅行商问题之2近似算法,全域树：連結全体頂点的边的集合最短全域树：可以用贪婪算法求解。从最短边开始顺序（不可以在圈内取）选取。最短全域树的長度最短回路,2重全域树法,三角不等式成立时，有近似算法：沿着最短全域树，已经经过的頂点，遍历所有頂点。跳过。2最短路径長2最短全域树長得到的路径長,启发式算法（平面TSP）,局部搜索SimulatedAnnealingTabuSearch,启发式算法,构筑法(constructionmethod)nearestneighbor法nearestaddition法farthestinsertion法改进法(improvementmethod)局部搜索法(localsearchmethod)模拟退火法(simulatedannealingmethod)禁忌搜索法(tabusearchmethod)遗传算法(geneticalgorithm)神经网络(neuralnetwork)：（没有用于TSP,最近没有使用此方法）,构筑法,nearestneighbor法nearestaddition法farthestinsertion法,构筑法,nearestneighbor法：（与最优值的误差15）nearestaddition法：（与最优值的误差20）farthestinsertion法：（与最优值的误差5）,改进方法,局部搜索法(localsearchmethod)模拟退火法(simulatedannealingmethod)禁忌搜索法(tabusearchmethod),局部搜索法(LocalSearch),最簡単的改进法改进法基础最有效的改进法有很多,局部搜索法(localsearchmethod),最基本的改进法也叫爬山算法(hillclimbingmethod)。在現在解的附近（相似解的集合）中试探，如果出现更好的目标函数値，就更新現在解。,目标函数値,满意,使用2-opt附近的局部搜索法,2-opt附近：交替2条边得到的路径集合从現在路径出发，交替2条边，如果得到更短的路径,（1条也可以），就更新现在的路径。NearestNeighbor+2-opt=(与最优値相差大约2.5%）,一般的局部搜索法（图）,（全局）最优解,局部最优解,局部最优解,邻域,目标函数値,满意,邻域的決定,旅行商问题的邻域2-opt邻域：替换2条边得到的路径。3-opt邻域：替换3条边得到的路径。4-opt邻域：替换4条边得到的路径。,邻域确定,例：2-opt3-opt4-opt。领域的确定：狭小宽广邻域搜索：时间短时间长所得解：不好的局部最优解好的局部最优解领域的确定取决于解的好坏与可使用的计算时间的平衡。Nearestneighbor=(与最优値有15偏差）Nearestneighbor+2-opt=(2.5偏差）Nearestneighbor+2,3-opt=(0.3偏差）,搜索空间設定,LinandKernighan算法搜索的解空间，从可行域稍微扩展，构造性能良好的搜索法。怀疑可行解：可行解附近的解集合，定义为怀疑可行解，在怀疑可行解中搜索。路径（路径e，路径k？）：e,k为路径标识字符,LinandKernighan算法,搜索的領域，从可行解集合（路径集合）稍微扩展。对应的路径,可行解,怀疑可行解,跳出局部最优解,跳出局部最优解,局部搜索法，会在局部最优解停止（陷落）。有必要跳出局部最优解改变初始解，再运用局部搜索法(multiplestartlocalsearch)暂时导入宽领域的附近解(iteratedlocalsearch)引入随机性模拟退火法(simulatedannealingmethod)最急下降最缓上升禁忌搜索法(tabusearchmethod),IteratedLocalSearch,暂时使用宽领域的附近解，跳出局部最优解。,iteratedlocalsearch,iteratedlocalsearch：暂时使用宽领域的附近解，跳出現在局部最优解。例：对于旅行商问题的LinandKernighan探索法，在得到局部最优解的同时，(任意)进行4-opt操作，跳出局部最优解。,模拟退火法(SimulatedAnnealing),使用随机性，跳出局部最优解。引入解的改进量，给予随机的偏向。,simulatedannealing,annealing:退火：为了消除金属或者玻璃内部的形变，使温度渐渐冷却到某种程度。按以下方法爬山：从現在地x附近领域内选择适当的一点。if(x),then(x=)。else(以某种概率p由x向移动)。x与的海拔高差小移动的概率p大。气温高（热）移动的概率p大。气温随时间徐徐下降。,simulatedannealing,反复执行以下各部。（目标函数f(x)）現在解为x，現在温度为T。x附近领域内选择适当的一点。if(比x为更好的解),then(x=y)。else(以概率exp-|f(x)-f()|/T更新x)。変化量|f(x)-f()|小更新概率大。温度T高更新概率大。（温度高的话，就有跳出局部最优解的可能性。）温度在循环的同时下降。例：对数冷却：第k循环的温度Tk1/log(k+1),simulatedannealing的特征,从附近选择1点进行计算。不是从附近全域进行搜索。可以在比局部搜索范围内更广的范围进行搜索