通信网络理论基础-关于算法.pptx

通信网理论基础 虞红芳 教授 博导 Part 02: 关于算法(Intro to Algorithm) 2013年春季 2 / 30 关于算法 1 2 3 4 算法的基本概念 算法的设计方法 算法的分析方法 算法的应用与实现 Algorithms are the “stuff” of computer science: they are central objects of study in many, if not most, areas of the field. - ROBERT SEDGEWICK “Algorithms” 3 / 30 算法的基本概念 名称的来历 1 2 3 算法是什么 算法的分类 2013年春季 2013年春季 4 / 30 Algorithm的由来 Why ? 因为：一个使得定量分析大众化了， 另一个使得知识大众化了。 1448 = MCDXLVIII Algorithm To honor the wise Arabian: Al Khwarizmi AD 600 十进制计数法及其符号在 印度(注意，不是阿拉伯) 被发明。 Decimal Nine Century Al Khwarizmi (Baghdad)写了一本介绍 十进制以及相应的四则运 算(甚至还包括求平方根 和求PIE)方法的阿拉伯文 教材。并在很多个世纪之 后被介绍到了西方。 Algorithm 1448 一个Mainz(德国城市)的 金匠，Johann Gutenberg，发明了金属 活字印刷。 Typography The Dark Ages ended, the human intellect was liberated, science and technology triumphed, the Industrial Revolution happened. Two ideas changed the world 因为那些计算方法具有“算法”的一切特征： Precise / Unambiguous / Mechanical / Efficient / Correct Why ? 5 / 30 算法是什么？ 求解问题的一个过程(Procedure)。 算法 过程 由一系列步骤构成 ，其中每个步骤都 是简单的，无歧义 的，容易实现的。 给定任意实例， 都能给出所要求 的结果。 求解 对一系列(甚至无 穷多个)实例的统 一/无歧义的描 述。由输入(给定 条件)和输出(待求 结果)组成。 对一系列(甚至无 穷多个)实例的统 一/无歧义的描 述。由输入(给定 条件)和输出(待求 结果)组成。 问题 问题问题给定一组整数，求其中最大值。 过程过程比较前2个数的大小，较大者与第3个比； 例子 2013年春季 6 / 30 历史上三大算法 1、求最大公约数的欧几里得算法 2、求素数的埃拉托塞尼筛法 3、求方根的开方算法 X_(n+1)=X_n+【A/(X_n（k-1）)-X_n】1/k 7 / 30 算法的分类 串处理(String) 数学： 算术；随机数；高斯消元； 几何；求积分；曲线拟合。 排序(Sorting) 图(Graph) 其他： FFT；线性规划；等等。 查找(Searching) 应用 2013年春季 8 / 30 关于算法 2 3 4 1算法的基本概念 算法的设计方法 算法的分析方法 算法的应用与实现 算法的应用是如此广泛，面对的问题千奇百怪，那么，算法 岂不是只能case-by-case地设计？难道其中还有些什么共 同的，统一的设计方法么？ 2013年春季 9 / 30 算法的设计方法 4 Divide and Conquer 1 2 3 5 Dynamic Programming Greedy Algorithm Exhaustive Search Local Search/Metaheuristic 2013年春季 10 / 30 Divide and Conquer 将原问题分解为 规模较小的子问题 由于所有拆分出 来的子问题都是相 同性质的，因此可 以方便地用递归 (Recursion)方 式来实现。 Divide 如果子问题仍然困 难，就继续对子问 题进行分解。 直到最终分解得到 的子问题变得容易“ 征服”(trivial)。 Conquer 将子问题的结果合 并成原问题的解 Combine 例1 求最大值 在一组整数中求最大值。 分成两组，分别求最大值，然后比较这两个 值，较大者作为原问题的解。 递归。 例2 查找 在一组升序整数 中，查找某个特 定的整数。 折半查找。 例3 遍历 在图中遍历所有 的节点。 深度优先遍历 ( DFS) 2013年春季 11 / 30 折半查找 请查错，并修改 Hint : 以A = 2,5,9 x = 5为例来思考。 伪码及实例 Function search (A, x, k, r) / find x in A k.r IF k = r THEN RETURN( k ) ELSE m = (k + r) / 2 IF x A m THEN RETURN( search( A, x, k, m) ) ELSE RETURN( search( A, x, m, r) 基于DC的求最大值 Function maximum( S, x, y ) / return maximum in Sx.y IF y x 1 THEN RETURN( max( Sx, Sy ) ELSE m1 = maximum( x, (x + y) / 2 ) m2 = maximum( (x + y) / 2 + 1, y ) RETURN( max( m1, m2 ) ) 伪码 伪码 2013年春季 12 / 30 算法的设计方法 4 Divide and Conquar 1 2 3 5 Dynamic Programming Greedy Algorithm Exhaustive Search Local Search/Metaheuristic 2013年春季 13 / 30 Dynamic Programming 串行 仍然划分为子问 题，但是子问题的 求解不是递归进行 的，而是顺序进行 的(串行)。 子问题的解存储 在一个表中供后续 的子问题求解时使 用。 Dynamic Programming is a fancy name for Divide and Conquer with a TABLE. 要点 要正确地设计各 个子问题的求解顺 序。 目的是保证：求 解某个子问题时如 果需要用到其他子 问题的解，那个解 已经在表中了。 用途 用DC方法分解出 的子问题数目很大 ，而且要反复用到 相同的子问题的 解。 例1 0-1背包问题 给定n个物品，体积分别为s1, s2, , sn，背包容积为K。 问，是否存在一组物品，其体 积之和刚好为K。即刚好能塞满 背包。 例2 所有最短路 求给定图中，所有节点对之间的 最短路径( All Pair Shortest Path)。 Floyd算法。 2013年春季 14 / 30 0-1背包问题的DP算法 ti,jti,j 表示前 i 个物品是否能组合成 j 这么大的 体积。如果能，该变量为TRUE；否则为 FALSE。 思考 “n个物品能否组合 成体积K”这个问题可 以分解为两个子问题 ： 子问题1：前n 1 个 物品能否组合成体积K ? 子问题2：前n 1 个 物品能否组合成体积 K sn ? 显然，只要任一答 案为TRUE，那么原 问题就为TRUE。 继续思考 子问题1可以分解为 子问题3：前n 2个能 否组成体积K? 子问题4：前n 2个能 否组成K sn-1? 子问题2可以分解为 子问题5：t n 2, K sn 为TRUE么 ? 子问题6：t n 2, K sn sn-1 为TRUE么? 干脆 . si可能取任何值，所以干脆不是问某个 特定的体积，而是问所有的体积： ti,1? ti,2?.ti,K? 并且反过来计算，计算完t1, 1K，再 来计算t2, 1K. 这样一来，后续计算所需要问的那些子 问题都已经求解并记录下来了。 Function knapsack (s1, s2, , sn, K) 01 t 0, 0 = TRUE 02 FOR j = 1 TO K DO t0, j = FALSE 03 FOR i = 1 TO n DO 04 FOR j = 1 TO K DO 05 t i, j = t i 1, j 06 IF j si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 2013年春季 15 / 30 0-1背包问题的DP算法 12345678910 i=1 s1=5 i=2 s2=4 i=3 s3=3 i=4 s4=6 XXXXO XXXX XX OOO O OO OO XXXXX XXX XXOOO XXOOOOOO 0-1背包问题的一个实例 n = 4，即有4个物品 体积分别为 5，4，3，6 K = 10，即背包容积为10 下面我们来填t i, j 表 课堂作业1：另一个实例 n = 8，体积分别为 15，5，16，7，1，15，6，3 K = 19，即背包容积为19 请填t i, j 表 课后思考：DC vs DP 我们给出了Knapsack问题的DP算法，试用DC方法构造一 个算法。（Hint：递归） 你觉得这两个算法哪个更好？为什么？ Function knapsack (s1, s2, , sn, K) 01 t 0, 0 = TRUE 02 FOR j = 1 TO K DO t0, j = FALSE 03 FOR i = 1 TO n DO 04 FOR j = 1 TO K DO 05 t i, j = t i 1, j 06 IF j si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 2013年春季 16 / 30 算法的设计方法 4 Divide and Conquar 1 2 3 5 Dynamic Programming Greedy Algorithm Exhaustive Search Local Search/Metaheuristic 2013年春季 17 / 30 Greedy Algorithm 先从简单的子问题入手，逐步扩展(Augment)子问 题的解，最终扩展为整个问题的解。 扩展 这种扩展是贪婪(Greedy)的。即只以当前的已知 条件(可能不全面，与DP相反)为依据，只保证局 部最佳，不考虑是否是全局最佳。 贪婪 Sometimes optimal; Sometimes pretty good; Sometimes lousy. But, always faster and easier (at least than DP). 性能 The trick is to determine when to be greedy. 要点 2013年春季 18 / 30 贪婪算法的例子 1 连续背包问题。 2 最短路问题。 Dijkstra算法 (Label Setting) 3 最小生成树问题。 Prim算法； Kruskal算法 基于贪婪算法的求解思路 核心思想：在体积一定的情况下，要减少重量，只有降 低密度。 怎样才能保证密度最小？ 先塞密度最小的；塞完了如果还空，就塞密度次小的。 直至最后，只能塞某个物品的一部分。 Function C-Knapsack (s1n, w1n, K) 01 按密度对si排序; 02 m = K; i = 1; 03 WHILE si m DO 04 xi = 1; m = m si; i = i + 1; 05 xi = m / si; 06 FOR j = i + 1 TO n DO xj = 0; 07 RETURN x1n Well talk about them later in this course 连续背包问题 给定n个物品，体积分别为s1, s2, , sn，质量分别为w1, w2, ., wn， 背包容积为K。 要求在塞满背包的同时，最小化背包的重量。 假定：允许将物品拆分为无限小的部分；且每个物品的密度都是均匀的 （注，不同物品密度可以不等）。 Continuous Knapsack 数学描述：求一组实数x1, x2, , xn，0 xi 1。 使得 xi si = K，且 xi wi 最小。 一个实例 K = 20; n = 5; s15 = 9, 5, 7, 12, 3; w15 = 4, 4, 8, 5, 1; 2013年春季 19 / 30 算法的设计方法 4 Divide and Conquar 1 2 3 5 Dynamic Programming Greedy Algorithm Exhaustive Search Local Search/Metaheuristic 2013年春季 20 / 30 原理 穷举/枚举/遍历所有可能。从中寻求最佳解。 Its always slow, then, WHY bother? 1.Better than nothing if no other way available. 2.May actually practical for instances with size small enough. 3.Sometimes its not trivial at all 穷举也有技巧(例如，往往需要 产生便于操作、便于排列组合的对象) 4.可以求得最佳，作为比较的对象。 技术 最常用的枚举方法是借助于Divide and Conquer. Exhaustive Search 2013年春季 21 / 30 算法的设计方法 4 Divide and Conquar 1 2 3 5 Dynamic Programming Greedy Algorithm Exhaustive Search Local Search/Metaheuristic 2013年春季 22 / 30 Local Search/Metaheuristics 模拟退火 模拟晶体的退 火过程，跳出 局部最优解。 遗传算法 随机变异+自然 选择 禁忌搜索 对随机的局部搜 索施加一定的限 制和导向。 蚁群/蜂群 仿生学原理 神经网络 人工智能 Its Exciting, Its Beautiful, and Its full of Fun. 2013年春季 23 / 30 小结纯属个人观点 复杂度 Exhaustive Search复杂度最高， DC和DP次之，但能保证最佳。 贪婪算法思路简洁，局部搜索应 用面广。但无法保证最佳。 通信网络应用中，沿用成熟算法及其变种 占多数。 需要自行设计时，优先考虑贪婪算法和局 部搜索，较少考虑DC和DP。 几乎从不考虑Exhaustive Search。 应用 Metaheuristic是最吸引人的研究课题研究 2013年春季 24 / 30 关于算法 3 4 1算法的基本概念 2算法的设计方法 算法的分析方法 算法的应用与实现 我们将学习很多算法，也将会去设计自己的算法。但是，我 怎么知道这些算法真的能达到目标？另外，同样能达到相同 目标的多个算法，我应该怎么选择？ 2013年春季 25 / 30 测量/评估算法的耗时 是很难的 1.计算机硬件不同， OS不同，运行环境 (是否存在其它进程 )不同。 2.问题实例不同：规 模，输入条件对算 法的影响等。 算法的分析 算法的正确性 (Correctness) 即判断算法是否能正确 求解给定的问题，或者 该算法是否能针对所有 的问题实例都给出最佳 的解。 算法的复杂度 (Complexity) 其目标通常是判断算法 求解问题实例所需要的 时间。有时是平均性能 ，大多数情况下是求最 坏性能。 Correctness 从理论上证明算法的正确性，有一个统一的证明模式，所谓Invariant 方法。参考算法导论2ed。 本课程仅对少数算法，从物理意义上去讨论其正确性。 分析的目标 2013年春季 26 / 30 Complexity 实例不同，耗时不同？ 求最坏情况下的耗 时。即假定所有的问 题实例中使得算法执 行的操作最多的作为 衡量算法的依据。 什么最耗时？ 循环。循环中操作的 次数是可以确定的， 只要确定循环的次数 ，就可以估算整个算 法的耗时。 怎么办？ 抓主要矛盾，即关注 算法中最耗时的部 分。 操作不同，耗时不同？ 考虑问题规模足够大 的时候。此时，不同 的操作耗时上的差异 不占主导地位了。 问题的规模如何定义? 基本上，问题中都包 含了一些参数，可以 描述输入信息的规 模。例如，图算法中 节点的数目，边的数 目等。 复杂度分析是要给出最坏情 况下，算法的操作次数与问 题规模的关系。 结论 注意 由于问题的规模足够大， 因此可以只取最高阶。忽略 低阶项和常系数。 参见下面的例子。 2013年春季 27 / 30 复杂度分析实例 Function C-Knapsack (s1n, w1n, K) 01 按密度对si排序; 02 m = K; i = 1; 03 WHILE si m DO 04 xi = 1; m = m si; i = i + 1; 05 xi = m / si; 06 FOR j = i + 1 TO n DO xj = 0; 07 RETURN x1n Function knapsack (s1, s2, , sn, K) 01 t 0, 0 = TRUE 02 FOR j = 1 TO K DO t0, j = FALSE 03 FOR i = 1 TO n DO 04 FOR j = 1 TO K DO 05 t i, j = t i 1, j 06 IF j si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 问题规模：n, K 第一个循环：K个操作； 第二个循环：循环体包 括赋值、判断和“或”3个操 作，循环nK次。 共计：3nK + K nKnK n n 问题规模：n, K 第一个循环：3n 第二个循环：n 共计：4n 注意 常用的的表达式：n, n2, log(n), n log(n), 2n, 等。