TSP问题导引解析.ppt
《TSP问题导引解析.ppt》由会员分享,可在线阅读,更多相关《TSP问题导引解析.ppt(65页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、旅行商问题入门旅行商问题入门Introduction to Traveling Salesman Problems東京大学工学部計数工学科松井知己旅行商问题旅行商问题(Traveling Salesman Problem)定式化定式化是是困困难难的的问题问题因为报道因为报道而成而成为为有名有名的的问题各各种种求解方法的求解方法的尝试尝试旅行商问题旅行商问题旅行商每每个城市都经过一次,又回到出发地。搜索出旅行商所经过的最短路径。个城市将会有,5!/2=5432/2=60条路。个城市有,(-1)!/2条路。近年来,研究报告和科学杂志上纷纷登载 使得这一问题变得有名起来。TSP(Traveling
2、Salesman Problem)原型:哈密尔顿回路问题钻孔规划问题钻孔规划问题决决定定在电路板上钻孔在电路板上钻孔(为焊入部件为焊入部件)順序问题)順序问题。钻孔机总钻孔机总移动距离最小化移动距离最小化 =单位时间单位时间内内生产量最大化。生产量最大化。不不对称称旅行商旅行商问题每每个城市都经过一次,又回到出发地。搜索出经过的最短路径。但是,城市间的走行时间会随 走行的方向不同而有不同。(走行行时间的非对称性)实际的道路路网,参见右图的情况。3562789164277854机械机械行程安排行程安排问题铁板板滚轧规划划需要根据零件来设定切刀的位置。变更切刀设置的费用,依据部件种种类不同而有所不
3、同。(宽度很窄就比较困难)。变更切刀设置的费用最小化回到非对称TSP城市=生产的零部件旅行商=滚轧机械距离=变更切刀设置的费用旅行商问题的变化城市间距离非对称TSP 城市间距离与方向有关关 一般对称TSP 城市间距离与方向无关关平面TSP 城市是平面上的点,城市间距离是2点間的直线距离 特殊其他情况m人TSP m人从出发点出发遍历所有城市刚好通过过各城市1次通过过1次以上通过过各边1次以上=中国邮递员问题 (Chinese Postman Problem)Hamilton闭合回路闭合回路问题问题旅行商旅行商问题问题模型模型困困难难的根源的根源图图:頂点及其与顶点相连的边称为图頂点:,边:a,b
4、,c,d,e,fa=1,2,b=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歩以后的路线。刚好一
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个城市的情况,(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 steps O(n)算法。Q3.2个矩阵的乘法。按定定义计算算
7、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个城市时,(n1)!2 条路线。100MIPS(mega instructions per second)1秒进行
8、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 世紀世紀(亿年)年)计算机速度与算机速度与组合爆炸合爆炸计算机速度不快的的话,差别将会有多么大!10秒可以进行的計算量是?100MIPS 10倍 100倍 1000倍 n 10
9、7 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的計算機相比,哪个更快?n 100 1,000 2n 1014世紀 0.85 秒 10284世紀 10263世紀 n!10141世紀 10120世紀
10、 102551世紀 102530世紀因为是在有限数里面求解,实质上就是讨论計算的速度。计算的复算的复杂度度(Computational Complexity)存在存在判断判断问题的困的困难什么是判断存在的问题问题:用YES和NO回答,但是回答的难易不同。全部的乌鸦乌鸦是黑色的 有不黒的乌鸦吗?YES:(簡単)举出这样的乌鸦。(举出反例)NO:(困難)检查所有的所有的乌鸦?有宇宙人吗?YES:(簡単)发现有宇宙人。NO:(困難)搜索所有宇宙?計算的可能性与反証可能性也是如此Hamiton 回路问题Hamilton 回路:正好一次连续通过所有的顶点,又回到出发点的路径(回路)。存在Hamilton
11、或回路吗?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回路问题指派问题最小包围圆问题最小包包围圆围圆问题问
12、题:包含给给定点集合,求半径最小的圆。不是 是n点:有O(n)时间算法。平面TSP给定的路线是最优解(最短)?不是 是?如果不是最优解,有更优解的证据是?是最优解的証据是?求解求解TSP的的算法算法严格算法格算法近似算法近似算法启启发算法算法TSP算法算法的种的种类严格算法(exact algorithm):求出1个最优解的算法。近似算法(approximation algorithm):保証求解(一定)精度。启发算法(heuristic algorithm):搜索认为是好的解的算法。解的精度无法保証。严格格算法算法分枝切割法分边边定界法組合的多面体論严格算法历史(平面TSP)1954:49城
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- TSP 问题 导引 解析
限制150内