跳到主要内容

1.1 算法

- · -

简单来说,所谓算法(algorithm)就是定义良好的计算过程,它取一个或一组值作为输入,并产生出一个或- -组值作为输出。亦即,算法就是一系列的计算步骤,用来将输人数据转换成输出结果。

我们还可以将算法看作是一种工具,用来解决一个具有良好规格说明的计算问题。有关该问题的表述可以用通用的语言,来规定所需的输人/输出关系。与之对应的算法则描述了一个特定的计算过程,用于实现这一输人/输出关系。

例如,假设需要将一列数按非降顺序进行排序。在实践中,这一问题经常出现。它为我们引人许多标准的算法设计技术和分析工具提供了丰富的问题场景。下面是有关该排序问题的形式化定义:

输入:由 nn 个数构成的一个序列 <a1,a2,...,an><a_1, a_2, ..., a_n>输出:对输入序列的一个排列 <a1,a2,...,an><a_1^`, a_2^`, ..., a_n^`> ,满足 a1a2...ana_1^` \leq a_2^` \leq ... \leq a_n^`

例如,给定一个输人序列 <31,41,59264158><31, 41, 59, 26, 41,58> , 一个排序算法返回的输出序列是 <26,31,41,41,58,59><26,31, 41, 41, 58, 59>。 这样的一个输人序列称为该排序问题的一个实例(instance)。一般来说,某一个问题的实例包含了求解该问题所需的输人(它满足有关该问题的表述中所给出的任何限制)。

在计算机科学中,排序是一种基本的操作(很多程序都将它用作- -种中间步骤),因此,迄今为止,科研人员提出了多种非常好的排序算法。对于一项特定的应用来说,如何选择最佳的排序算法要考虑多方面的因素,其中最主要的是考虑待排序的数据项数、这些数据项已排好序的程度、对数据项取值的可能限制、打算采用的存储设备的类型(内存、磁盘、磁带)等。

如果一个算法对其每一个输入实例,都能输出正确的结果并停止,则称它是正确的。我们说一个正确的算法解决了给定的计算问题。不正确的算法对于某些输人来说,可能根本不会停止,或者停止时给出的不是预期的结果。然而,与人们对不正确算法的看法相反,如果这些算法的错误率可以得到控制的话,它们有时也是有用的。关于这一点,在第31章中研究用于寻找大质数的算法时介绍了一个例子。但是,一般而言,我们还是仅关注正确的算法。

算法可以用英语、以计算机程序或甚至是硬件设计等形式来表达。不论采用哪种形式,唯一的要求就是算法的规格说明必须提供关于待执行的计算过程的精确描述。

算法可以解决哪些类型的问题?

研究人员并不仅仅是针对排序这一计算问题设计了大量的算法(读者在看到本书的厚度时可能也会这么猜想的)。算法的实际应用面很广,例如:

  • 人类基因项目的目标是找出人类DNA中的所有100 000种基因,确定构成人类DNA的30亿种化学基对的各种序列,将这些信息存储在数据库中,并开发出用于进行这方面数据分析的工具。这些步骤中的每一个都需要复杂的算法。该项目所涉及的各个问题的解决方案已超出了本书的范围,但本书中有好几章中的思想在解决这些生物问题时都用到 了,这样就使得科学家们可以有效地利用已有资源来完成任务,并且,当利用实验室技 术可以提取出更多的信息时,就可以带来人、财、物、时间等方面的节约。
  • 因特网使得全世界的人们都能够快速地访问和检索大量的信息。为了能实现这一目的,人们采用了巧妙的算法来管理和操纵大量的数据。这方面必须解决的问题包括寻找好的数据传输路径(第24章将介绍解决这些问题的技术)、利用搜索引擎来快速地找到包含特定信息的网页等(有关技术将在第11章和第32章中介绍)。
  • 电子商务使得商品和服务可以以电子的形式进行谈判和交易。然而,电子商务要想得到广泛应用的话,非常重要的一点就是保持信用卡号、密码、银行结单等信息的私密性。公共密钥加密技术和数字签名技术(将在第31章中介绍)是这一领域内所使用的核心技术,它们的基础就是数值算法和数论理论。
  • 在制造业和其他商业应用中,是否能有效地分配稀有资源常常是非常重要的。例如,石油公司可能希望确定该在何处打井,以求最大化预期效益。美国总统候选人可能希望确定该把竞选宣传的资金花在何处,以使赢得竞选胜利的可能性最大。航空公司可能希望以尽可能小的代价来将机组人员分配到不同的航班上,以便做到既到考虑到每一个航班,又不会违反政府有关航空人员调度的规定。因特网服务提供商可能希望确定该把额外的资源置于何处,以便能够更有效地服务其客户。所有这些都是可以利用线性规划求解向题的例子,这一技术将在第29章中介绍。

尽管这些例子中某些细节已经超出了本书的范围,我们仍给出了适用于这些问题和问题领域的底层支撑技术。此外,在本书中,我们还说明了如何解决许多具体的问题,例如:

  • 给定一幅道路交通图,上面标注出了每一对相邻交叉路口之间的距离。我们的目标就是确定一个交叉路口到另一个交叉路口之间的最短路线。即使不允许每- - 条路线自我交叉,可能的路线数量也会是巨大的。在所有可能的路线中,该如何来选出最短的路线呢?这里,用一个图来对道路交通图进行建模(前者本身就是对实际道路的-种建模;有关图的内容将在第10章和附录B中介绍),希望在图中找出一个顶点到另一个顶点之间的最短.路径。在第24章中,将看到如何来有效地解决这一问题。
  • 给定由n个矩阵所组成的一个序列 <A1A2...,An><A_1,A_2,..., A_n>, 希望确定其乘积Al2...An.因为矩阵乘法是可以结合的,因而存在着若干合法的乘法顺序。例如,如果 n=4n=4,可以按照以下几种顺序来执行矩阵乘法: (A1(A2(A3A4)))(A_1(A_2(A_3A_4))), (A1((A2A3)A4))(A_1((A_2A_3)A_4)), ((A1A2)(A3A4))((A_1A_2)(A_3A_4)), ((A1(A2A3))A4)((A_1(A_2A_3))A_4)(((A1A2)A3)A4)(((A_1A_2)A_3)A_4)。 如果这些矩阵都是正方矩阵(因而其大小都是一样的), 乘法的顺序对矩阵乘法将花多少时间是没有影响的。然而,如果这些矩阵的大小不同的话(但其大小对矩阵乘法来说是相容的),那么,乘法的顺序如何就会带来很大的差别了。可能的乘法结合顺序的数量是n的指数级的,因此,要尝试所有可能顺序的话,可能会花很长的时间。在第15章中,我们将会看到,如何用一种称为动态规划的技术来更为有效地解决这一问题。
  • 给定一个方程 axb(mod nax \equiv b({\rm mod}\ n), 其中 aabbnn 都是整数,希望找出所有(在模 nn 时)满足该方程的整数工。方程的解可能有零个、一个或多个。可以简单地尝试依次用 x=0,1...n1x = 0, 1,...,n-1 来代人该方程,但第31章中给出了一种更为有效的方法。
  • 给定平面上 nn 个点,希望找出这些点的凸壳,即包含这些点的最小凸多边形。从直观上看,可以将每一个点看成是由-块板上突起的一个钉子表示的。因而,包围这些点的凸壳可以看成是一根包围了所有这些钉子的绷紧的橡皮绳。每一个令橡皮绳发生方向变化的钉子都是该凸壳的一个顶点(33.3节的图33-6给出了一个例子)。这些点的2n个子集中的任何一个都可能是该凸壳的顶点。知道哪些点是该凸壳的顶点还不够,还需要知道它们出现的顺序。因此,该凸壳的顶点构成有多种选择。第33章给出了两种用于寻找凸壳的好方法。

上面这些例子远远没有穷尽所有可能的情况(单从本书的重量就能看出这一点了),但也体现了许多有趣算法的两个共同特征:

  1. 有很多候选的解决方案,其中大部分都不是我们所需要的。找到真正需要的解决方案往往不是一件容易的事。
  2. 有着实际的应用。在上面列出的问题中,最短路径问题提供了最简单的例子。运输公司(如汽车货运或铁路公司)对于如何在公路或铁路网中找出最短路径,有着经济方面的利益,因为选取更短的路线可以降低劳动力和燃料成本。还有,在因特网上,一个路由结点也需要在网络中寻找最短路径,以便快速地路由消息。

数据结构

本书还包含了几种数据结构。数据结构是存储和组织数据的一种方式,以便于对数据进行访问和修改。没有哪一种数据结构可以适用于所有的用途和目的,因而,了解几种数据结构的长处和局限性是相当重要的。

技术

尽管可以将本书当作- -本有关算法的“菜谱”(cookbook)来使用,但是,仍然可能在将来的某一天, 碰到一个问题后,一时不太容易找到一个已有的算法来解决它(例如,本书的练习和思考题中有很多就是这样的情况)。本书将教给读者-些算法设计和分析的技术,以便读者自行设计算法、证明其正确性和理解其效率。

一些比较难的问题

本书的大部分都是关于一些比较高效的算法的。衡量算法效率的常用标准是速度,即一个算法得到最后结果所需要的时间。然而,有一些问题至今还没有已知的有效解法。第34章研究了这些问题的一个有趣的子集,即NP完全问题。

为什么说NP完全问题有趣呢?首先,尽管迄今为止都没有谁能找出NP完全问题的有效解法,但也没有人能够证明NP完全问题的有效解法是不存在的。换句话说,NP完全问题是否存在有效算法是未知的。其次,NP完全问题集有一个显著的特点,即如果该集合中的任何一个问题存在有效的算法,则该集合中的其他所有问题都存在有效算法。NP完全问题之间的这种关系,使得缺乏有效的算法变得更为令人着急。第三,有几个NP完全问题类似于(但又不完全同于)一些有着已知有效算法的问题。对一个问题陈述的一点小小的改动,就会对其已知最佳算法的效率带来很大的变化。

对NP完全问题有所了解是很有价值的,因为有些NP完全问题会时不时地在实际应用中冒出来。例如,如果要求你找出有关某一NP完全问题的有效算法,你很可能会花费大量时间去探寻,结果却是徒劳无益的。如果你能证明该问题是NP完全的,就可以把时间花在设计一个有效的算法上,该算法可以给出比较好的、但不一定是最佳可能的结果。我们来看一个具体的例子。假设有一个货车运输公司,它有一个中央仓库。每一天,它都要在仓库中将货物装满货车,并让它驶往若千个地方去送货。在一天结束时,这辆货车必须最后回到仓库,以便下一天再装货物。为了降低成本,该公司希望选择一条送货车行驶距离最短的送货顺序。这一问题即著名的“旅行商人问题”,并且是个NP完全问题。对于该问题,尚没有已知的有效算法。但是,在特定的假设下,该问题存在着有效的算法,它们能够给出比最短可能的距离长不了多少的总体距离。第35章讨论了这种“近似算法”。

练习

  • 1.1-1 给出一个真实世界的例子,其中包含着下列的某种计算问题:排序,确定多矩阵相乘的最佳顺序,或者找出凸壳。
  • 1.1-2 除了运行速度以外,在真实世界问题背景中,还可以使用哪些效率指标?
  • 1.1-3 选择你原来见过的某种数据结构,讨论一下其长处和局限性。
  • 1.1-4 上文中给出的最短路径问题和旅行商人问题有哪些相似之处?有哪些不同之处?
  • 1.1-5 举出一个现实世界的问题例子,它只能用最佳解决方案来解决。再举出另一个例子,在甘由“沂化”屠代解出也兄以解出向斯
该内容转载自 《算法导论》
如有侵权,请联系我删除。
版权归原作者所有,再次转载请遵守原作者相关协议。