通信网理论基础：02-关于算法

1、通信网理论基础Part 02: 关于算法(Intro to Algorithm)2013年春季2 / 30关于算法1234算法的基本概念 算法的设计方法算法的分析方法算法的应用与实现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算法的基本概念名称的来历123算法是什么算法的分类2013年春季2013年春季4 / 30Algo

2、rithm的由来Why ?因为：一个使得定量分析大众化了，另一个使得知识大众化了。1448 = MCDXLVIIIAlgorithmTo honor the wise Arabian:Al KhwarizmiAD 600十进制计数法及其符号在印度(注意，不是阿拉伯)被发明。DecimalNine CenturyAl Khwarizmi (Baghdad)写了一本介绍十进制以及相应的四则运算(甚至还包括求平方根和求PIE)方法的阿拉伯文教材。并在很多个世纪之后被介绍到了西方。Algorithm1448一个Mainz(德国城市)的金匠，Johann Gutenberg，发明了金属活字印刷。Typo

3、graphyThe 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 / CorrectWhy ?5 / 30算法是什么？求解问题的一个过程(Procedure)。算法过程由一系列步骤构成，其中每个步骤都是简单的，无歧义的

4、，容易实现的。给定任意实例，都能给出所要求的结果。求解对一系列(甚至无穷多个)实例的统一/无歧义的描述。由输入(给定条件)和输出(待求结果)组成。对一系列(甚至无穷多个)实例的统一/无歧义的描述。由输入(给定条件)和输出(待求结果)组成。问题问题给定一组整数，求其中最大值。过程比较前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)数学：算术；随机数；高斯消元；几何；求积分；曲线拟合

5、。排序(Sorting)图(Graph)其他：FFT；线性规划；等等。查找(Searching)应用2013年春季8 / 30关于算法2341算法的基本概念 算法的设计方法算法的分析方法算法的应用与实现算法的应用是如此广泛，面对的问题千奇百怪，那么，算法岂不是只能case-by-case地设计？难道其中还有些什么共同的，统一的设计方法么？2013年春季9 / 30算法的设计方法4Divide and Conquer1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季10

6、 / 30Divide and Conquer 将原问题分解为规模较小的子问题由于所有拆分出来的子问题都是相同性质的，因此可以方便地用递归(Recursion)方式来实现。Divide 如果子问题仍然困难，就继续对子问题进行分解。 直到最终分解得到的子问题变得容易“征服”(trivial)。Conquer将子问题的结果合并成原问题的解Combine例1 求最大值 在一组整数中求最大值。 分成两组，分别求最大值，然后比较这两个值，较大者作为原问题的解。 递归。例2 查找 在一组升序整数中，查找某个特定的整数。 折半查找。例3 排序 为一个序列按序排列 归并排序11 / 30 折半查找 请查错，并

7、修改 Hint : 以A = 2,5,9x = 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.yIF y x 1 THEN RETURN( max( Sx, Sy )E

8、LSE m1 = maximum( x, (x + y) / 2 ) m2 = maximum( (x + y) / 2 + 1, y ) RETURN( max( m1, m2 ) )伪码伪码2013年春季12 / 30算法的设计方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季13 / 30Dynamic Programming串行 仍然划分为子问题，但是子问题的求解不是递归进行的，而是顺序进行的(串行)。 子问题的解存储

9、在一个表中供后续的子问题求解时使用。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 Sho

10、rtest Path)。 Floyd算法。2013年春季14 / 300-1背包问题的DP算法ti,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么 ?

11、 子问题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 = TRUE02 FOR j = 1 TO K DO t0, j = FALSE03 FOR i = 1 TO n DO04 FOR j = 1 TO K DO05 t i, j = t i 1, j 06 IF j

12、 si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 2013年春季15 / 300-1背包问题的DP算法12345678910i=1s1=5i=2s2=4i=3s3=3i=4s4=6XXXXOXXXXXXOOOOOOOOXXXXXXXXXXOOOXXOOOOOO0-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,

13、 j 表课后思考：DC vs DP 我们给出了Knapsack问题的DP算法，试用DC方法构造一个算法。（Hint：递归） 你觉得这两个算法哪个更好？为什么？Function knapsack (s1, s2, , sn, K)01 t 0, 0 = TRUE02 FOR j = 1 TO K DO t0, j = FALSE03 FOR i = 1 TO n DO04 FOR j = 1 TO K DO05 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年春季1

14、6 / 30算法的设计方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季17 / 30Greedy Algorithm先从简单的子问题入手，逐步扩展(Augment)子问题的解，最终扩展为整个问题的解。扩展这种扩展是贪婪(Greedy)的。即只以当前的已知条件(可能不全面，与DP相反)为依据，只保证局部最佳，不考虑是否是全局最佳。贪婪Sometimes optimal; Sometimes pretty good; Somet

15、imes 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

16、-Knapsack (s1n, w1n, K)01 按密度对物品排序;02 m = K; i = 1;03 WHILE si m DO04 xi = 1; m = m si; i = i + 1;05 xi = m / si;06 FOR j = i + 1 TO n DO xj = 0;07 RETURN x1nWell talk about them later in this course连续背包问题 给定n个物品，体积分别为s1, s2, , sn，质量分别为w1, w2, ., wn，背包容积为K。 要求在塞满背包的同时，最小化背包的重量。 假定：允许将物品拆分为无限小的部分；且每个

17、物品的密度都是均匀的（注，不同物品密度可以不等）。 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算法的设计方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季20 / 30原

18、理穷举/枚举/遍历所有可能。从中寻求最佳解。Its always slow, then, WHY bother?Better than nothing if no other way available.May actually practical for instances with size small enough.Sometimes its not trivial at all 穷举也有技巧(例如，往往需要产生便于操作、便于排列组合的对象)可以求得最佳，作为比较的对象。技术最常用的枚举方法是借助于Divide and Conquer.Exhaustive Search2013年春季21

19、 / 30算法的设计方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季22 / 30Local Search/Metaheuristics模拟退火模拟晶体的退火过程，跳出局部最优解。遗传算法随机变异+自然选择禁忌搜索对随机的局部搜索施加一定的限制和导向。蚁群/蜂群仿生学原理神经网络人工智能Its Exciting, Its Beautiful, and Its full of Fun.2013年春季23 / 30小结纯属个人观

20、点复杂度 Exhaustive Search复杂度最高，DC和DP次之，但能保证最佳。 贪婪算法思路简洁，局部搜索应用面广。但无法保证最佳。 通信网络应用中，沿用成熟算法及其变种占多数。 需要自行设计时，优先考虑贪婪算法和局部搜索，较少考虑DC和DP。 几乎从不考虑Exhaustive Search。应用 Metaheuristic是很吸引人的研究课题研究 2014年春季24 / 30关于算法341算法的基本概念 2算法的设计方法算法的分析方法算法的应用与实现我们将学习很多算法，也将会去设计自己的算法。但是，我怎么知道这些算法真的能达到目标？另外，同样能达到相同目标的多个算法，我应该怎么选择？

21、2013年春季25 / 30测量/评估算法的耗时是很难的计算机硬件不同，OS不同，运行环境(是否存在其它进程)不同。问题实例不同：规模，输入条件对算法的影响等。算法的分析算法的正确性(Correctness) 即判断算法是否能正确求解给定的问题，或者该算法是否能针对所有的问题实例都给出最佳的解。算法的复杂度(Complexity)其目标通常是判断算法求解问题实例所需要的时间。有时是平均性能，大多数情况下是求最坏性能。Correctness 从理论上证明算法的正确性，有一个统一的证明模式，所谓Invariant方法。参考算法导论2ed。 本课程仅对少数算法，从物理意义上去讨论其正确性。分析的目标

22、2013年春季26 / 30Complexity实例不同，耗时不同？求最坏情况下的耗时。即假定所有的问题实例中使得算法执行的操作最多的作为衡量算法的依据。什么最耗时？循环。循环中操作的次数是可以确定的，只要确定循环的次数，就可以估算整个算法的耗时。怎么办？抓主要矛盾，即关注算法中最耗时的部分。操作不同，耗时不同？考虑问题规模足够大的时候。此时，不同的操作耗时上的差异不占主导地位了。问题的规模如何定义?基本上，问题中都包含了一些参数，可以描述输入信息的规模。例如，图算法中节点的数目，边的数目等。复杂度分析是要给出最坏情况下，算法的操作次数与问题规模的关系。结论注意 由于问题的规模足够大，因此可以

23、只取最高阶。忽略低阶项和常系数。 参见下面的例子。2013年春季27 / 30复杂度分析实例Function C-Knapsack (s1n, w1n, K)01 按密度对si排序;02 m = K; i = 1;03 WHILE si m DO04 xi = 1; m = m si; i = i + 1;05 xi = m / si;06 FOR j = i + 1 TO n DO xj = 0;07 RETURN x1nFunction knapsack (s1, s2, , sn, K)01 t 0, 0 = TRUE02 FOR j = 1 TO K DO t0, j = FALSE03 FOR i = 1 TO n DO04 FOR j = 1 TO K DO05 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 + KnKn 问题规模：n, K 第一个循环：3n 第二个循环：n 共计：4n注意 常用的的表达式：n, n2, log(n), n log(n), 2n, 等。 Polynomial vs. Exponenti