算法导论——第1章 算法在计算中的作用

简介

什么是算法？为什么算法值得研究？相对于计算机使用的其他技术来说算法的作用是什么？

本章我们将回答这些问题。

1.1 算法

算法就是任何良定义（well-defined）的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。

良定义（well defined）就是指无歧义的、不会导致矛盾的、符合其应满足的所有要求的定义

问题陈述说明了期望的输入和输出之间的关系。算法描述实现这个关系的计算过程。

问题实例由计算该问题所必须的（满足问题陈述中的各种约束条件的）输入组成。

若对每个输入实例，算法都以正确的输出停机，则称该算法是正确的，并称该算法解决了给定的计算问题。

算法解决的问题：

1. 人类基因工程。识别人类DNA中的所有10万个基因，确定构成DNA的30亿个化学基对的序列，在数据库中存储这类信息并为数据分析开发工具。
2. 互联网使得全世界的人都能快速地访问与检索大量信息。借助于一些聪明的算法，互联网上的网站能够管吗理和处理这些海量数据。必须使用算法的问题示例包括为数据传输寻找好的路由（求解这些问题的技术在第24章给出），使用一个搜索引擎来快速地找到特定信息所在的网页（有关技术在11章和32章中）
3. 电子商务使得货物与服务能够以电子方式洽谈与交换，并且它依赖于像信用卡号、密码和银行结单这类个人信息的保密性。电子商务中使用的核心技术包括(第31章中包含的)公钥密码与数字签名，它们以数值算法和数论为基础。
4. 制造业和其他商务企业常常需要按最有益的方式来分配稀有资源。一家石油公司也许希望知道在什么地方设置其油井，以便最大化其预期的利润。一位政治候选人也许想确定在什么地方花钱购买竞选广告，以便最大化赢得竞选的机会。一家航空公司也许希望按尽可能最廉价的方式把乘务员分配到班机上，以确保每个航班被覆盖并且满足政府有关乘务员调度的法规。一个互联网服务提供商也许希望确定在什么地方放置附加的资源，以便更有效地服务其顾客。所有这些都是可以用线性规划来求解的问题的例子，我们将在第29章学习这种技术。

更加具体的问题：

1. 给定一张交通图，上面标记了每对相邻十字路口之间的距离，我们希望确定从一个十字路口到另一个十字路口的最短道路。
   即使不允许穿过自身的道路，可能路线的数量也会很大。在所有可能路线中，我们如何选择哪一条是最短的？
   这里首先把交通图(它本身就是实际道路的一个模型)建模为一个图(第六部分和附录B将涉及这个概念)，然后寻找图中从一个顶点到另一个顶点的最短路径。第24章将介绍如何有效地求解这个问题。
2. 给定两个有序的符号序列X和Y，求出X和Y的最长公共子序列。
   X的子序列就是去掉一些元素(可能是所有，也可能一个没有)后的X。例如，(A，B，C，D，E，F，G)的一个子序列是(B，C，E，G)。X和Y的最长公共子序列的长度度量了这两个序列的相似程度。例如，若两个序列是DNA链中的基对则当它们具有长的公共子序列时我们认为它们是相似的。
   若X有m个符号且Y有n个符号，则X和Y分别有2^m和2^n个可能的子序列。除非m和n很小，否则选择X和Y的所有可能子序列做匹配将花费使人望而却步多的时间。第15章将介绍如何使用一种称为动态规划的一般技术来有效地求解这个问题。
3. 给定一个依据部件库的机械设计，其中每个部件可能包含其他部件的实例，我们需要依次列出这些部件，以使每个部件出现在使用它的任何部件之前。若该设计由n个部件组成，则存在n!种可能的顺序，其中n!表示阶乘函数。
   因为阶乘函数甚至比指数函数增长还快，（除非我们只有几个部件，否则）先生成每种可能的顺序，再验证按该顺序每个部件出现在使用它的部件之前，是不可行的。这个问题是拓扑排序的一个实例，第22章将介绍如何有效地求解这个问题。
4. 给定平面上的n个点，我们希望寻找这些点的凸壳。凸壳就是包含这些点的最小的凸多边形。直观上，我们可以把每个点看成由从一块木板钉出的一颗钉子来表示。凸壳则由一根拉紧的环绕所有钉子的橡皮筋来表示。如果橡皮筋因绕过某颗钉子而转弯，那么这颗钉子就是凸壳的一个顶点(例子参见图33-6)。
   n个点的2”个子集中的任何一个都可能是凸壳的顶点集。仅知道哪些点是凸壳的顶点还很不够，因为我们还必须知道它们出现的顺序。所以为求凸壳的顶点，存在许多选择。第33章将给出两种用于求凸壳的好方法。

从上述问题中，算法问题共有的两个特征：

1. 存在许多候选解，但绝大多数候选解都没有解决手头的问题。寻找一个真正的解或一个最好的解可能是一个很大的挑战。
2. 存在实际应用。在上面所列的问题中，最短路径问题提供了最易懂的例子。一家运输公司(如公路运输或铁路运输公司)对如何在公路或铁路网中找出最短路径，有着经济方面的利益，因为采用的路径越短，其人力和燃料的开销就越低。互联网上的一个路由结点为了快速地发送一条消息可能需要寻找通过网络的最短路径。

数据结构是一种存储和组织数据的方式，旨在便于访问和修改。

技术。虽然可以把本书当做一本有关算法的“菜谱”来使用，但是也许在某一天你会遇到一个问题，一时无法很快找到一个已有的算法来解决它（例如本书中的许多练习和思考题就是这样的情况）。
本书将教你一些算法设计与分析的技术，以便你能自行设计算法、证明其正确性和理解其效率。
不同的章介绍算法问题求解的不同方面。有些章处理特定的问题，例如，第9章的求中位数和顺序统计量，第23章的计算最小生成树，第26章的确定网络中的最大流。其他章介绍一些技术，例如第4章的分治策略，第15章的动态规划，第17章的摊还分析。

难题。NP完全问题中每个问题的复杂度与整个类的复杂度有关联性，假如其中任意一个问题在多项式时间内可解的，则这一类问题都是多项式时间可解。这类问题没有已知的有效算法，但我们可以找到一些“近似算法”。

并行性。为了从多核计算机获得最佳的性能，设计算法时必须考虑并行性。第27章给出了充分利用多核的“多线程”算法的一个模型。从理论的角度来看，该模型具有一些优点，它形成了几个成功的计算机程序的基础，包括一个国际象棋博弈程序。

1.2 作为一种技术的算法

有效的算法可以帮助我们明智地去使用时间（计算时间）和空间（存储器空间）资源。

效率。为求解相同问题而设计的不同算法在效率方面常常有显著差别，这些差别可能比由于硬件和软件造成的差别要重要得多。

我们应该像计算机硬件一样把算法看成一种技术，因为整个系统的性能不但依赖于快速的硬件也依赖于有效的算法。

相对于其他先进技术，算法也是十分重要的技术。因为所有这些都广泛地使用算法，算法是当代计算机中使用的大多数技术的核心。

总结

这章概述算法这种技术，让读者认识一些算法概念，知道算法的地位和重要性。