算法导论学习方法

算法导论学习方法 算法导论学习方法 篇一: 算法导论学习报告算 法 设 计 与 分 析 学 习 报 告1 第一部分 学习内容归纳―计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为 所要求的输出的过程， 或者说， 算法是对计算机上执行的计算过程的具体描述。‖ (参考文献: 百度百科) 《算法设计与》是一门面向设计，在计算机科学中 处于核心地位的课程。这门课程主要讲授了在计算机应用中经常遇到的问题和求 解的方法，分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法 复杂性的分析，以及计算理论简介。第一部分―概论和数学准备‖在简单了解了算法的基本概念和复杂性、研究 步骤等几个重要知识点后，着重学习了算法的数学基础，包括生成函数、差方方 程的求解等，主要适用于求解算法的时间复杂性。―任何可以用计算机求解的问题‎‎所需要的计算时间都与其规模有关:算法设计与分析》是一门面向设计，在计算机科学中 处于核心地位的课程。这门课程主要讲授了在计算机应用中经常遇到的问题和求 解的方法，分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法 复杂性的分析，以及计算理论简介。第一部分―概论和数学准备‖在简单了解了算法的基本概念和复杂性、研究 步骤等几个重要知识点后，着重学习了算法的数学基础，包括生成函数、差方方 程的求解等，主要适用于求解算法的时间复杂性。―任何可以用计算机求解的问题所需要的计算时间都与其规模有关》 ——分治法就运用了这样的思想。分治法的要领在于 Divide(子问题的划分) -Conquer(子问题的求解)-Combine(子问题解的组合) 。由于子问题和原 递归的思想在分治法中显得尤其重要，它们经常同时运用在算法问题 是同类的， 设计 中。这部分内容从 Select(求第 k 小元)算法，寻找最近点对算法和快速傅立 叶变换 FFT 等实际应用中深化对分治法思想的理解， 同时也强调了平衡思想的重 要性。第三部分―动态规划‖与分治法类似，同样是把问题层层分解成规模越来越 小的同类型的子问题。但与分治法不同的是，分治法中的子问题通常是相互独立 的， 而动态规划法中的子问题很多都是重复的，因此通常采用递推的方法以避免 重复计算。然而，也不是所有的情况下都采用递推法，当有大量的子问题无需求 解时， 更好的方式是采用动态规划法的变形——备忘录方法。通常需要用到动态 规划法求解的问题都具有子问题的高度重复性和最优子结构性质两大特征， 这也 是我们分析问题和设计算法时的关键点。最长公共子序列 LCS 问题和最优二分搜 索树就是从动态规划法的两个主要特征角度分析问题， 进而设计出相应的解决算 法的。而这部分内容中的另一个问题——流水作业调度，则告诉我们采用动态规 划时偶尔也得不到高效的算法，我们要学会将已有的知识灵活运用，适当加工。第四部分 ―集合算法‖中首先介绍了一种分析算法复杂度的手法——平摊分 析(Amortized Analysis) 。与之前我们所接触的算法分析方法即逐一考虑执行 每条指令所需的时间复杂度再进行累加的方法不同， 平摊分析是对若干条指令从 整体角度考虑其时间复杂度， 通过这样的方法获得的时间复杂度更加贴近实际的 情况。平摊分析的主要方法有聚集方法，会计方法和势能方法。聚集方法将指令 的时间复杂度分类计算再相加; 会计方法采用了耗费提前计算的思想;势能方法 引入了势函数的概念， 从每步操作的数据结构状态和势函数的关系角度分析得出 操作的平摊代价。―集合算法‖这一部分主要分析了 Union(合并集合)和 Find (给出元素所在集合名)这两种运算。从上学期的《数据结构》课程的学习中， 我们就已经发现集合和树之间的关系是密不可分的， 我们经常用树结构来表示集 合。2-3 树是一种特殊的每个内结点都只有 2 个或 3 个儿子的树，广泛的应用 而 于可实现 Member(查找) 、Insert(插入) 、Delete(删除)操作的数据结构— —字典，可实现 Insert、Delet e、Union 和 Min(查找最小叶结点)的数据结构 ——可并堆，可实现 Insert、Delet e、Fin d、Concatenate(保序合并)和 Split2 (分裂)的数据结构——可连接队列等。之前讨论的算法中每一步计算步骤都是确定的，然而第五部分―随机算法‖ 中所讨论的随机化算法允许算法在执行的过程中随机的选择下一个执行步骤。―在许多情况下， 当算法在执行过程中面临一个选择时，随机性选择常比最优选 择省时。因此随机化算法可在很大程度上降低算法的复杂度。(参考文献:数据结构》课程的学习中， 我们就已经发现集合和树之间的关系是密不可分的， 我们经常用树结构来表示集 合。2-3 树是一种特殊的每个内结点都只有 2 个或 3 个儿子的树，广泛的应用 而 于可实现 Member(查找) 、Insert(插入) 、Delete(删除)操作的数据结构— —字典，可实现 Insert、Delet e、Union 和 Min(查找最小叶结点)的数据结构 ——可并堆，可实现 Insert、Delet e、Fin d、Concatenate(保序合并)和 Split2 (分裂)的数据‎‎结构——可连接队列等。之前讨论的算法中每一步计算步骤都是确定的，然而第五部分―随机算法‖ 中所讨论的随机化算法允许算法在执行的过程中随机的选择下一个执行步骤。―在许多情况下， 当算法在执行过程中面临一个选择时，随机性选择常比最优选 择省时。因此随机化算法可在很大程度上降低算法的 会得到完全不同的效果， 这是它的基本特征——算法在执复杂度。(参考文献》 行时产生真正随机的结 果。一般情况下， 随即算法分为两大类——Las Vegas 算法和 Monte Carlo 算法。Las Vegas 算法不会得到不准确的结果，但有时却会找不到解，这时就需要重复 调用算法进行计算。而 Monte Carlo 算法用来求取问题的准确解。它能保证求得 一个截但无法保证其正确性，这是 Monte Carlo 算法的主要缺点。不过由于每次 执行的算法都是独立的， 通过反复执行算法可以有效的将发生错误的概率大大降 低。另外， 对于一个已经有了平均性质较好的确定性算法的问题， 通过 Sherwood 随机化方法可将确定性算法改成随机算法， 以解决其在最坏情况下效率不高的问 题， 提高了算法的性能。随机化算法为很多用确定性算法难以很好的解决的难解 问题提供了高效的解决途径，具有很高的实用价值。第六部分―NP 完全性理论与近似算法‖首先介绍了计算模型、确定性和非 确定性图灵(Turing)机。―在进行问题的计算复杂性分析之前，首先必须建立 求解问题所用的计算模型， 包括定义该计算模型中所用的基本运算，其目的是使 问题的计算复杂性分析有一个共同的客观尺度。(参考文献: ‖ 《计算机算法设计 与分析(第 3 版))随机存取机 RAM(Random Access Machine) 》 、随机存取存储 程序机 RASP Random Access Stored Program Machine) ( 和图灵机 (Turing Machine) 是三种基本的计算模型。RAM 和 RASP 的相同处在于都有各种寻址指令且时间复 杂性数量级相同，不同处在于 RAM 程序的不允许修改和 RASP 程序的可修改性。RAM 程序和 RASP 程序之间可以相互模拟。图灵机可以计算函数部分的递归函数， 涉及到递归可枚举集、递归集、原始递归集、部分递归函数、完全递归函数和原 始递归函数。确定性图灵机 DTM 和非确定性图灵机 NDTM 的差别在于，NDTM 的每 一步动作允许有若干个选择，且它的 ID 序列通常是由树描述的，而 DTM 的 ID 序列是线性的。这部分接着又进一步深入介绍 NP 完全性理论和解 NP 难问题的近 似算法。是能在多项式时间内被一台 NDTM 所接受的语言。NP 完全问题是当前 NP 计算机算法领域的热点研究课题。第二部分 学习学习之初刚开始看到那些函数以及一大堆数学公式的时候都觉得头大， 一时 都摸不清这些复杂的式子是用来干什么的， 甚至都以为学的不是算法而是高数了。后来在接触到分治法等算法思想后， 在老师讲解的例子中学会了对那些式子的应 用。课后也在实际的应用中真正掌握了第一部分所讲的数学知识，懂得了那些数 学基础对算法研究的重要性。所以说，只有当自己学会在问题中运用了，才算是 真正学会了那些知识。算法的思想看着都似乎简单易懂， 就算思路复杂的只要认真研究也比较容易 理解， 但要真正的在实验中、 在实际问题的解决过程中运用出来就不是那么容易 的一件事了。对于同一个问题，往往都有好几种不同的算法，就像要求分别运用3 KMP、Monte Carlo、Las Vegas 算法解决同一个问题的实验二一样。每种算法都 有各自的优缺点，需要我们从算法的准确性和时间复杂度等多个方面进行权衡， 从而找到最优的算法。第三部分 个人建议一直以来都习惯于老师用 PPT 或者 PDF 课件上课， 个人觉得上课看着屏幕上 的 Word 文档有点不大适应。特别是刚开始上课讲函数的时候，那部分知识涉及 比较复杂的数学计算， 看得比较吃力。所以建议老师或许可以改用 PPT 课件作为 教学的辅助工具，这样我们课后打印课件进行复习的时候也会方便一点。另外，对于课后老师布置的实验题，做起来有难度而且很容易出现错误，耗 费了不少时间。我觉得可以专门在机房上几堂实验课，大家在实验中碰到错误可 以及时的请教老师或者和同学讨论。第四部分 报告总结继上学期《数据结构与算法》课程的学习后，在《算法设计与分析》这门课 程中我又更深入的学习了几种算法常用技术， 学会了运用这些典型方法设计算法 和反洗算法的效率。将来不管是继续读研还是工作，对算法的理解和研究都是十 分重要 的。因此，在今后的学习和研究中，我也会继续对算法的重视。在最后， 也要感谢邓老师继《专业导论》后对我们这门课的辛苦教授。4 篇二:计算机算法设计 与分析(第 3 版))随机存取机 RAM(Random Access Machine) 》 、随机存取存储 程序机 RASP Random Access Stored Program Machine) ( 和图灵机 (Turing Machine) 是三种基本的计算模型。RAM 和 RASP 的相同处在于都有各种寻址指令且时间复 杂性数量级相同，不同处在于 RAM 程序的不允许修改和 RASP 程序的可修改性。RAM 程序和 RASP 程序之间可以相互模拟。图灵机可以计算函数部分的递归函数， 涉及到递归可枚举集、递归集、原始递归集、部分递归函数、完全递归函数和原 始递归函数。确定性图灵机 DTM 和非确定性图灵机 NDTM 的差别在于，NDTM 的每 一步动作允许有若干个选择，且它的 ID 序列通常是由树描述的，而 DTM 的 ID 序列是线性的。这部分接着又进一步深入介绍 NP 完全性理论和解 NP 难问题的近 似算法。是能在多项式时间内被一台 NDTM 所接受的语言。NP 完全问题是当前 NP 计算机算法领域的热点研究课题。第二部分 学习心得学习之初刚开始看到那些函数以及一大堆数学公式的时候都觉得头大， 一时 都摸不清这些复杂的式子是用来干什么的， 甚至都以为学的不是算法而是高数了。后来在接触到分治法等算法思想后， 在老师讲解的例子中学会了对那些式子的应 用。课后也在实际的应用中真正掌握了第一部分所讲的数学知识，懂得了那些数 学基础对算法研究的重要性。所以说，只有当自己学会在问题中运用了，才算是 真正学会了那些知识。算法的思想看着都似乎简单易懂， 就算思路复杂的只要认真研究也比较容易 理解， 但要真正的在实验中、 在 运用出来就不是那么容易 的一件事了。对于同一个问题，实际问题的解决过程中 往往都有好几种不同的算法，就像要求分别运用3 KMP、Monte Carlo、Las Vegas 算法解决同一个问题的实验二一样。每种算法都 有各自的优缺点，需要我们从算法的准确性和时间复杂度等多个方面进行权衡， 从而找到最优的算法。第三部分 个人建议一直以来都习惯于老师用 PPT 或者 PDF 课件上课， 个人觉得上课看着屏幕上 的 Word 文档有点不大适应。特别是刚开始上课讲函数的时候，那部分知识涉及 比较复杂的数学计算， 看得比较吃力。所以建议老师或许可以改用 PPT 课件作为 教学的辅助工具，这样我们课后打印课件进行复习的时候也会方便一点。另外，对于课后老师布置的实验题，做起来有难度而且很容易出现错误，耗 费了不少时间。我觉得可以专门在机房上几堂实验课，大家在实验中碰到错误可 以及时的请教老师或者和同学讨论。第四部分 报告总结继上学期《数据结构与算法》课程的学习后，在《算法设计与分析》这门课 程中我又更深入的学习了几种算法常用技术， 学会了运用这些典型方法设计算法 和反洗算法的效率。将来不管是继续读研还是工作，对算法的理解和研究都是十 分重要 的。因此，在今后的学习和研究中，我也会继续对算法的重视。在最后， 也要感谢邓老师继《专业导论》后对我们这门课的辛苦教授。4 篇二》，还有几个‖大神‖推荐计算机程序设计艺术 (现在我疑心他们是否翻过这 些书)，草草的翻了下这两本书发现实在看不懂，但幸运的是 我在无意中发现了 豆瓣这个神奇的网站， 里面有很多质量不错的书评， 于是我就把评价很高 而且看上去不那么吓人的计算机书籍都买了下来——事实证明豆瓣要比这些‖学长‖或是‖ 大神‖靠谱的多得多。数据结构与算法分析——C 语言描述数据结构与算法分析——C 语言描述是我学习数据结构的第一本书: 当时有很多地方看不 懂，于是做记号反复看;代码看不明白，于是抄到本子上反复研读;一些算法想不通，就把 它所有的中间状态全画 出来然后反复推演。事实证明尽管这种学习方法看起来傻逼而且效 率很低，但对于当时同样傻逼的我却效果不错——傻人用傻办法嘛，而且这本书的课后题 大多都是 经典的面试题目，以至于日后我看到编程之美的第一反应就是这货的题目不全是 抄别人的么。至今记得，这本书为了说明算法是多么重要，在开篇就拿最大子序列和作为例子，一路把复 杂度从 O(N3)杀到 O(N2)再到 O(NlgN)最后到 O(N)， 当时内心真的是景仰之情=如滔滔江 水连绵不绝，尼玛为何可以这么屌， 此外， 我当时还把这本书里图算法之前的数据结构全手打了一遍， 后来找实习还颇为自得的 把这件事放到简历里，现在想想真是傻逼无极限。凭借这个读书成长中学到的知识，我总算比较顺利的找到了一份实习工作，这是后话。入门 我的实习并没有用到什么算法(现在看来就是不停的堆砌已有的 API，编写一堆自己都不知 道对不对的代码而已)，在发现身边的人工作了几年却还在和我做同样的事情之后，我开始 越来越不安。尽管当时我对自己没什么规划，但我清楚这绝壁不是我想做的工作。微软的梦工厂 在这个摇摆不定的时刻， 微软的梦工场成了压倒骆驼的最后一支稻草， 这本书对微软亚洲研 究院的描写让我下定了‖找工作就要这样的公司‖的决心，然而我又悲观的发现无论是以我 当时的能力还是文凭，都无法达到微软亚研院的要求，矛盾之下，我彻底推翻了自己‖毕业 就工作‖的想法，辞掉实习，准备考研。考研的细节无需赘述， 但至今仍清楚的记得自己在复试时惊奇且激动的发现北航宿舍对面就 是微软西格玛大厦，那种离理想又进了一步的感觉简直爽到爆。算法设计与分析 我的研究生生涯绝对是一个反面典型——翘课，实习，写水论文，做水研究，但有一点我 颇为自得——从头到尾认真听了韩军教授的算法设计与分析课程。韩军给我印象最深的有两点: 课堂休息时跑到外面和几个学生借火抽烟; 讲解算法时的犀利 和毫不含糊。尽管韩军从来没有主动提及，但我敢肯定算法设计与分析基础就是他算法课程事实上的 (de-facto)，因为他的课程结构几乎和这本书的组织结构一模一样。如果数据结构与算法分析——C 语言描述是我的数据结构启蒙，那么韩军的课程和算法设 计与分析基础就是我的算法启蒙， 结合课程和书籍， 我一一理解并掌握了复杂度分析、 分治、 减治、变治、动态规划和回溯这些简单但强大的算法工具。算法引论算法引论是我这时无意中读到的另一本算法书， 和普通的算法书不同， 这本书从创造性的角 度出发——如果说算法导论讲的是有哪些算法，那么算法引论讲的就是如何创造算法。结 合前面的算法设计与分析基础， 这本书把我能解决的算法问题数量扩大了一个数量级。之后， 在机缘巧合下，我进入微软亚洲工程院实习，离理想又近了一步，自我感觉无限牛逼。巩固 在微软工程院的实习是我研究生阶段的一个非常非常非常重要的转折点: 1. 2. 3. 做出了一个还说的过去的小项目。期间百度实习面试受挫，痛定思痛之下阅读了大量的程序设计书。微软的实习经历成为了我之后简历上为数不多的亮点之一(本屌一没成绩，二没论 文，三没 ACM)。这里就不说 1 和 3 了(和本文题目不搭边)，重点说说 2。由于当时组内没有特别多的项目，我负责的那一小块又提前搞定了，mentor 便很慷慨的扔 给我一个 Kinect 和一部 Windows Phone 让我研究，研究嘛，自然就没有什么 deadline， 于是我就很鸡贼的把时间三七开: 七分倒腾 Windows Phone，三分看书 经典论文。然而一件事打断了这段安逸的生活—— 百度实习面试 基友在人人发百度实习内推贴，当时自我感觉牛逼闪闪放光芒，于是就抱着看看国内 IT 环 境+虐虐面试官的变态心理投了简历，结果在第一面就自己的师兄爆出翔: 他让我写一个 stof(字符串转浮点数)，我磨磨唧唧半天也没写出完整实现，之后回到宿舍赶快写了一个 版本发到师兄的邮箱，结果对方压根没鸟我。这件事对我产生了很大的震动——? ? ?原来自己连百度实习面试都过不去。原来自己还是一个编程弱逼。原来自己还是一个算法菜逼。 痛定思痛，我开始了第二个‖五年计划‖，三七开的时间分配变成了七三开: 七分看书，三 分 WP。而这一阶段的重点从原理(Principle)变成了实现(Implementation)——Talk is cheap, show me the code. Elements of Programming由于一直觉得名字里带‖Elements of‖的都是酷炫叼炸天的书，所以我几乎是毫不犹豫的 买了这本 Elements of Programming，事实上这本书里的代码(或者说 STL 的代码)确实 是: 快，狠，准，古龙高手三要素全齐。C Interfaces and Implementation百度面试被爆出翔的经历让我意识到另一个问题，绝大多数公司面试时都需要在纸上写 C 代码，而我自己却很少用 C(多数情况用 C#)，考虑到自己还没牛逼到能让公司改变面试 流程的地步，我需要提升自己编写 C 代码的能力(哪怕只是为了面试)。一顿 Google 之 后，我锁定了 C Interfaces and Implementation——另一本关于如何写出狂炫酷帅叼炸 天的 C 代码的奇书，这里套用下 Amazon 的评论: Probably the best advanced C book in existance。严格来说上面两本书都不是传统的算法书， 因为它们侧重的都不是算法， 而是经典算法的具 体实现 (Implementation)，然而这正是我所需要的: 因为算法的原理我能说明白，但要 给出优雅正确简练的实现我就傻逼了，哪怕是 stof 这种简单到爆的‖算法‖。依然是以前的傻逼学习方法: 反复研读+一遍又一遍的把代码抄写到本子上，艰难的完成了 这两本书后，又读 ming Practice)书籍，自我感觉编程了相当数量的编程实践(Program 能力又大幅提升，此外获得新技能——纸上编码。这也成为了我之后找工作面试的三板斧 之一。应用 说老实话，自从本科实习之后，我就一直觉得算法除了面试时能用用，其它基本用不上，甚 至还写了一篇当时颇为自得现在读起来极为傻逼的文章来黑那些动不动就‖ 基础‖ 或‖ 内功‖ 的所谓‖大牛‖们，这里摘取一段现在看起来很傻逼但当时却觉得是真理的文字: 所以那些动则就扯什么算法啊基础啊内功啊所谓的大牛们， 请闭上你的嘴， 条条大道通罗马。算法并不是编程的前提条件，数学也 不会阻碍一个人成为优秀的程序员。至少在我看来， 什么算法基础内功都是唬人的玩意， 多编点能用的实用的程序才是王道， 当然如果你是一个 pure theorist 的话就当我什么都没说好了。然而有意思的是， 写了这篇文章没多久， 鼓吹算法无用论的我自己做的几个大大小小的项目 全部用到了算法——我疑心是上天在有意抽我的脸。LL(k) 我在微软实习的第一个项目做的是代码覆盖率分析——计算 T-SQL 存储过程的代码覆盖 率。简单的看了下 SQL Server 相关的文档，我很快发现 SQL Reporting Service 可以记录 T-SQL 的执行语句及行号，于是行覆盖(line coverage)搞定，但老大说行覆盖太 naive， 我们需要更实际的块覆盖(block coverage)。阅读了块覆盖的定义后，我发现我需要对 T-SQL 进行语法分析，在没有找到一个好用的 T-SQL Parser 的情况下，只能自己动手搞一个: 比较奇诡的是，做这个项目时当时我刚好把 ANTLR 作者的 Language Implementation Patterns(中文)看了一半，什么 LL(k)啊 Packrat 啊 AST Walker 的概念啊正热乎着呢。于是， 自己自己就照着 T-SQL 的官方 EBNF， 三下五除二撸了一个 T-SQL 存储过程的 LL(k) Parser，把代码转换成 AST，然后用一个 External AST Walker 生成代码块覆盖的 HTML 报表，全部过程一周不到。老大自然是很满意——我疑心他的原计划是花两三个月来完成这个项目，因为这个项目之 后的两 个月我都没什么活干，天天悠哉游哉。拼音索引 拼音索引是我接的一个手机应用私活里的小模块， 用户期待在手机文本框可以根据输入给出 智能提示: 比如说输入中国: 同样，输入拼音也应给出提示: 中文匹配这个简单，但拼音匹配就得花时间想想了——懒得造轮子的我第一时间找到了微 软的拼音库，但接下来我就发现微软这个鸟库在手机上跑不动，研究 了下发现 WP7 对 Dictionary 的 items 数量有限制，貌似是 7000 还是 8000 个 item 就会崩盘，而汉字 则有两万多个，尼玛。痛骂 MS 坑爹+汉字坑爹之余，还是得自己撸一个库出来: 1. 2. 首先把那两万个汉字搞了出来，排序，然后弄成一个超长的字符串。接下来用 Int16 索引了汉字所有的拼音(貌似 500 多个)。 3.再接下来用 Int64 建立汉字和拼音的关联——汉字有多音字，所以需要把多个拼音 pack 到一个 Int64 里，这个简单，位操作就搞定。4. 5.最后用二分+位移 Unpack，直接做到从汉字到拼音的检索。后来小测了下性能，速度是 MS 原来那个库的五十倍有余，而代码量只有 336 行。用户很 happy——因为我捎带把他没想到的多音字都搞定了，而且流畅的一逼。我也很 happy，因为没想到自己写的库居然比 MS 的还要快几十倍，同时小十几倍。从这个事情之后我变得特别理解那些造轮子的人——你要想想，如果你需要一个飞机轮子 但市场上只有自行车轮子而且老板还催着你交工，你能怎么搞。快速字符串匹配 前面提到在微软实习时老大扔给我一个 Windows Phone 让我研究下，我当时玩了玩就觉 着不太对劲，找联系人太麻烦。比如说找‖张晓明‖，WP 只支持定位到 Z 分类下——这意味着我需要在 Z 分类下的七十 多个联系人(姓张的姓赵的姓钟的等等)里面线性寻找，每次我都需要滑动四五秒才能找到 这个张姓少年。这 TMD 也太傻逼了， 本屌三年前的老破 NOKIA 都支持首字母定位， 996- ZXM- 张晓明， 直接搞定，尼玛一个新时代 Windows Phone 居然会弱到这个程度。搜了一下发现没有好 用的拨号程序，于是本屌就直接撸了一个支持首字母匹配的拨号程序出来扔到 WP 论坛里。结果马上就有各种问题出现——最主要的反映是速度太慢，一些用户甚至反馈按键有时要 半秒才有反应。本屌问了下他的通讯录大小: 大概 3000 多人。吐槽怎么会有这么奇葩的通 讯录之余， 我意识到自己的字符串匹配算法存在严重的性能问题: 拼音，然后一个个的匹配——结果如果联系人数量太多 读取所有人的姓名计算出 的话，速度必然拙计。于是我就开 始苦思冥想有没有一个能够同时搜索多个字符串的高端算法， 以至于那两天坐地铁都在嘟囔 怎么才能把这个应用搞的快一些。最终还是在 Algorithms on Strings, Trees and Sequences 里找到了答案——确实有能够 同时搜索多个字符串的方法: Tries，而且这本书还用足足一章来讲怎么弄 Multiple string parison，看得我当时高潮迭起，直呼过瘾。具体细节不多说，总之换了算法之后，匹 配速度快了大约九十多倍，而且代码还短了几十行。哪怕是有 10000 个联系人，也能在 0.1 秒内搞定，速度瓶颈就这样愉快的被算法搞定。Writing Efficient Programs 之后又做了若干个项目，多多少少都用到了‖自制‖的算法或数据结构，最奇诡的一次是写 一个电子书阅读器里的分页，我照着模拟退火(Simulated Annealing)的原理写了一个快 速分页算法，事实上这个算法确实很快——但问题是我都不知道为啥它会这么快。总之， 算法是一种将有限计算资源发挥到极致的武器， 当计算资源很富余时算法确实没大用， 但一 旦到了效率瓶颈算法 绝壁是开山第一刀(因为算法不要钱嘛～要不还得换 CPU 买 SSD 升 级 RAM，肉疼啊～～)。一些人会认为这种说法是有问题，因为编写新算法的人力成本有 时 比增加硬件的成本还要高——但别忘了增加硬件提升效率也是建立在算法是 Scalable 的基础上——说白了还是得撸算法。说到优化这里顺带提一下 Writing Efficient Programs——很难找到一本讲代码优化的书 (我疑心是自从 Knuth 说了过早优化是万恶之源之后没人敢写，万恶之源嘛，写它干毛)， 注意这本书讲的是代码优化——在不改变架构、算法以及硬 管书中的一些诸如变量复用或是循环展开的 trick 已件的前提之下进行的优化。尽 经过时，但总体仍不失为一本好书。 提高 实习实习着就‎‎到了研二暑假，接下来就是求职季。求职季时我有一种莫名的复仇感——尼 玛之前百度实习面试老子被你们黑的漫天飞翔， 这回求职老子要把你们一个个黑回来， 尼玛。现在回想当时的心理实属傻逼+幼稚，但这种黑暗心理也起了一定的积极作用: 我丝毫不敢 有任何怠慢，以至于在 5 月份底我就开始准备求职笔试面试，比身边的同学早了两个月不 止。我没有像身边的同学那般刷题——而是继续看书抄代码学算法，因为我认为那些难得 离谱的题面试官也不会问——事实上也是如此。Algorithm Design Manual因为很多 Coding Interview 的论坛都提到这本红皮书，我也跟风搞了一本。事实证明，仅 仅是关于 Backtrack Template 那部分的描述就足以值回书价，更不用说它的 Heuristics 和课后题。编程珠玑 更多的编程珠玑这两本书就不用多介绍，编程珠玑和更多的编程珠玑，没听说过这两本书请自行面壁。前者 偏算法理论，后者偏算法轶事，前者提升能力，后者增长谈资，都值得一读。The Science of Programming读到编程珠玑里面关于 Binary Search 的正确性证明时我大呼过瘾， 原来程序的正确性也是 可以推导的，然后我就在那一章的引用里发现 David Gries 的 The Science of Programming。看名字就觉得很厉害，直接搞了一本开撸。不愧为编程珠玑引用的书籍， 撸完 The Science of Programming 之后，本屌获得了证明简单代码段的正确性这个技能 ——求职面试三板斧之二。证明简单代码段的正确性是一个很神奇的技能——因为面试时 大多数公司都会要求在纸上写一段代码， 然后面试官检查这段代码， 如果你能够自己证明自 己写的代码是正确的，面试官还能挑剔什么呢,之后就是各种面试，详情见之前的博客，总 之就是项目经历、纸上代码加正确性证明这三板斧，摧枯拉朽。进化 求职毕业季之后就是各种 Happy，Happy 过后本屌发现即将面临另一个问题: 算法能力不 足。因为据说以后的同事大多是 ACM 选手，而本屌从来没搞过算法竞赛，而且知道的算法 和数据结构都极为基础: 像那些元胞自动机、 斐波那契堆或是线段树这些高端数据结构压根 只是能把它们的英文名称拼写出来，连用都没用过，所以心理忐忑的一逼。为了不至于到时 入职被鄙视的太惨烈，加上自己一贯的算法自卑症，本屌强制自己再次学习算法: Algorithms 4thAlgorithms 是我重温算法的第一本书，尽管它实际就是一本数据结构的入门书，但它确实 适合当时已经快把算法忘光的本屌——不为学习，只为重温。这本书最大的亮点在于它把 Visualization 和 Formatting 做到了极致——也许它不是最好的数据结构入门书，但它绝 壁是我读过的排版最好的书，阅读体验爽的一逼;当然这本书的内容也不错，尤其是红黑树 那一部分，我想不会有什么书会比此书讲的更明白。6.851 Advanced Data StructuresAdvanced Data Structures 是 为什么会找到这个教程呢,因为 GoogleAdvanced Data MIT 的高级数据结构教程， Structures 第一个出来的就是这货。 这门课包含各种让本屌世界观崩坏的奇诡数据结构和算法，它们包括但不限于: ? ? ? ? ? ?带‖记忆‖的数据结构(Data Structure with Persistence)。van Emde Boas(逆天的插入，删除，前驱和后继时间复杂度)。o (1)时间复杂度的的 LCA、RMQ 和 LA 解法。奇幻的 o(n)时间复杂度的 Suffix Tree 构建方法。o(lglgn)的 BST。… 总之高潮迭起，分分高能，唯一的不足就是没有把它们实现一圈。以后本屌一定找时间把它 们一个个撸一遍。总结 从接触算法 到现在，大概七年: 初学时推崇算法牛逼论，实习后鼓吹算法无用论，读研后再 被现实打回算法牛逼论。怎么这么像辩证法里的肯定到否定再到否定之否定。现在来看，相当数量的鼓吹算法牛逼论的人其实不懂算法的重要性——如果你连用算法解 决实际问题的经历都没有， 那你如何可以证明算法很有用,而绝大多数鼓吹算法无用论的人 不过是低水平码农的无病呻吟——他们从未碰到过需要用算法解决的难题，自然不知道算 法有多重要。Peter Norvig 曾经写过一篇非常精彩的 SICP 书评， 我认为这里把 SICP 换成算法依然适用: To use an analogy, if algorithms were about automobiles, it would be for the person who wants to know how cars work, how they are built, and how one might design fuel-efficient, safe, reliable vehicles for the 21st century. The people who hate algorithms are the ones who just want to know how to drive their car on the highway, just like everyone else. MIT 教授 Erik Demaine 则更为直接: If you want to bee a good programmer, you can spend 10 years programming, or spend 2 years programming and learning algorithms. 总而言之，如果你想成为一个码农或是熟练工(Code Monkey)，你大可以不学算法，因 为算法对你确实没有用;但如果你想成为一个优秀的开发者(Developer)，扎实的算法必 不可少，因为你会不断 的掉进一些只能借助算法才能爬出去的坑里。 篇四: 《算法导论》学习总结——快速排序《算法导论》学习总结——快速排序曾经在程序员杂志上看到快速排序的作者，Hoare，曾经的图灵奖获得者啊，牛光闪闪的。不 过当时，对快速排序什么的，印象不算深刻，毕竟没好好学。记得当时杂志上说到的是，快速排 序，应该是目前最快的内部排序算法(虽然独立到语言上，C++的 sort 会比调用快速排序快) 。现 在就进入快速排序的美好复习吧。与归并排序类似，快排也用分治模式。主要是三个步骤:算法导论》学习总结——快速排序《算法导论》学习总结——快速排序曾经在程序员杂志上看到快速排序的作者，Hoare，曾经的图灵奖获得者啊，牛光闪闪的。不 过当时，对快速排序什么 的，印象不算深刻，毕竟没好好学。记得当时杂志上说到的是，快速排 序，应该是目前最快的内部排序算法(虽然独立到语言上，C++的 sort 会比调用快速排序快) 。现 在就进入快速排序的美好复习吧。与归并排序类似，快排也用分治模式。主要是三个步骤》是这样实现的: 对于最原始的快排，严蔚敏老?? int Partion(vector int v ,int low ,int high) ?? {//对 vector 进行划分，返回枢轴下标 ?? ?? ?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? } } v[low] = pivotkey ; return low ; int pivotkey; pivotkey = v[low] ; while ( low high ) { while (low high v[high] = pivotkey) high -- ; v[low] = v[high]; while (low high v[low] = pivotkey ) low ++ ; v[high] = v[low]; ??? void quickSort(vector int number ,int left ,int right) ??? { ??? ??? ??? ??? ??? ??? ??? } } if ( left right ) { int i = Partion(number , left, right) ; quickSort(number, left, i-1); // 对左边进行递归 quickSort(number, i+1, right); // 对右边进行递归当然，区别都只是在划分的过程，毕竟分治，才是快排的精髓嘛，不过这俩大同小异。快排的运行时间，显然与划分是否对称有关，要是直接划分出来，是一个最不均衡的二叉树， 那就够喝一壶的了，跟插入排序似的。下面网址有说法，是快排隐藏的二叉排序树思想，其实可 以参考， 虽然只是个人理 解 ://bbs.chinaunix.net/viewthread.php?tid=1011316。其实说到二叉， 堆排序不也是吗,区别只是堆排序显式的建堆，也就构成了一笔不小的开销，如果考虑隐藏排序 二叉树的话，倒是可以理解为毛快排快于堆排。由于快排平均情况下效果显然很良好，那么怎么得到平均情况就是个值得思考的问题，所 以书上给出了，在划分的时候，随机获取一个数作为枢轴，而不是用我们的 A[low]。于是我们得 到了快排的随机化版本如下: ??? int Partion(vector int A,int p ,int r) ??? {//数组划 分 ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? } ??? int RandomPartion(vector int A,int p ,int r) ??? {//在 A[p]到 A[r]中随机划分 } swap(A[i+1],A[r]); return i+1; } int x=A[r]; int i=p-1; for (int j=p ; j j++) { if ( A[j] = x ) { i++; swap(A[i],A[j]); ??? ??? ??? ??? }int i= p + rand()%(r-p+1); //i -RANDOM(p,r) swap(A[r],A[i]); return Partion(A,p,r);??? void RandomQsort(vector int A, int p ,int r) ??? {//递归快排 ??? ??? ??? ??? ??? ??? ??? } } if (p r) { int q = RandomPartion(A,p,r); RandomQsort(A,p,q-1); RandomQsort(A,q+1,r);与常规快排的区别，就是在划分的时候，获取一个随机数下标，再用其数组中的值作为枢 轴，当然，这样就充分考虑平均性能了。还有一种改进 RANDOM-QUICKSORT 的方法，就是根据从子数组更仔细地选择的(而不是随机选择的元素)作为枢轴来划分。常用的做法是三 数取中。可以参考: ://blog.csdn.net/zhanglei8893/article/details/6266915本章最后还提到个很蛋疼的 Stooge 排序，实现如下: ??? void StoogeSort(vector int A, int i ,int j) ??? {//递归快 排 ??? ??? ??? ??? ??? ??? ??? ??? ??? } if (A[i] A[j]) swap(A[i],A[j]); if (i+1 =j) return; int k = (j-i+1)/3; StoogeSort(A,i,j-k);//前2/3 StoogeSort(A,i+k,j);//后2/3 StoogeSort(A,i,j-k);//又前2/3??? // StoogeSort(A,i,i+k-1);// 如果采用1/3排不出来啊对于数组 A[i。j]，STOOGE-SORT 算法将这个数组划分成均等的3份，分别用 A, B, C 表示。第 8、9行从宏观上来看它进行了两趟，结果是最大的1/3到了 C，最小的1/3到了 B，从 宏观上来看，整个数组的三个大块就有序了，再进行递归，整个数组就有序了。第8和第9行，可 以看做一个冒泡过程。不过从运行时间的测试来讲，很不给力(具体数据就不列了) 。STOOGE-SORT 最坏情况 下的运行时间的递归式 T(n) = 2T(2n/3)+Θ (1) 由主定律可以求得 T(n)=n^2.71，相比插入排序、快速排序的 Θ(n^2)和 堆排序、合并排序的 Θ(nlgn)，不给力啊。参考自: ://blog.csdn.net/zhanglei8893/article/details/6235294。本章最后，练习7-4还提出个尾递归的概念，起因是 QuickSort 的第二次递归调用不是必须的，可以用迭代控制结构来替代。如: QUICKSORT (A, p, r) 1 while p r 2 3 4 5 do ? Partition and sort left subarray. q ? PARTITION(A, p, r) QUICKSORT (A, p, q - 1)p?q+1 具体 有效性的证明可以参考: ://blog.csdn.net/zhanglei8893/article/details/6236792， 需要说明的是，当数组正序时，其递归深度和栈深度都为 Θ(n)。 篇五: 算法导论复习资料算法导论复习资料——软件 0902高超算法导论复习资料 一、选择题: 第一章的概念、术语。 二、考点分析: 、复杂度的渐进表示，复杂度分析。 1、复杂度的渐进表示，复杂度分析。 2、正确性证明。、正确性证明。考点: 1)正确性分析(冒泡，归并，选择) ;2)复杂度分析(渐进表示O，,，?，替换法证 明，先猜想，然后给出递归方程) 。循环不变性的三个性质: 1)初始化: 它在循环的第一轮迭代开始之前，应该是正确的; 2)保持: 如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也 应该保持正确; 3)当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。插入排序算法: INSERTION-SORT(A INSERTION-SORT(A) 1 for j ? 2 to length[A] 2 do key ? A[j] 3 ? Insert A[j] into the sorted sequence A[1，j - 1]. 4 i ? j-1 5 while i 0 and A[i] key 6 do A[i + 1] ? A[i] 7 i ? i-1 8 A[i + 1] ? key 插入排序的正确性证明: 课本11页。归并排序算法: 课本17页及19页。归并排序的正确性分析: 课本20页。 3、分治法(基本步骤，复杂度分析) ——许多问题都可以递归求解 。—— 、分治法(基本步骤，复杂度分析) ——许多问题都可以递归求解 。考点: 快速排序，归并排序，渐进排序，例如: 12球里面有一个坏球，怎样用最少的次数找出 来。(解: 共有24种状态，至少称重3次可以找出不同的球) 不是考点: 线性时间选择，最接近点对，斯特拉算法求解。解: 基本步骤: 一、分解: 将原问题分解成一系列的子问题; 二、解决: 递归地解各子问题。若子问题足够小，则直接求解; 三、合并: 将子问题的结果合并成原问题的解。复杂度分析: 分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运 行时间，得到递归式 T(n)=Q (1) n =c T(n)=aT(n/b)+D(n)+C(n) n c 附加习题: 请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S 和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。第 1 页 共 13 页 算法导论复习资料——软件 0902高超第 2 页 共 13 页 算法导论复习资‎‎料——软件 0902高超，导出最优 4、动态规划(最优子结构性质，自底向上填表计算最优解值(即最长公共子序列) 导出最优 动态规划(最优子结构性质，自底向上填表计算最优解值(即最长公共子序列) ， 解) 。考点: 最优子结构性质，自底向上填表计算最优解值，导出最优解。a)动态规划算法设计的4个步骤: 1)描述最优解的结构;2)递归定义最优解的值;3)按自底 向上的方式计算最优解的值;4)由计算出的结果构造一个最优解。b)最优子结构遵循的共同模式: 1)问题的一个解可以是做一个选择，做这种选择可能会 得到一个或多个有待解决的子问题;2)假设对一个给定的问题，已知的是一个可以导致最优解 的选择，不必关心如何确定这个选择，尽管假定它是已知的;3)在已知这个选择后，要确定哪 些子问题会随之发生， 以及如何最好地描述所得到的子问题的空间; 利用一种―剪切粘贴法‖， 4) 来证明在问题的一个最优解中， 使用的子问题的解本身也必须是最优的。备注: 备注: problem exhibits A optimal substructure if an optimal solution to the problem contains within it optimal solutions to第 3 页 共 13 页 算法导论复习资料——软件 0902高超subproblems. Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply. c)最长公共子序列的算法: 这里以两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}为输入，注意课 本211页的自底向上填表方法。LCS注: 此程序运行时间为O(mn) ，每个表项的计算时间为O (1) LCS-LENGTH(X, Y) 1 m ? length[X] 2 n ? length[Y] 3 for i ? 1 to m 4 do c[i, 0] ? 0 5 for j ? 0 to n 6 do c[0, j] ? 0 7 for i ? 1 to m 8 do for j ? 1 to n 9 do if xi = yj 10 then c[i, j] ? c[i - 1, j - 1] + 1 11 b[i, j] ? ―= 12 else if c[i - 1, j] ? c[i, j - 1] 13 then c[i, j] ? c[i - 1, j] 14 b[i, j] ? ? 15 else c[i, j] ? c[i, j - 1] 16 b[i, j] ? ? 17 return c and b PRINT注: 此程序运行时间为O(m+n) PRINT-LCS(b, X, i, j) 1 if i = 0 or j = 0 2 then return 3 if b[i, j] = = 4 then PRINT-LCS(b, X, i - 1, j - 1) 5 print xi 6 elseif b[i, j] = ? 7 then PRINT-LCS(b, X, i - 1, j) 8 else PRINT-LCS(b, X, i, j - 1) d)矩阵链乘法的算法: 参照课本上的矩阵链表得出矩阵相乘的最小算法。m[i, j ] = min{m[i, k ] + m[k + 1, j ]i ?k j+ pi ?1 pk p j }第 4 页 共 13 页 算法导论复习资料——软件 0902高超MATRIX-CHAIN，共有O(n^2)表项，则为O(n^3) MATRIX-CHAIN-ORDER(p) 每个表项的复杂度是O(n) 1 n ? length[p] - 1 2 for i ? 1 to n 3 do m[i, i] ? 0 4 for l ? 2 to n ?l is the chain length. 5 do for i ? 1 to n - l + 1 6 do j ? i + l - 1 7 m[i, j] ? ? 8 for k ? i to j - 1 9 do q ? m[i, k] + m[k + 1, j] + pi-1 pkpj 10 if q m[i, j] 11 then m[i, j] ? q 12 s[i, j] ? k 13 return m and s PRINT-OPTIMALPRINT-OPTIMAL-PARENS(s, i, j) 1 if i = j 2 then print Ai 3 else print ( 4 PRINT-OPTIMAL-PARENS(s, i, s[i, j]) 5 PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j) 6 print ) e)备忘录算法: 1)程序结构采用自顶向上;2)保留了递归结构，开销较大;3)当所有的子 问 题都需要求解时，自底向上的方法效率较高，否则可以采用备忘录方法。备忘录算法的代码可以参照课本207页。f)最优二叉查找树: 1)一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是 把有最大概率的关键字放在根部来构造一棵最优二叉查找树。 5、贪心法(最优子结构性质 贪心选择性质) 贪心选择性质) 、贪心法(最优子 结构性质+贪心选择性质 。考点: 学会证明最优子结构性质和贪心选择性质的问题。a)活动选择问题: if Sij = φ ?0 ? c[i, j ] = ? {c[i, k ] + c[k , j ] + 1} if Sij ? φ ?max ? i k j注意课本上224页地贪婪法定理证明，这就是贪婪法的合理性证明。RECURSIVE-ACTIVITY-SELECTOR(s, j) RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j) 1m ? i+1 2 while m j and sm fi ? Find the first activity in Sij. 3 do m ? m + 1第 5 页 共 13 页 算法导论复习资料——软件 0902高超4 if m j 5 then return {am} ? RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j) 6 else return GREEDY-ACTIVITY-SELECTOR(s, f) GREEDY-ACTIVITY-SELECTOR(s, f) CTOR( 1 n ? length[s] 2 A (本文来自: WwW.CdFdS.Com 池 锝网:算法导论学习方法)? {a1} 3i ? 12 4 for m ? 2 to n 5 do if sm ? fi 6 then A ? A ? {am} 7 i ? m 8 return A b)贪心算法遵循的步骤: 1)决定问题的最优子结构;2)设计出一个递归解;3)证明在递归 的任一阶段，最优选择之一总是贪心选择，那么，做贪心选择总是安全的;4)证明通过做贪心 选择，所有的子问题(出一个以外)都为空;5)设计出一个实现贪心策略的递归算法;6)将 递归算法转换成迭代算法。c)根据贪心选择来构造最优子结构: 1)将优化问题转化成这样一个问题，即先做出选择，再 解决剩下的一个子问题;2)证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心 选择的安全;3)说明在做贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的 最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。d)贪心选择性质: 证明定理16.1 e)最优子结构性质: 课本229页。 6、搜索(回溯法、剪枝函数、最小成本优先) 、搜索(回溯法、剪枝函数、最小成本优先) 。考点: 回溯，剪枝函数，最小成本优先的问题;分支界限法，剪枝函数所具备的性质。a)回溯法: 1)定义: 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通 就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为―回溯点‖。2)回溯法解题的步骤: a、针对所给的问题，定义问题的解空间; b、确定易于搜索的解空间结构; c、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。2)回溯法解决的n后问题: 在一个n * n的棋盘上放置n个王后，使得n后彼此不受攻击。3)回溯法解决0-1背包问题: 附: 证明部分背包问题具有贪心选择性质。课本练习题16.2-3: 第 6 页 共 13 页 算法导论复习资料——软件 0902高超c剪枝函数: 约束函数: 剪去不满足约束函数的子树; 限界函数: 剪去由限界函数表明不能得到最优解的子树。P( x1 , x2 ,。, xk +1 ) ? P( x1 , x2 ,。, xk )0 k n剪枝函数的必要条件: 典型例题: 1)求不等式的整数解 5x1+4x2?x3 =10, 1 =xj =3, i =1,2,3第 7 页 共 13 页 算法导论复习资料——软件 0902高超2)装载问题: c)最小成本优先算法: 注: 分支——限界的基本思想: 1 回溯法的深度优先比较盲目 2 广度优先代价太高 4 能优先搜索那些最有希望得到解的路径 6 深入分析问题，得到有用的启发信息 7 利用启发信息构造成本函数 8 最小成本优先的搜索策略 9 结合剪枝函数 典型题型: 重拍九宫问题。 7、最大流(概念，最大流 最小割定理，Edmonds-Karp算法) 最小割定理， 算法) 、最大流(概念，最大流-最小割定理 算法 。考点: 最大流的相关概念， 最大流——最小割定理， Edmonds-Karp算法， 要求掌握Ford-Fulkerson 算法的相关内容。1)流网络定义: 有向图G = (V, E)，如果图G满足: – 存在源结点(source) s(s的入度为0) – 存在汇结点(sink) t(t的出度为0) – 任意结点v?V，有s ~ v ~ t – 容量函数C: E ? R+ 称G为流网络。流的定义: 流网络G，若函数 p: V XV? R+满足下述条件: – 容量限制: 对任意(u,v) ? E，有0 =p(u,v) =c(u,v) – 守恒条件: 对任意u ?(V-{s,t})，有 则称p为G上的流。注意课本399页的引理。2)对源点顶点来说，离开它的正流要比进入它的正流更多;对汇点顶点来说，进入它的正流要 比离开它的正流更多。先证明如下: |f|=f(s，V) =f(V，V)-f(V-s，V) =f(V，V-s) =f(V，t)+f(V，V-s-t) =f(V，t) 3)Ford-Fulkerson方法: 此方法依赖三中重要思想，a、残留网络;b、增广路径; c、割。这些 是最大流最小割定理的精髓。Ford-Fulkerson方法沿增广路径反复增加流， ( 知道找出最大流为止; 而最大流最小割定理告诉我们: 一个流是最大流，当且仅当它的残留网络不包含增广路径。) 一、残留网络: 在不超过容量c(u，v)的条件下，从u到v之间可以压入的额外网络流量， 就是(u，v)残留容量，定义为cf(u，v)=c(u，v)-f(u，v) 。注意课本401页的残留网络的 例子。残留网络Gf本身也是一个流网络，其容量由cf给出，且|Ef| =2|E|。注意课本402页的引理 26.2。 二、增广路径: 注意课本403页引理26.3和引理26.4。第 8 页 共 13 页 算法导论复习资料——软件 0902高超 三、流网络的割: 注意403页的几个引理。四、最大流最小割定理: 几个相互等价的条件。FORD-FULKERSON(G FORD-FULKERSON(G, s, t) 1 for each edge (u, v) ? E[G] 2 do f[u, v] ? 0 3 f[v, u] ? 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) ? min {cf(u, v) : (u, v) is in p} 6 for each edge (u, v) in p 7 do f[u, v] ? f[u, v] + cf(p) 8 f[v, u] ? -f[u, v] FORD-FULKERSON的复杂性: FORD-FULKERSON过程的运行时间取决于如何决定第四行中 的增广路径，选择不好，算法可能不会终止。假设容量是整数 ? 1~3行O(|E|) ? 4~8循环执行O(|f*|) ? 找增广路O(|E|) ? O(|E||f*|) FORD-FULKERSON算法有其缺点，可以参照课本406页。4)Edmonds-Karp算法: 如果在第四行中用广度优先搜索来实现对增光路径p的计算。即如果增 光路 径是残留 网络中 从s到 t 的最短路径 (其 中每条 边为 单位 距离， 或权 ) 则能够改进 ， FORD-FULKERSON算法的界;称FORD-FULKERSON方法的这种实现为Edmonds-Karp算法。Edmonds-Karp算法的运行时间为O(V*E2) 注意课本407页关于Edmonds-Karp算法的一些证明。 8、NP完全问题(多项式时间规约) 、 完全问题 多项式时间规约) 完全问题( 。考点: 多项式时间内的规约问题，掌握NP 完全问题的证明方法。P类问题: 是在多项式时间内可解的问题，即都是在O(nk)时间内求解的问题，此处k为某个常 数，n是问题的输入规模。NP类问题: 是在多项式时间内―可验证‖的问题即能够在问题输入规模的多项式时间内，验证 该问题是正确的。注意: P问题包含于NP问题。但P不一定是NP问题的真子集。NPC问题: NP完全问题，即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题， 那么这个NP问题就成为NPC问题。换言之，如果这个问题解决了，那么所有的NP问题也都能解 决了。若问题L满足 若问题L 若问题 – L ? NP, and – L′?P L for every L ′? NP. ′?P 则问题L NPC的 只满足条件2则称问题是NP hard的 NP则问题L是NPC的，若L只满足条件2则称问题是NP-hard的。注意: 如果任何NP完全问题可以在多项式时间内解决，则NP中所有问题都有一个多项式时间 的算法。第 9 页 共 13 页 算法导论复习资料——软件 0902高超1)多项式时间内的规约: – 若问题2可以被多项式时间求解，则问题1也可被多项式时间求解; – 若问题1不能被多项式时间求解，则问题2也不能多项式时间求解; – problem1 ?p problem2表明: 问题1的求解不―难‖于问题2。假定一个判定问题A和另外一个不同的判定问题B，在一个过程中，它能将A的任何势力a转换为 B的、具有以下特征的势力b: a、转化操作需要多项式时间; b、两个实例的答案是相同的，即a的答案是―是‖ ，当且仅当b的答案也是―是‖ ， 称这样的过程为多项式时间的规约算法。可以参照课本599页的图。a、给定问题A的一个实例a，利用多项式时间规约算法，将它转换为问题B的一个实例b。b、在实例b上，运行B的多项式时间判定算法。 c、将b的答案用作a的答案。可以将对问题A的求解―规约‖为对问题B的求解。注意: 第一个NP完全问题就是电路可满足性问题。2)NP完全性与可归约性: 课本609页引理34.3 3)电路可满足性问题: 引理: 电路可满足性问题属于NP类、NP难度及NP完全的。例题解析: 例题解析: 1、设有一个长度为 的数字串，要求选手使用 个乘号将它分成 的数字串， 个乘号将它分成K+1个部分，找出一种分法， 个部分， 、设有一个长度为N的数字串 要求选手使用K个乘号将它分成 个部分 找出一种分法， 使得这K+1个部分的乘积能够为最大。个部分的乘积能够为最大。(EX: 有一个数字串: ， 使得这 个部分的乘积能够为最大 ( : 有一个数字串: 312，当N=3，K=1时会有以下两 ， 时会有以下两 种分法: 种分法: 3*12=3 6、31*2=62，这时，符合题目要求的结果是: 31*2=62。、 ，这时，符合题目要求的结果是: 。) 教授是一家石油公司的顾问， 2、Olay教授是一家石油公司的顾问，这家公司正在计划建造一条由东向西的大型管道，它穿 、 教授是一家石油公司的顾问 这家公司正在计划建造一条由东向西的大型管道， 过一个有n口油井的油田 从每口井中都有一条喷油管道沿最短路径与主管道直接连接( 口油井的油田。过一个有 口油井的油田。从每口井中都有一条喷油管道沿最短路径与主管道直接连接(或南 或北) 给定各口井的x坐标和 坐标，应如何选择主管道的最优位置(使得各喷管长度总和最 。给定各口井的 坐标和y坐标 或北) 给定各口井的 坐标和 坐标，应如何选择主管道的最优位置(使得 各喷管长度总和最 。),证明最优位置可在线性时间内确定 证明最优位置可在线性时间内确定。小),证明最优位置可在线性时间内确定。证明: 问题， 3、NPC证明: 如集合的等划分问题，TSP问题，最小顶点覆盖问题。、 证明 如集合的等划分问题， 问题 最小顶点覆盖问题。 一、证明: 顶点覆盖问题是NP完全问题。证明: 顶点覆盖问题是NP完全问题。NP完全问题 将3SAT变换到VC. 设U={u1,u2,。,un}, C={c1,c2,。,cm}是3SAT的实例. 如下构造图G, 分量 设计法. 真值安排分量: Ti=(Vi,Ei), 1?i?n, 其中Vi={ui,ūi}, Ei={{ui,ūi}} 任意覆盖必至少包含ui或ūi中的一个,否则不能覆盖边{ui或ūi}. 满足性检验分量: Sj=(Vj‘,Ej‘), 1? j? m, 其中 Vj‘={a1[j],a2[j],a3[j]} Ej‘={{a1[j],a2[j]},{a1[j],a3[j]},{a2[j],a3[j]}} 覆盖至少包含Vj‘中的两个顶点,否则不能覆盖Ej‘中的三角形 联络边:第 10 页 共 13 页 算法导论复习资料——软件 0902高超沟通分量之间的关系 对于每个子句cj, 设cj = {xj,yj,zj}, 则 Ej‘‘={{a1[j],xj},{a2[j],yj},{a3[j],zj}} G = (V,E) V = (V1?V2?。?Vn)?(V1‘?V2‘?。?Vm‘) E = E1?E2?。?En)?(E1‘?E2‘?。?Em‘) ?(E1‘‘?E2‘‘?。?Em‘‘) K = n +2m 显然构造可在多项式时间完成 例如 U = {u1,u2,u3,u4}, C = {{u1,ū3,ū4},{ū1,u2,ū4}}, 则G如下，K = 4 + 2×2 = 8设V‘是V中不超过K的顶点覆盖, 则V‘中必包含Ti中的一个顶点和每个Ej‘中的两个顶点, 至 少要n+2m个顶点. 而K=n+2m, 故V‘中一定只包含每个Ti中的一个顶点和每个Ej‘中的两个顶 点. 如下得到赋值 ui?V‘ ? t(ui)=T ūi?V‘ ? t(ui)=F Ej‘‘中的三条边有两条被Vj‘?V‘中的顶点覆盖, 第三条必被V‘?Vi中的顶点覆盖. 这 表示在Vi中的这个顶点对应的文字取真. 所以子句cj被满足. 从而C被满足. 设t: U?{T,F}是满足C的一组赋值. 若t(ui)=T, 则在Ti中取顶点ui, 否则取ūi. 因为t满足子句 cj, 在Ej‘‘中的三条联络边中至少有一条被覆盖, 那么取Ej‘‘中的另两条边的端点作为V‘ 中的端点即可. 证明: TSP(旅行商问题)问题是NP完全问题。NP完全问题 二、证明: TSP(旅行商问题)问题是NP完全问题。首先来说明TSP问题属于NP。给定该问题的一个实例，用回路中n个顶点组成的序列作为证 书。验证算法检查该序列是否恰好包含每个顶点一次，并且对边的费用求和后，检查和是否至 多为k。为了证明TSP是NP难度的，先证明HAM-CYCLE =PTSP。设G=(V，E)是HAM- ，其CYCLE 额一个实例。构造TSP的实力如下，建立一个完全图G‘=(V，E‘) 中E‘={(i，j) : i，j 属于V且i～=j}，定义费用函数为 c(i，j)={0，如果(i，j)属于E {1，如果(i，j)不属于E Notice: 因为G是无向图，它没有自环路，因而对所有的顶点v属于V，都有c(v，v)=1，于是第 11 页 共 13 页 算法导论复习资料——软件 0902高超 G‘，c，0 就是TSP的一个实例，它很容易在多项式时间内产生。现在说明图G中具有一个汉密尔顿回路，当且仅当图G‘中有一个费用至多为0的回路。假 定图G中有一个汉密尔顿回路h，h中的每条边度属于E，因此在G‘中的费用为0。因此h在G‘ 中的费用为0的回路。反之，假定图G‘中有一个费用h?至多为0的回路。由于E‘中边的费用 只能是0或1，故回路h‘的费用就是0，且回路上每条边的费用必为0。故h?仅包含E中的边。证明: 集合的等划分问题是NP完全问题。NP完全问题 三、证明: 集合的等划分问题是NP完全问题。实例: 有穷集A s(a)? 实例: 有穷集A，?a?A, s(a)?Z+. 是否存在A 问: 是否存在A‘?A，使得 ? s(a ) = ? s(a ) a? A a? A? A 显然均分是NP类问题。下面将3DM变换到均分问题 设W,X,Y,M ? W×X×Y 是3DM的实例， 其中|W| = |X| = |Y| = q， W = {w1,w2,… ,wq} X = {x1,x2,… ,xq} Y = {y1,y2,… ,yq} M = {m1,m2,… ,mk} 构造A，|A| = k +2 对应于每个mi = (wf(i),xg(i),yh(i)) 有ai. s(ai)为二进制数，分成3q段，每段有p = ?log(k+1)?位,共计3pq位，每段对应一个 W?X?Y中的元 素. Wf(i),xg(i),yh(i) 所代表的段的最右位为1，其它为0.s(a i ) = 2 p( 3q ? f ( i )) + 2 p( 2q ? g ( i )) + 2 p( q ? h( i ))w1 w2 … wq x1 x2 … xq y1 y2 … yq 注: 2p ?k+1，k? 2p?1 , 当 k个1相加时不会产生段之间的进位 3 q ?1 p?log(k+1)， 令 pj p ( 3 q ?1 ) p( 3q ? 2 )B= ? 2j=0=2?+2?+ 。 + 2 2 p + 2 p + 20B的段数与s(ai)一样，每段的最右位为1，其它为0 例如: W={w1,w2},X={x1,x2},Y={y1,y2}, M={(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)} p=?log(3+1)?=2 元素a1,a2,a3分别对应 (w1,x2,y2),(w1,x2,y1),(w2,x1,y1) s(a1) = 01 00 00 01 00 01 = 210 + 24 + 20 s(a2) = 01 00 00 01 01 00 = 210 + 24 + 22 s(a3) = 00 01 01 00 01 00 = 28 + 26 + 22 B = 01 01 01 01 01 01 子集A‘ = {ai:1?i?k} 满足 ? s(a ) = B a? A 当且仅当 M‘ = {mi: ai?A‘}是M的匹配 A的最后两个元素b1,b2s(b1 ) = 2 ? s(a i ) ? Bi =1ks(b2 ) = ? s(a i ) + Bi =1k第 12 页 共 13 页 算法导论复习资料——软件 0902高超考虑包含b1的子集A‘, 必有a? A ? { b1 }? s ( a ) = 2 ? s ( a i ) ? ( 2 ? s( a i ) ? B ) = Bi =1 i =1kk因此A‘-{b1}的元素对应的三元组构成M的匹配 反之，若子集M‘构成M的匹配，则 A‘ = {b1}?{ai: mi?M‘} 满足 ka? A ? s( a ) = ( 2 ? s( a i ) ? B ) + Bi =1 k i =1 a? A? A = 2 ? s(ai ) =? s (a )证明题的考点: 1、正确性证明问题。 2、替换法证明问题。 3、贪心选择性质证明问题。 4、NP完全问题的证明。 5、最大流问题的证明。简单题的考点: 1、回溯法基本思想和步骤。 2、分治算法的基本方法和步骤。 3、搜索算法的基本方法和步骤。 4、动态规划问题的基本方法和步骤。 5、分支界限算法的基本方法和步骤。第 13 页 共 13 页