TSP问题导引

旅行商问题入门IntroductiontoTravelingSalesmanProblems東京大学工学部計数工学科松井知己旅行商问题(TravelingSalesmanProblem)●定式化是困难的问题●因为报道而成为有名的问题●各种求解方法的尝试旅行商问题旅行商每个城市都经过一次,又回到出发地。搜索出旅行商所经过的最短路径。６个城市将会有,5!/2=5×4×3×2/2=60条路。ｎ个城市有,（ｎ-1）!/2条路。近年来,研究报告和科学杂志上纷纷登载使得这一问题变得有名起来。TSP（TravelingSalesmanProblem）原型：哈密尔顿回路问题钻孔规划问题决定在电路板上钻孔（为焊入部件）順序问题。钻孔机总移动距离最小化=单位时间内生产量最大化。不对称旅行商问题每个城市都经过一次,又回到出发地。搜索出经过的最短路径。但是，城市间的走行时间会随走行的方向不同而有不同。（走行时间的非对称性）实际的道路路网，参见右图的情况。3562789164277854机械行程安排问题铁板滚轧规划需要根据零件来设定切刀的位置。变更切刀设置的费用,依据部件种类不同而有所不同。（宽度很窄就比较困难）。变更切刀设置的费用最小化回到非对称TSP城市=生产的零部件旅行商=滚轧机械距离=变更切刀设置的费用旅行商问题的变化城市间距离非对称TSP城市间距离与方向有关一般对称TSP城市间距离与方向无关平面TSP城市是平面上的点,城市间距离是2点間的直线距离特殊其他情况m人TSPm人从出发点出发遍历所有城市刚好通过各城市1次→通过1次以上通过各边1次以上=中国邮递员问题(ChinesePostmanProblem)Hamilton闭合回路问题●旅行商问题模型●困难的根源图图：頂点及其与顶点相连的边称为图頂点：①,②,③,④,⑤边：a,b,c,d,e,fa={1,2},b={2,3},。。。１２３４５abcdeｆHamilton回路问题Hamilton闭合回路：正好一次连续通过所有的顶点,又回到出发点的路径(回路)。下面的图中有Hamilton回路吗？YES:有Hamilton回路NO:没有Hamilton回路HamiltonWilliamRowanHamilton(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个城市的情况,(n‐1)!／2条路。組合的数量虽然有限，但是数量巨大,所以很难找到最优解。组合锁(CombinationLock)：組合虽然有限,但是要找到最优的解（打开锁）是很困难的。知道锁的性质,有效的开锁。因为要在有限时间内求解问题，所以对求解所花的时间讨论是最基本的讨论。9012334567１2345計算量＋,－,×,÷,比較：这5个基本的演算全部可以一步执行。(实际上,×比＋更花时间。×实际上是连加）Q1.求a1,…,an2倍的和。(1)2×a1+･･･+2×an,2n-1steps→O(n)算法。(2)2×(a1+･･･+an),nsteps→O(n)算法。Q2.a1b1+･･･+anbn的計算。2n-1steps→O(n)算法。Q3.2个ｎ×ｎ矩阵的乘法。按定义计算n2(2n-1)steps→O(n3)算法。注:Strassen算法是O(n2.7)。算法的速度算法的运行时间，很大程度上依赖于输入的数。最坏値评价：最不利情况下估计所用的时间。:O(n)O(nlogn)多項式时间算法O(n2)polynomialtimealgorithmO(n3)::O(2n)指数时间算法O(n!)exponentialtimealgorithmO(nlog2n)=O(nlog10n)組合爆炸（对称）TSP：n个城市时,(n‐1)!／2条路线。100MIPS(megainstructionspersecond)1秒进行100万次计算＝1次/10-6秒光速3.0×1010cm/秒(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.5×108世紀（１５０亿年）计算机速度与组合爆炸计算机速度不快的的话，差别将会有多么大！10秒可以进行的計算量是？100MIPS10倍100倍1000倍n1071081091010n23千1万3万10万n32154621千2千2n23273033n!101112131000倍⇒一步的时间是10-9秒⇒10-9秒光只可以前进30cm5mm的芯片：光要走1.7×10‐11秒。如果把計算機并联的话5mm四方芯片：光要走5mm的话需要1.7×10‐11秒,也就是1步需要花1.7×10‐11秒时间。地球表面全部覆盖上述芯片，需要：2.0×1019個。与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‐完全：有多項式时间算法，但几乎无法求解的问题的等级NPco-NPNP-完全PHamilton回路问题指派问题最小包围圆问题最小包围圆问题：包含给定点集合,求半径最小的圆。不是是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）●局部搜索●SimulatedAnnealing●TabuSearch启发式算法构筑法(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%）etc。一般的局部搜索法（图）（全局）最优解局部最优解局部最优解邻域目标函数値满意邻域的決定旅行商问题的邻域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算法搜索的解空间，从可