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

现代优化技术 第3讲讲：现代优化技术基础之计算机基础 主要内容 计算复杂性理论 (Complexity Theory) 计算量的概念 计算量的表示 算法与计算量 算法的计算复杂性 多项式时间算法与指数时间算法 计算复杂性的影响因素 P与NP问题 计算机编程语言（Programming） 优化问题及其计算的复杂性 组合优化问题： 组合数虽然有限，但因其数量太多， 寻找最优解很难。 背包问题（knapsack problem）： n个物品, 2n实行可能解。 旅行商问题（traveling salesperson problem）： 都市n个, n!实行可能解。 用有限時間可以求解，但计算时间太长，成本太高 9 0 12 3 3 4 56 7 2 34 5 计算量的膨胀 每秒钟可以穷举24个城市的全排列 24！ 找出TSP问题最优解的所需要时间： TSP问题规模：24 25 26 27 28 29 30 31 穷举需时间： 1秒 25秒 10分 4时 5日 4.5月 11年 3.3世纪 计算量的表示 l, l比较：， l 5种基本演算都是用1step 可以实现. l 事实上,比多占用時間. l 四舍五入不算基本演算. 5种基本演算： 计算量的表示 算法计算量： 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 计算量的表示 算法计算量： Q3. 计算：a1b1+anbn. 2n-1 steps. Q4. 2个阶矩阵相乘. n2(2n-1) steps（ n2(n+n-1)） 计算量的表示 算法计算量： Q5. a1, a2,., an：n个整数 求其和为最大的部分集合. 所有的部分集合的和进行比較 2n (n-1) +(2n-1) steps 计算量的膨胀 10行10列棋盘上米粒的数量 （第1格内放1粒米，以后每格顺次增加1倍) 格序号 米粒数 重量 (kg) 1 1 2.010-5 9 256 5.110-3 18 131072 2.6100 27 67108864 1.3103 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 计算量膨胀例 计算量的膨胀 100MIPS (mega instructions per second) 1秒間100万回的計算1step 用 10-6秒 光速 3.01010cm/秒 (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世纪 计算量的膨胀的速度： 计算量的膨胀速度 计算机速度增加的效果（1） 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 13 1000倍 1step 用 10-9秒 10-9秒 光可以行进30cm 计算量的膨胀速度 计算机速度增加的效果（2） 计算速度 1秒可以求解问题的规模 2n n n2 n5 n10 1 100 100 100 100 100 2 101 200 141 115 107 10 103 1000 316 158 126 100 107 10000 1000 251 158 1000 110 100000 3162 398 200 10000 113 1000000 10000 631 251 100000 117 10000000 31623 1000 316 1000000 120 100000000 100000 1585 398 计算量的膨胀速度 平行（并列）計算的场合 0.5 cm 见方小碎片，覆盖地球表面需要 2.01019 个 与100MIPS的单个计算机相比，能加速多少？ n 100 1,000 . 2n 1014世纪 0.85 秒 10284世纪 10263世纪 n! 10141世纪 10120世纪 102551世纪 102530世纪 算法与计算量 每个問題都可能有多个算法存在 每个算法的计算量（速度）都不同。 例： 赝品金币問題： 问题：9個外观完全一样的金币.，有一个是假的 （重量轻） 提问：用天秤来鉴别真伪，天秤需要使用几次？ 算法与计算量 贋品金币問題的算法与计算量 789 23 456 左边軽 右边軽 平衡 23 中有偽币 789 中有偽币 456 中有偽币 左边軽 3 2 右边軽 平衡 32 4 56 7 89 算法复杂度的表示 算法的复杂性：空间复杂性+时间复杂性 算法复杂度的表示 空间复杂性（ space complexity）： 算法复杂度的表示 空间复杂性： 算法复杂度的表示 时间复杂性（ time complexity ）： 算法复杂度的表示 时间复杂性的渐进表示： 算法复杂度的表示 时间复杂性的渐进表示： 算法复杂度的表示 时间复杂性的渐进表示： 算法复杂度的表示 时间复杂性的渐进表示： 算法复杂度的表示 时间复杂性的渐进表示： 算法复杂度的计算 计算复杂度的表示法例 n+1000nO(n) log n+n3+1000n2 O(n3) 判断： n! O(nn)？ 10n2 O(n3)？ log n O(n)？ 思考： O()? 算法复杂度的计算 例：背包问题的贪婪算法（greedy algorithm） 的计算复杂度 多项式时间算法与指数时间算法 多项式时间算法与指数时间算法 指数時間算法 = 用问题规模的指数函数来表示計算時間(上限)的算法 非有效算法的代名詞 多項式時間算法 = 能用问题规模的多项式函数来表示計算時間（上限）的算法 高效率算法的代名詞 多项式时间算法与指数时间算法 多项式时间算法的计算时间 问题规模计算时间 10 20 30 40 50 100 1000 10000 （100MIPS计算机） 多项式时间算法与指数时间算法 问题规模 计算时间 （1宇宙龄=150亿年） 10 20 30 40 50 100 1宇宙龄=150亿年 指数时间算法的计算时间（100MIPS计算机） 指数时间算法例 旅行商问题的计算量 n 个城市可能的巡回路线： n!的Stirling近似公式 指数时间算法例 排序问题的计算量： 排序問題：S=a1, a2,., an，n個整数列， 按数值大小排列 data S 输入 需O(n) 時間； 可能的排列種類数 n!种； 算法中每一个比較,都增加 2倍的情形数 2分树的高度 （比较的次数）, log2 (n!)=O(n log n) xy? yes no n!种可能的排列 计算复杂度的影响因素 模型及建模条件 例： RL 1/2 计算复杂度的影响因素 模型1及其建模假设模型2及其建模假设模型3及其建模假设 计算复杂度的影响因素 计算复杂度的影响因素：探索空间 探索空间探索空间1 1-解的近似度、满意度 例：010之间的整数解：1-9共9个可行解（一维） 010之间的实数解：精确到小数点后6位 共有107个可行解（一维）； 107n个可行解（n维） 探索空间探索空间2 2-解空间大小 例：桌子上有6根火柴，要求构建出4个三角形。 计算复杂度的影响因素 探索策略的选取 基于计算复杂度的优化问题分类 所有优化问题 NP问题 NP完全问题 旅行商問題 背包問題 P问题 最短路問題 线性规划問題 P（polynomial）问题 NP 问题 （non-deterministic polynomial） NP完全问题 NP-complete problem NP困难问题 NP-hard problem X 问题 基于