[数学]第7讲TSP问题导引2011.ppt

旅行商问题入门Introduction to Traveling Salesman Problems 東京大学工学部計数工学科 松井知己 旅行商问题(Traveling Salesman Problem) ●定式化是困難的问题 ●因为报纸报道而成为有名的问题 ●各种求解方法的尝试 旅行商问题 旅行商每个城市都经过一次,又回到出发地。有哪些信誉好的足球投注网站出旅行商所经过的最短路径。 ６个城市的话将会有, 5!/2= 5×4×3×2 / 2 = 60条路。 ｎ 个城市的话, （ｎ - 1）! /2条路。 近年来, 报纸和科学杂志上纷纷登载 使得这一问题变得有名起来。 TSP（Traveling Salesman Problem） 原型：哈密尔顿回路问题 钻孔规划问题 决定电路板上钻孔（焊入部件）順序的问题。 总移动距离最小化 = 单位时间内生产量最大化。 不对称旅行商问题 每个城市都经过一次,又回到出发地。有哪些信誉好的足球投注网站出经过的最短路径。 但是，城市间的走行时间会随 走行的方向不同而有不同。 （走行时间的非対称性） 实际的道路路网， 参见右图的情况。 机械行程安排问题 铁板滚轧规划 需要根据零件来设定切刀的位置。 变更切刀设置的费用,会根据部件的 种类不同而有所不同 。 （宽度很窄就比较困难）。 变更切刀设置的费用最小化 回到非対称TSP 城市 = 生产的零部件 旅行商 =滚轧机械 距离 =变更切刀设置的费用 旅行商问题的变化 城市间距离 非対称TSP 城市間距离与方向有关 一般 対称TSP 城市間距离与方向无关 平面TSP 城市是平面上的点, 城市間距离是2点間的直线距离 特殊 其他约束 m人TSP m人从出发点出发遍历所有城市 刚好通过各城市1次→通过1次以上 通过各边1次以上 = 中国邮递员问题 (Chinese Postman Problem) Hamilton闭合回路问题 ●旅行商问题模型 ●困难的根源 图 图：頂点及其与顶点相连的边称为图 頂点：①, ②, ③, ④, ⑤ 边：a, b, c, d, e, f a ={1,2}, b ={2,3}, 。。。 １ ２ ３ ４ ５ a b c d e ｆ Hamilton 回路问题 Hamilton 闭合回路：正好一次连续通过所有的顶点, 又回到出发点的路径(回路)。 下面的图中有Hamilton回路吗？ YES:有Hamilton回路 NO:没有Hamilton回路 Hamilton William Rowan Hamilton (1805-1865) 因发现「Hamilton４元数」成名的英国数学家。 Icosian Game: 寻找刚好一次通过所有正12面体的頂点（20个），又回到原点的路线，2人玩的游戏。 Hamilton 将付给胜者25英镑。 第一人： 指定最初4歩 （5个頂点）。 第二人：探索5歩以后的路线。 刚好一次通过所有正12面体 的頂点（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个城市的情况, (n‐1)!／2条路。 組合的数量虽然有限，但是数量巨大,所以很难找到最优解。 组合锁 (Combination Lock)： 組合虽然有限,但是要找到最优的 解（打开锁）时很困难的。 知道锁的性质,有效的开锁。 因为要在有限时间内求解问题，所以 对求解所花的时间讨论是最基本的讨论。 計算量 ＋,－,×,÷, 比較： 这5个基本的演算全部可以一步执行。 (实际上,×比＋更花时间。） Q1. 求a1, …,an 2倍的和。 (1) 2×a1+･･･+ 2×an , 2n-1 steps→ O(n)算法。 (2) 2×(a1+･･･+an) , n steps→ O(