《TSP问题导引解析》由会员分享，可在线阅读，更多相关《TSP问题导引解析（66页珍藏版）》请在金锄头文库上搜索。
1、TSPTSP问题导引解析问题导引解析旅行商问题旅行商问题(Traveling Salesman Problem)定式化定式化是困是困难难的的问题问题因为报道因为报道而成而成为为有名有名的的问题各各种种求解方法的求解方法的尝试尝试旅行商问题旅行商问题旅行商每每个城市都经过一次,又回到出发地。搜索出旅行商所经过的最短路径。个城市将会有, 5!/2= 5432 / 2 = 60条路。 个城市有, （ - 1）! /2条路。近年来, 研究报告和科学杂志上纷纷登载 使得这一问题变得有名起来。TSP（Traveling Salesman Problem）原型：哈密尔顿回路问题钻孔规划问题钻孔规划问题决定在
2、电路板上钻孔（为焊入部件）順序问题决定在电路板上钻孔（为焊入部件）順序问题。钻孔机总移动距离最小化钻孔机总移动距离最小化 = = 单位时间单位时间内生产量最大化。内生产量最大化。不不对称旅行商称旅行商问题每每个城市都经过一次,又回到出发地。搜索出经过的最短路径。 但是，城市间的走行时间会随 走行的方向不同而有不同。（走行行时间的非对称性）实际的道路路网，参见右图的情况。3562789164277854机械行程安排机械行程安排问题铁板板滚轧规划划需要根据零件来设定切刀的位置。变更切刀设置的费用,依据部件种种类不同而有所不同 。（宽度很窄就比较困难）。变更切刀设置的费用最小化回到非对称TSP城市
3、= 生产的零部件旅行商 =滚轧机械距离 =变更切刀设置的费用旅行商问题的变化城市间距离非对称TSP 城市间距离与方向有关关 一般对称TSP 城市间距离与方向无关关平面TSP 城市是平面上的点, 城市间距离是2点間的直线距离 特殊其他情况m人TSP m人从出发点出发遍历所有城市刚好通过过各城市1次通过过1次以上通过过各边1次以上 = 中国邮递员问题 (Chinese Postman Problem)Hamilton闭合回路问题闭合回路问题旅行商旅行商问题问题模型模型困困难难的根源的根源图图：頂点及其与顶点相连的边称为图頂点：, , , , 边：a, b, c, d, e, fa =1,2, b
4、=2,3, 。 abcdeHamilton 回路问题Hamilton 闭合回路：正好一次连续通过所有的顶点, 又回到出发点的路径(回路)。下面的图中有Hamilton回路吗？ YES:有Hamilton回路 NO:没有Hamilton回路HamiltonWilliam Rowan Hamilton (1805-1865)因发现Hamilton 元数成名的英国数学家。Icosian Game: 寻找刚好一次通过所有正12面体的頂点（20个），又回到原点的路线，2人玩的游戏。Hamilton 将付给胜者25英镑。第一人： 指定最初4歩（5个頂点）。第二人：探索5歩以后的路线。刚好一次通过所有正12
5、面体的頂点（20个），又回到原点。找到的话，胜利。20？参考参考书目目参考书目目The Traveling Salesman Problem, E. L.Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, Wiley, 1985。参考书目目通向旅行商问题的邀请, 山本芳嗣, 久保幹雄, 朝倉書店。参考书目目整数规划法与組合最优化, 今野浩, 鈴木久敏, 日科技連。组合数的爆炸（巨大的合数的爆炸（巨大的计计算量）算量）旅行商旅行商问题问题的的难难度度计计算量算量组合最优化的难度（对称）TSP：n个城市的情况, (n1)!2
6、条路。 組合的数量虽然有限，但是数量巨大,所以很难找到最优解。组合锁 (Combination Lock)：組合虽然有限,但是要找到最优的解（打开锁）是很困难的。 知道锁的性质,有效的开开锁。因为要在有限时间时间内求解问题，所以 对求解所花的时间讨论是最基本的讨论。901 23345 6723 45計算量, 比較： 这5个基本的演算全部可以一步执行。(实际上,比更花时间。实际上是连加）Q1. 求a1, ,an 2倍的和。 (1) 2a1+ 2an , 2n-1 steps O(n)算法。 (2) 2(a1+an) , n steps O(n)算法。Q2. a1b1+anbn的計算。 2n-1
7、steps O(n)算法。Q3. 2个矩阵的乘法。 按定定义计算算 n2(2n-1) steps O(n3)算法。 注: Strassen 算法是 O(n2.7)。算法的速度算法的速度算法的运行时间时间，很大程度上依赖于输入的数。 最坏値评价： 最不利情况下估计所用的时间。 :O(n)O(n log n ) 多項式时间时间算法O(n2) polynomial time algorithmO(n3) : : O(2n) 指数时间时间算法O(n!) exponential time algorithmO(n log2 n ) = O(n log10 n ) 組合爆組合爆炸炸（对称）TSP： n个城
8、市时, (n1)!2 条路线。100MIPS (mega instructions per second)1秒进行100万次计算1次 / 10-6秒秒 光速 3.01010 cm/秒 (10-6秒 前进300m)n 10 100 1,000 10,000n 10-5秒 10-4秒 10-4秒 0.001秒n2 10-4秒 0.01秒 1秒 100秒n3 0.001秒 1秒 16.6分 277小时2n 0.001秒 1014世紀 10284世紀 n! 0.036秒 10141世紀 102551世紀 自己体会吧! 宇宙宇宙年年龄 1.5108 世紀世紀 （亿年）年）计算机速度与算机速度与组合爆炸合
9、爆炸计算机速度不快的的话，差别将会有多么大！10秒可以进行的計算量是？ 100MIPS 10倍 100倍 1000倍 n 107 108 109 1010 n2 3千 1万 3万 10万n3 215 462 1千 2千2n 23 27 30 33 n! 10 11 12 131000倍 一步步的时间是10-9秒 10-9秒 光只可以前进30cm5mm的芯片：光要走1.71011 秒。如果把計算機并联的话5 mm 四方 芯片： 光要走 5mm 的话需要1.71011 秒, 也就是1步步需要花1.71011 秒时间。地球表面全部覆盖上述芯片，需要： 2.01019個。与100MIPS的計算機相比，
10、哪个更快？n 100 1,000 2n 1014世紀 0.85 秒 10284世紀 10263世紀 n! 10141世紀 10120世紀 102551世紀 102530世紀因为是在有限数里面求解, 实质上就是讨论計算的速度。计算的复算的复杂度度(Computational Complexity )存在存在判断判断问题的困的困难什么是判断存在的问题问题：用YES和NO回答，但是回答的难易不同。全部的乌鸦乌鸦是黑色的 有不黒的乌鸦吗？YES：（簡単）举出这样的乌鸦。（举出反例） NO：（困難）检查所有的所有的乌鸦？有宇宙人吗？YES :（簡単）发现有宇宙人。NO：（困難）搜索所有宇宙？計算的可能性
11、与反証可能性也是如此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完全
12、：有多項式时间时间算法算法， ， 但几乎无法但几乎无法求解的问题的等级NPco-NPNP-完全PHamilton回路问题指派问题最小包围圆问题最小包包围圆问题围圆问题：包含给给定点集合, 求半径最小的圆。 不是 是n点：有O(n)时间算法。平面TSP给定的路线是最优解(最短)？ 不是 是？如果不是最优解，有更优解的证据是？是最优解的証据是？求解求解TSP的算法的算法严格算法格算法近似算法近似算法启启发算法算法TSP算法算法的种的种类严格算法 (exact algorithm)：求出1个最优解的算法。近似算法 (approximation algorithm)：保証求解（一定）精度。启发算法 (
13、heuristic algorithm)：搜索认为是好的解的算法。解的精度无法保証。严格算法格算法分枝切割法分边边定界法組合的多面体論严格算法历史（平面TSP)1954: 49城市： 切除平面法 Dantzig, Fulkerson and Johnson 1971: 65城市： 拉各朗日双对法Held and Karp1980: 318城市: 分枝切割法Christofides and Padberg1991: 666城市： 分枝切割法Grotschel and Holland1991: 2,392城市： 分枝切割法Padberg and Rinaldi1993: 4,461城市： 並行計算
14、机分枝切割法Applegate, Bixby, Chvatal and Cook1994: 7,397城市： 並行計算机分枝切割法Applegate, Bixby, Chvatal and Cook近似算法近似算法近似近似的困難的困難簡単簡単的个近似算法的个近似算法近似的困难定理：对于给定任意正数 M，以下成立。给定（对称）TSP，最短路径的长度的M倍以下的路径存在否？这样的问题问题就是NP完全的。求最优解的M倍以内的近似解，与原问题问题（TSP)的难易程度相同。三角不等式成立时，就有近似算法。旅行商旅行商问题问题之之2近似算法近似算法全域树树：連結全体頂点的边边的集合最短全域树树：可以用贪婪
15、算法求解。从最短边边开始开始顺序（不可以在圈内取）选取。最短全域树树的長度最短回路 1 245788 1 245788 1 245788 1 2457885 1 247882重全域树法三角不等式成立时，有近似算法：沿着最短全域树树， 已已经经过的頂点，遍历所有頂点。 跳过。2最短路径長2最短全域树長得到的路径長启启发式算法式算法（平面TSP）局部搜索局部搜索 Simulated Annealing Tabu Search启发式算法式算法构筑法 (construction method) nearest neighbor 法法 nearest addition 法法 farthest inser
16、tion 法法改进法 (improvement method)局部搜索法 (local search method)模拟退火法 (simulated annealing method)禁忌搜索法 (tabu search method)遗传算法(genetic algorithm)神经网络(neural network)：（没有用于TSP,最近没有使用此方法）构筑法构筑法 nearest neighbor 法法 nearest addition 法法 farthest insertion 法法构筑法nearest neighbor 法：（与最优值的误差 15）nearest addition
17、法： （与最优值的误差 20）farthest insertion 法： （与最优值的误差 5）改改进方法方法局部搜索法 (local search method)模拟退火法 (simulated annealing method)禁忌搜索法 (tabu search method)局部搜索法 (Local Search)最簡単的改进法改进法基础最有效的改进法有很多局部搜索法 (local search method)最基本的改进法也叫爬山算法 (hill climbing method) 。在現在解的附近（相似解的集合）中试探，如果出现更好的目标函数値，就更新現在解。（全局）最优优解局部最优
18、优解局部最优优解目标函数値满意使用2-opt附近的局部搜索法 2-opt附近：交替2条边边得到的路径集合从現在路径出发，交替2条边边， 如果得到更短的路径, （1条也可以），就更新现在的路径。Nearest Neighbor + 2-opt =(与最优値相差大大约2.5%）etc。一般的局部搜索法 （图） （全局）最优优解局部最优优解局部最优优解邻域目标函数値满意邻域的決定旅行商问题问题的邻域邻域2-opt邻域邻域：替换2条边边得到的路径。3-opt邻域邻域：替换3条边边得到的路径。4-opt邻域邻域：替换4条边边得到的路径。邻域确定域确定例 ： 2-opt 3-opt 4-opt 。领域的确
19、定领域的确定： 狭小 宽广 邻域搜索 ： 时间短 时间长所得解： 不好的局部最优优解好的局部最优优解领域的确定取决于领域的确定取决于解的好坏与可使用的计算时间的平衡。 Nearest neighbor =(与最优优値有15偏差） Nearest neighbor + 2-opt =(2.5偏差）Nearest neighbor + 2,3-opt =(0.3偏差）搜索空搜索空间設定設定Lin and Kernighan算法 搜索的解空间，从可行域稍微扩展，构造性能良好的搜索法。怀怀疑可行解：可行解附近的解集合，定义为怀疑可行解，在怀怀疑可行解中搜索。路径 （路径e ，路径k？）：e,k为路径标
20、识字符Lin and Kernighan 算法搜索的領域，从可行解集合（路径集合）稍微扩展。对应的路径可行解怀怀疑可行解跳出局部最优解跳出局部最跳出局部最优解解局部搜索法，会在局部最优优解停止（陷落）。有必要跳出局部最优优解改变初始解，再运用局部搜索法(multiple start local search)暂时导入宽领域域的附近解(iterated local search)引入随机性模拟退火法 (simulated annealing method)最急下降最缓上升禁忌搜索法 (tabu search method)Iterated Local Search暂时使用宽领域域的附近解，跳出局
21、部最优优解。iterated local searchiterated local search：暂时使用宽领域域的附近解，跳出現在局部最优优解。例：对于旅行商问题问题的 Lin and Kernighan探索法，在得到局部最优优解的同时，(任意) 进行4-opt 操作，跳出局部最优优解。模拟退火法(Simulated Annealing)使用随机性，跳出局部最优优解。引入解的改进量，给予随机的偏向。simulated annealingannealing: 退火：为了消除金属或者玻璃内部的形变，使温度渐渐冷却到某种种程度。按以下方法爬山： 从現在地 x 附近附近领域内选择适当的一点 。if
22、(x ), then (x = )。else (以某种种概率p 由x 向 移动动)。 x 与 的海拔高差小 移动动的概率 p大。 气温高（热） 移动动的概率 p大。气温随随时间徐徐下降。simulated annealing反复反复执行行以下各部。（目标函数 f (x) ）現在解为 x，現在温度为T。x 附近附近 领域内选择适当的一点 。if ( 比比 x 为更好的解), then (x = y)。else (以概率 exp-| f(x)-f( )| / T 更新 x)。 変化量|f(x)-f( )|小 更新概率大。 温度T高 更新概率大。 （温度高的话，就有跳出局部最优优解的可能性。）温度在
23、循环的同时下降。例：对数冷却：第k 循环的温度 Tk1/log(k+1)simulated annealing 的特征的特征从附近选择1点进行计算。不是从附近全域进行搜索。可以在比局部搜索范围内更广的范围进行搜索。 也可以用opt 附近搜索。定理Hajek表現为simulated annealing行为的Markov chain如果是按既定的弱可逆的话，使用对数冷却的 simulated annealing 生成解的列，以概率1向最优解收敛。注：保証上述定理收收敛所花所花的时间时间， ，比比O( !） ）長。禁忌搜索法(Tabu Search)最急下降最緩上升，跳出局部最优优解。使用禁忌表，避
24、免循环。最急降下最緩上昇（最小化问题问题的）跳出局部最优解：最急下降：向下時，朝下降最快的方向下降。最緩上昇：不向下时，朝最缓的方向上升。只是这样的话，会陷于重复复的几个解。使用禁忌表，暂时一段时间内禁止使用。（下页示例）tabu search 2opt 附近：交換2条边边tabu：某个循环时边 e与边边 f 交換过了，那么以后数次的循环，禁止使用e 和 f 的 2-opt 交換。tabu list：禁止交換的边边的表。tabu search: 在可能的 2-opt 交換中，选择最急下降最緩上昇的交換。tabu length：停留于tabu 状态的禁忌解的数量。 从 511 的値中任意选取。记忆频率（率（长期期记忆）的引入）的引入在解的一部分中进行局部交換，如果目标函数值没有什么变化，说明这一目标函数值多次发生的可能性大。记忆频率：解的更新方法有很多种种，记忆频率是将解出现的频率（次数）记忆起来。 尽量不要进行频率高的更新tabu search 的特点附近领域内全搜索：在不怎么不怎么宽的附近领域内选取。算法的框架：可以把大多数问题问题的依赖規則包含起来。变化很多（太多了）。建立良好算法的公式很少。完结束结束
