算法的乐趣[试读]

本章的标题既然是“程序员与算法”，就必然要涉及一个基本问题，那就是“程序员是否必须会算法”。这是一个充满争议的问题，虽然并不像“生存还是毁灭”之类的选择那样艰难而沉重，但也绝不是一个轻松的话题。朋友们在我的“算法系列”博客专栏上发表的评论和回复，并不都是我所期待的赞美和鼓励，也常常会有一些冷言冷语。比如，“穷举也算是算法吗”或者“请你说明一下算法在XX系统中能起到什么作用”。 有一次，一个网友通过邮件问我：“你写的都是小儿科的东西，几十行代码就能搞定，能不能整一点高深的算法？”我反问他什么是他所理解的高深的算法，他答复说：“像遗传算法、蚁群算法之类的。”于是我给了他一个遗传算法求解0-1背包... 查看全部[ 1.1　什么是算法 ]

很多人可能是好莱坞大片看多了，以为计算机神通广大，但事实不是这样的。计算机其实是一种很傻的工具，傻到几乎没有智商（至少目前是这样）。它可以连续几年做同一件事情而毫无怨言，但是如果你不告诉它怎么做，它什么事情也不会做。最有创造性的活动其实是由一种被称为“程序员”的人做的，计算机做的只不过是人类不愿意做的体力活而已。比如图像识别技术，需要一个字节一个字节地处理数据，提取数据的特征值，然后在海量的数据中比较、匹配这些特征值，直到累得两眼昏花，人类才不会干这种傻事儿呢。计算机愿意做，但前提是你要告诉它怎么做。算法可以理解为这样一种技术，它将告诉计算机怎么做。有人将编程理解为搭积木，直接用别人开发好的组... 查看全部[ 1.2　程序员必须要会算法吗 ]

算法有很多种存在形式，编写计算机程序只是其中一种，是程序员惯用的方式，本书要介绍的内容就是如何以计算机程序的方式研究算法。1.2节介绍的两个例子都是我亲身经历过的事情，程序员在大部分时间里都是处理一些平凡而琐碎的程序，但有时候也需要做一些创造性的工作。记住，程序员就是计算机的“上帝”，计算机能解决问题是因为它的“上帝”告诉它怎么做。那么，当问题来临的时候，“上帝”是到各种论坛上发帖子求代码，还是自己解决问题？ 如果要自己解决问题，应该如何解决问题？为什么要自己解决问题？先来回答第一个问题——如何设计算法解决问题？人类解决问题的方式是当遇到一个问题时，首先从大脑中搜索已有的知识和经验，寻找它们... 查看全部[ 1.3　算法的乐趣在哪里 ]

本书讲到的算法都是以计算机程序作为载体展示的，其基本形式就是程序代码。作为一个软件开发人员，你希望看到什么样的代码？是这样的代码： double kg = gScale * 102.1 + 55.3; NotifyModule1(kk); double kl1 = kg / l_mask; NotifyModule2(kl1); double kl2 = kg * 1.25 / l_mask; NotifyModule2(kl2); 还是这样的代码： double globalKerp = GetGlobalKerp(); NotifyGlobalModule(globalK... 查看全部[ 1.4　算法与代码 ]

本章借用了多部知名著作中对算法的定义，只是想让大家对算法有一个“宽容”一点的理解。通过我亲身经历的两个例子，说明了程序员与算法之间“剪不断，理还乱”的关系。除此之外，还简单探讨了算法乐趣的来源、算法和代码的关系，以及研究代码本身的乐趣等内容。 如果你认同我的观点，就可以继续阅读本书了。本书的每一章都是独立的，没有前后关系，你可以根据自己的喜好直接阅读相关的章节。希望本书能使你有所收获，并体会到算法的乐趣。 1.6　参考资料 [1] Cormen T H, et al. Introduction to Algorithms (Second Edition). The MIT Press,... 查看全部[ 1.5　总结 ]

每年凤凰花开、蝉鸣绿叶的季节，都是毕业的季节，也是同学们找工作的季节。很显然，学生和雇主之间从来都是双向选择的关系，然而学霸们往往先人一步，早早地就抓了一把offer。无奈，即便是学霸也分身无术，最终只能选择一个offer。毫无疑问，学霸们会根据自己的偏好对offer排队，选其中最好的一个。有时候我会想，其他也给了学霸offer的公司岂不是少了一个名额？显然我是多虑了，其实这些雇主公司也有一个偏好列表作为备用，如果空出了名额，他们会从这个备用的偏好队列中再选一个。但这总归不是一个最高效的资源配置方式，大量的撤销和重新选择会浪费很多社会资源。有没有一种方法，在双向选择公开透明的基础上，按照资源配... 查看全部[ 7.1　稳定匹配问题 ]

本节利用舞伴问题介绍一个Gale-Shapley算法的应用实例。舞伴问题是这样的：有 n 个男孩与 n 个女孩参加舞会，每个男孩和女孩均交给主持一个名单，写上他（她）中意的舞伴名字。无论男孩还是女孩，提交给主持人的名单都是按照偏爱程度排序的，排在前面的都是他们最中意的舞伴。试问主持人在收到名单后，是否可以将他们分成 n 对，使每个人都能和他们中意的舞伴结对跳舞？为了避免舞会上出现不和谐的情况，要求这些舞伴的关系是稳定的。 假如有两对分好的舞伴：（男孩A，女孩B）和（男孩B，女孩A），但是男孩A更偏爱女孩A，女孩A也更偏爱男孩A，同样，女孩B更偏爱男孩B，而男孩B也更偏爱女爱B。在这种情况下，... 查看全部[ 7.2　Gale-Shapley算法的应用实例 ]

当参加舞会的男孩和女孩按照一定的顺序排好队，位置固定之后，使用Gale-Shapley算法能够得到一个确定的稳定匹配结果。但是对这群男孩和女孩来说，稳定匹配的结果肯定不是唯一的，其实只要将计算策略从“男士优先”转换成“女士优先”，就可以得到另外一个完全不同的稳定匹配结果。同样，调整一下男孩们的位置顺序，比如让最后一个男孩排在第一的位置，让他第一个邀请女孩，则Gale-Shapley算法也可以得到一个完全不同的稳定匹配结果。 很显然，对于任意情况下的n个男孩和n个女孩来说，肯定有多个稳定匹配，那么，到底有多少个稳定匹配？稳定匹配首先必须是完美匹配，而且稳定匹配的个数小于或等于完美匹配，所以，我... 查看全部[ 7.3　有多少稳定匹配 ]

之前讨论稳定匹配问题的时候，我们把完美匹配定义为每个男人和女人都属于匹配中的某个对，并不是很直观，现在我们准备用图的术语更一般地表达完美匹配的概念。首先介绍一下二部图，二部图G=(V,E)是这样的一个图，它的顶点集合V可以划分为X和Y两个集合，它的边集合E中的每条边都有一个端点在X集合，另一个端点在Y集合。图7-2就是一个二部图。 现在给出针对二部图的匹配的定义，给定一个二部图G=(V,E)的子图M，如果M的边集中任意两条边都不依附于同一个顶点，则称M是一个匹配。简单地说，图7-2中x2、x3、x4等点都有多条边与之连接，也就是说有多个边依附于这些点，因此图7-2所示的二部图不是一个匹配。现... 查看全部[ 7.4　二部图与二分匹配 ]

各种匹配问题可不是仅仅用来娱乐的算法竞赛题目，它们在现实生活中都有着广泛的应用。比如稳定匹配原理作为一种资源的分配方法，就在美国的医疗体系中得到了广泛应用。19世纪40年代，在先进医疗技术的引领下，美国的医疗体系得到了巨大的发展，但是稀缺的医学院毕业生成了这个体系的心病。为了争抢稀缺资源，医院被迫在学生毕业前好几年就向他们提供实习机会。学生们则在还没有被证明有资格从事医疗工作的情况下就已经完成了工作配对，同时，如果医院提供的实习机会没有被学生接受，那么再向别的候选人提供机会就太晚了。很显然，这个市场没有稳定匹配，于是在19世纪50年代，美国启动了一个名为“国家住院医生匹配项目”（NRMP）的计... 查看全部[ 7.5　总结 ]

[1] Gale D, Shapley L S. College Admissions and the Stability of Marriage. American Mathematical Monthly，1962,69:9-15 [2] Levitin A. 算法设计与分析基础. 潘彦译. 北京：清华大学出版社，2007 [3] Cormen T H, et al. Introduction to Algorithms (Second Edition). The MIT Press, 2001 [4] Knuth D E. The Art of Computer Progr... 查看全部[ 7.6　参考资料 ]