大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础

1、大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,1,现代优化技术,第3讲：现代优化技术基础之计算机基础,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,2,主要内容,计算复杂性理论 (Complexity Theory) 计算量的概念 计算量的表示 算法与计算量 算法的计算复杂性 多项式时间算法与指数时间算法 计算复杂性的影响因素 P与NP问题 计算机编程语言（Programming）,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,3,优化问题及其计算的复杂性,组合优化问题： 组合数虽然有限，但因其数量太多， 寻找最优解很难。 背包问题（knapsa

2、ck problem）： n个物品, 2n实行可能解。 旅行商问题（traveling salesperson problem）： 都市n个, n!实行可能解。 用有限時間可以求解，但计算时间太长，成本太高,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,4,计算量的膨胀,每秒钟可以穷举24个城市的全排列 24！,找出TSP问题最优解的所需要时间：,TSP问题规模：24 25 26 27 28 29 30 31 穷举需时间： 1秒 25秒 10分 4时 5日 4.5月 11年 3.3世纪,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,5,计算量的表示, 比较：，

3、5种基本演算都是用1step 可以实现. 事实上,比多占用時間. 四舍五入不算基本演算.,5种基本演算：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,6,计算量的表示,算法计算量：,a1, a2,., an：n个整数 Q1. 求和（1）： a1+a2+an. n-1 steps Q2. 求和（2）： (1) 2a1+ 2an , 2n-1 steps (2) 2(a1+an) , n steps,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,7,计算量的表示,算法计算量：,Q3. 计算：a1b1+anbn. 2n-1 steps. Q4. 2个阶矩阵相乘. n

4、2(2n-1) steps（ n2(n+n-1)）,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,8,计算量的表示,算法计算量：,Q5. a1, a2,., an：n个整数 求其和为最大的部分集合. 所有的部分集合的和进行比較 2n (n-1) +(2n-1) steps,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,9,计算量的膨胀,10行10列棋盘上米粒的数量 （第1格内放1粒米，以后每格顺次增加1倍) 格序号 米粒数 重量 (kg) 1 1 2.010-5 9 256 5.110-3 18 131072 2.6100 27 67108864 1.3103

5、36 34359738368 6.9 105 45 17592186044416 3.5 108 54 9007199254740992 1.8 1011 63 4611686018427387904 9.21013 72 2361183241434822606848 4.7 1016 81 1208925819614629174706176 2.4 1020,计算量膨胀例,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,10,计算量的膨胀,100MIPS (mega instructions per second) 1秒間100万回的計算1step 用 10-6秒 光速 3.0

6、1010cm/秒 (10-6秒 行进300m) n 10 100 1,000 10,000 n 10-5秒 10-4秒 10-3秒 0.01秒 n2 10-4秒 0.01秒 1秒 100秒 n3 0.001秒 1秒 16.6分 277时 2n 0.001秒 1014世紀 10284世紀 n! 0.036秒 10141世紀 102551世纪,计算量的膨胀的速度：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,11,计算量的膨胀速度,计算机速度增加的效果（1）,10秒钟的计算量？ 100MIPS 10倍 100倍 1000倍 n 107 108 109 1010 n2 3千 1万

7、3万 10万 n3 215 462 1千 2千 2n 23 27 30 33 n! 10 11 12 13 1000倍 1step 用 10-9秒 10-9秒 光可以行进30cm,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,12,计算量的膨胀速度,计算机速度增加的效果（2）,计算速度 1秒可以求解问题的规模 2n n n2 n5 n10 100 100 100 100 100 101 200 141 115 107 103 1000 316 158 126 107 10000 1000 251 158 110 100000 3162 398 200 113 1000000 1

8、0000 631 251 100000 117 10000000 31623 1000 316 1000000 120 100000000 100000 1585 398,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,13,计算量的膨胀速度,平行（并列）計算的场合,0.5 cm 见方小碎片，覆盖地球表面需要 2.01019 个 与100MIPS的单个计算机相比，能加速多少？ n 100 1,000 . 2n 1014世纪 0.85 秒 10284世纪 10263世纪 n! 10141世纪 10120世纪 102551世纪 102530世纪,大连海事大学现代优化技术第3讲：现代优

9、化技术基础之计算机基础,14,算法与计算量,每个問題都可能有多个算法存在 每个算法的计算量（速度）都不同。 例： 赝品金币問題： 问题：9個外观完全一样的金币.，有一个是假的 （重量轻） 提问：用天秤来鉴别真伪，天秤需要使用几次？,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,15,算法与计算量,贋品金币問題的算法与计算量,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,16,算法复杂度的表示,算法的复杂性：空间复杂性+时间复杂性,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,17,算法复杂度的表示,空间复杂性（ space complexity）

10、：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,18,算法复杂度的表示,空间复杂性：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,19,算法复杂度的表示,时间复杂性（ time complexity ）：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,20,算法复杂度的表示,时间复杂性的渐进表示：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,21,算法复杂度的表示,时间复杂性的渐进表示：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,22,算法复杂度的表示,时间复杂性的渐进表示：,大连海事大学现代优化技术第3

11、讲：现代优化技术基础之计算机基础,23,算法复杂度的表示,时间复杂性的渐进表示：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,24,算法复杂度的表示,时间复杂性的渐进表示：,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,25,算法复杂度的计算,计算复杂度的表示法例,n+1000nO(n) log n+n3+1000n2 O(n3) 判断： n! O(nn)？ 10n2 O(n3)？ log n O(n)？ 思考：,O()?,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,26,算法复杂度的计算,例：背包问题的贪婪算法（greedy algorit

12、hm） 的计算复杂度,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,27,多项式时间算法与指数时间算法,多项式时间算法与指数时间算法,指数時間算法 = 用问题规模的指数函数来表示計算時間(上限)的算法,非有效算法的代名詞,多項式時間算法 = 能用问题规模的多项式函数来表示計算時間（上限）的算法,高效率算法的代名詞,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,28,多项式时间算法与指数时间算法,多项式时间算法的计算时间,（100MIPS计算机）,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,29,多项式时间算法与指数时间算法,1宇宙龄=150亿年

13、,指数时间算法的计算时间,（100MIPS计算机）,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,30,指数时间算法例,旅行商问题的计算量,n 个城市可能的巡回路线：,n!的Stirling近似公式,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,31,指数时间算法例,排序问题的计算量：,排序問題：S=a1, a2,., an，n個整数列， 按数值大小排列 data S 输入 需O(n) 時間； 可能的排列種類数 n!种； 算法中每一个比較,都增加 2倍的情形数 2分树的高度 （比较的次数）, log2 (n!)=O(n log n),大连海事大学现代优化技术第3

14、讲：现代优化技术基础之计算机基础,32,计算复杂度的影响因素,模型及建模条件 例：,R,L,1/2,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,33,计算复杂度的影响因素,模型1及其建模假设,模型2及其建模假设,模型3及其建模假设,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,34,计算复杂度的影响因素,计算复杂度的影响因素：探索空间,探索空间1-解的近似度、满意度 例：010之间的整数解：1-9共9个可行解（一维） 010之间的实数解：精确到小数点后6位 共有107个可行解（一维）； 107n个可行解（n维） 探索空间2-解空间大小 例：桌子上有6根火柴，要求构建出4个三角形。,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,35,计算复杂度的影响因素,探索策略的选取,大连海事大学现代优化技术第3讲：现代优化技术基础之计算机基础,36,基于计算复杂度的优化问题分类,所有优化问题,NP问题,NP完全问题 旅行商問題 背包問題 ,P问题 最短路問題 线性规划問題 ,P（polynomial）问题,NP 问题 （non-deterministic polynomial）,NP完全问题 NP-complete problem NP困难问题 NP-hard problem,X 问题,大连海事大学现代优化技术第3