算法设计与分析20111

1、算法设计与分析2011-秋季学期秋季学期课程介绍课程介绍 教学教学参考书参考书1 M. H. Alsuwaiyel：Algorithms: Design Techniques and Analysis,电子电子工业出版社工业出版社影印本影印本, 1999.2 R.C.Lee, S.S.Tseng, Y.T.Tsai：算法设计与分析：算法设计与分析导论导论, 王王卫东译，机械卫东译，机械工业出版社，工业出版社，2005.3 Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein：算法：算法导论导论, MIT第第3

2、版版, 2009. 教学教学内容内容1. 引论引论 2. 分治法分治法 3. 动态规划动态规划 4. 集合算法集合算法5. 随机算法随机算法 6. 计算模型计算模型 7. NP完全问题完全问题 教学教学方式方式问题驱动，鼓励实验，强调探索，欣赏专栏问题驱动，鼓励实验，强调探索，欣赏专栏第一第一章：引论章：引论 两个中心问题： 旅行商问题：在一个完全网络中求长度最小的哈密尔顿回路。 0-1背包问题： 给定n种物品和一个背包，每个物品具有特定重量和价值，背包具有最大负荷重量，如何向背包中放入物品使得它们的总价值达到最大。 本学期要求对这两个问题分别至少实现4种不同的算法并分析算法效率，对特定数据记

3、录运行时间来验证你的分析。1.1 特殊算法和通用算法特殊算法的例子：例1：小明和小红共吃了m个苹果，小明比小红多吃了n个，小明和小红各吃了几个苹果？(m, n是正整数，mn)解答1 (蛮力法)：因为mn, 说明小明没把m个苹果都吃了，小明最少吃了m/2+1(向下取整)个苹果，最多吃了m-1个苹果，在这些可能中检查小明比小红多吃了几个，若多吃了n个，这就是答案。解答1的缺点：1. 若m值很大，比如10000，该方法太麻烦。(算法效率低)2. 有时无解，如m=10, n=3时, 6-4=2，7-3=4， 8-2=6，9-1=8哪个也不等于3。(算法失败)解答2(调整法)：小明和小红先平分苹果，各得

4、m/2个，然后小红给小明n/2个，结果小明吃了(m+n)/2个，小红吃了(m-n)/2个。例2：鸡兔同笼，共有头m只，腿n只，问鸡兔各几只？(m, n是正整数，n是偶数，2mn4m)解答1 (搞笑法) ：训练鸡兔听从命令，然后让它们抬起两只腿，这样鸡两脚朝天，兔如猿人两腿直立，地上还有n-2m只腿, 因此有n/2-m只兔, 2m-n/2只鸡.解答2 (调整法)：先设笼中全是鸡, 此时缺n-2m腿，然后用兔子换鸡，换一只多两条腿，共需换n/2-m只，因此有n/2-m只兔, 2m-n/2只鸡.通用算法的例子：高斯消元法解线性方程组。例1只需输入矩阵(1, 1, m/1, -1, n),例2只需输入

5、矩阵(1, 1, m/2, 4, n).结论：通用算法能顶一大堆特殊算法，所以在设计算法时应该追求算法的通用性思考题1：一个16升的容器中装满了牛奶，另外有一个6升和一个11升的空容器，如何用它们来平分牛奶？提示：这是一个隐式图搜索问题，图搜索算法应该设计成通用模块，用它可以求解一大批趣味数学题，不同的题目有不同的后继结点生成模块，但它们容易实现。例如这一类的容器分液体问题可以有下面几个变种：思考题1A: 小明拿着一个7升和一个11升的空容器来到水龙头前，他如何才能带回6升水呢？思考题1B: 小明拿着一个7升,一个13升和一个19升的空容器来到水龙头前，他如何才能在两个容器中各盛10升水呢？思

6、考题1C: 小明有两个100毫升的容器中装满了牛奶，另外有一个40毫升和一个70毫升的空碗，如何用它们在两个碗中各盛30毫升的牛奶，并且一点儿牛奶也不泼掉呢？要求：用一个通用图搜索模块和4个后继结点生成模块同时求解这4个问题，并自己找几个其它的隐式图搜索问题，如狼羊白菜过河等，利用通用图搜索模块求解。1.2 蛮力法思考题2：求一个4位数x和一个一位数y, 使得x与y的乘积z也是4位数，且x, y, z包含了所有1到9的数字。对组合问题求一个解的蛮力算法：1 生成第一个候选对象；2 While (还有候选对象)3 if (当前候选对象符合要求) break;4 else 生成下一个候选对象； 5

7、 if (还有候选对象) 输出当前候选对象；注：(1)蛮力算法可以看作通用算法，只需实现一个遍历器和检查函数；(2) 常见的候选范围包括全体允许重复的排列，全体不允许重复的排列，全体递增排列(即组合)等，全集的全体子集可以表示为允许重复的0-1排列，也可以表示为集合元素下标的全体组合。对组合问题求全体解的蛮力算法：1 生成第一个候选对象；num=0;2 While (还有候选对象)3 if (当前候选对象符合要求) 4 输出当前候选对象; +num; 4 生成下一个候选对象； 注：上述算法同时具有计数功能，如果只要求计数，只须删去输出语句。例：子集和数问题设A为正整数的集合，求A的子集, 使得

8、B的全体元素的和sum满足某个性质(广义)。例如，在一个特定的区间a, b中，当区间收缩成一个点, a, a时，即sum=a(狭义)。例: 在A=2, 7, 36, 40, 53, 59, 62, 69, 77, 80, 87, 89, 95, 98, 100, 102, 103, 106, 112, 115, a=220的情况下求狭义解时，子集40, 80, 100是一个解。优化问题的蛮力算法：1 生成第一个候选对象；2 While (还有候选对象)3 if (当前候选对象符合要求) break;4 else 生成下一个候选对象； 5 if (还有候选对象) 6 当前最小对象指向当前候选对象的拷贝；7 生成下一个候选对象；8 While (还有候选对象) 9 if (当前候选对象符合要求 &当前候选对象比当前最小对象还小)10 当前最小对象指向当前候选对象的拷贝；11 生成下一个候选对象； 12 输出当前最小对象;欣赏专栏欣赏专栏-1：循环赛日程安排：循环