本书是《计算机程序设计艺术 第4卷 组合算法》的第0册。本册介绍了组合搜索的历史和演化，涉及组合搜索技术的理论和实践应用；探究了与布尔函数相关的所有重要问题，考察了如何最有效地计算一个布尔函数的值的技术。本册是《计算机程序设计艺术》第7章，即组合搜索这一长篇宏论的起始。

关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践的唯一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
为开始第4卷及后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册子的内容将被归并成每卷综合的最后的版本，而在1962年开始的许多努力将得以完成。
（说明：http://www-cs-faculty.stanford.edu/~knuth/taocp.html包含了与本书及相关图书有关的当前信息。另外，http://www-cs-faculty.stanford.edu/~knuth/sgb.html上有关于斯坦福图库的信息，包括可下载的软件，可用于处理第7章的许多例子中的图。）
第4卷　第0册
本册揭开了计算机程序设计艺术目前最长一章的序幕，而论述组合算法的这章将包括完整的3卷。非正式地说，组合算法是对量非常大的对象，如排列或图元素，进行高速处理的技术。组合模式或排列技术可解决大量的现实问题，而处理这些问题的现代方法比起以前所采用的直接过程快上千倍。本册是后面章节的基础，这里首先讨论的是组合学的本质，接着介绍在计算机内部如何有效处理0和1的基本思想，包括布尔基础和布尔求值等内容。如常，为了强化作者的阐述，书中包括了大量细心组织、包括使用说明和详细解答的新的习题。

将所有好素材都放进一本书显然不可能，对一个主题的某个方面进行适当广泛的讨论甚至也可能导致篇幅的增长失去控制。
　　　　—杰拉尔德·弗兰德（Gerald B. Folland）编辑之角（2005）
　　著书立说最重要之事便是决定置何于卷首。
　　　　—布莱斯·帕斯卡尔（Blaise Pascal）《思想录》740（c.1660）
　　本书是《计算机程序设计艺术，第4卷：组合算法》的第0册。如本书第1卷第1册的前言所述，本书以这种分册的非完整形式出版是因为第4卷的写作将延续多年，而我却迫不及待地等待人们阅读我业已完成的部分内容并提供他们宝贵的反馈意见。
　　从整卷的情况看，本册是组合算法这一宏大篇章的起始。如果我身体状况许可，那么第7章会是《计算机程序设计艺术》一书最长的一章，其最终将划归为至少3个分卷（4A、4B和4C）。和篇幅次长的第5章类似，出现在主要内容之前的是介绍性的材料，其中包含了数十个习题。即将开始的漫漫征途需要备好充足的重要补给。另外，由于第6章的撰写和出版已有30多年了，我需要使第6章过渡到新一章的过程中出现的冲突尽可能少。
　　第7章以7.1节，即0和1，作为合适的起点，虽然层次不同，也是引论性的内容，在此我们深入探究作为计算机基础的布尔函数相关的所有重要问题。其中，7.1.1节为以后要建立的重要上层建筑打下坚实的理论和实践基础，7.1.2节则考虑如何最有效地计算一个布尔函数的值的问题。
　　7.1节的剩余部分7.1.3节和7.1.4节将作为第4卷第1册出版。接着的是7.2节，生成所有的可能性。对应于7.2.1节的分册已经出版，7.2.2节将从总体上对回溯问题进行研究。如果一切顺利，本书的篇章将继续延续，而目前规划的整个第7章的轮廓，可参见封底列出的TAOCP网址。
　　这些介绍性小节的习题数比我原先规划的要多出一倍。事实上，本册的习题总数是难以置信的336，但其中许多十分简单，目的是强化读者对基本概念的理解，或对斯坦福图库（The Stanford GraphBase）的了解。而其他习题真的是很有吸引力的，很有必要在这里出现。不管你相信与否，我拒绝了许多比这里出现的练习更有诱惑力的习题。
感谢Robert W. Floyd，1977年他应我之邀阅读了本书的草稿并给出了数十个极有价值的建设性意见。感谢开放大学的Robin Wilson，他仔细阅读了本书并提出了许多详细的建议。感谢数以百计的读者，他们针对本书草稿提出了许多极具价值的反馈意见并发布于互联网上。
　　对于本书出现的每一个错误，不管是印刷上的、技术上的还是与历史相关的，我都将乐意奉上2.56美元的酬谢给第一个报告的读者。如果你发现了忘了放进索引的条目，也可得到同样的酬谢。每个对行文进行改进的建议的酬谢是32美分（而且，如果你发现了一个习题更好的解，那么你得到的将远非金钱，作为荣誉性的奖励，我会在最后的出版物中列入你的名字）。
　　本册所用但未加说明的记法可参见第1、2或3卷中的记法索引。索引给出了与记法相关的进一步信息之所在（你还可参见各册“记法说明”之下的内容）。当然，未来某个时日，第4卷也会有它自己的记法索引。
　　与尚未完成的内容间的交叉索引有时以“00”标示，这个现在不存在的值留作他日填写实际页码之用。
　　祝大家阅读愉快！

D. E. K.
加利福尼亚，斯坦福
2008年1月

第4卷前言
　　第4卷的标题是组合算法，给出标题的时候我就很想加上一个子标题：我最喜欢的程序设计类型。但我的编辑认为题目应该不带感情色彩。但事实仍是，我一直喜欢散发有组合风味的程序。
　　另一方面，我经常惊奇地发现，在许多人的脑海里，单词“组合”是和计算难度联系在一起的。确实，在Samuel Johnson编著的闻名的英语语言字典（1755）中，他就称其相应的名词“现通常被用于引起痛苦的场合”。同事告诉我他遇到挫折时会说“各种困境的组合打败了我”。为何会这样呢？对我而言，组合学所引发的是完全纯净的喜悦；难道对其他人，它所唤起的会是纯粹的恐慌吗？
　　 确实，组合问题通常和巨大无比的大数相联系。Johnson的字典包括了一个引自Ephraim Chambers的说明，他说道，一个24个字符的字母表上的长度小于等于24的单词量有1 391 724 288 887 252 999 425 128 493 402 200个之多。而对应于10个字符的字母表的单词量是11 111 111 110；当字符数是5时，单词量则是3905。以此推论，当字母表中的字符个数从5到10再到24依此继续增长时，“组合爆炸”问题无疑将会发生。
　　在我的一生中，计算机的处理能力发生了巨大的变化。在输入这些单词时，我知道处理它们的计算机的速度比起我开始致力于此书写作时的IBM 650型计算机快了10万倍，其内存容量也大了10万倍。将来的计算机计算速度会更快，容量也会更大。这些令人惊诧的进步不会降低人们对得到组合问题答案的渴望，而恰恰相反，曾经是不可想象的计算能力的出现激起了人们的期望，刺激了大家的胃口，因为若n仅增量1，组合问题的规模就可能会增大10万倍。
　　组合算法可以非形式化地定义为对组合对象，如排列或图，进行高速操作的技术。我们通常尽力发现满足一定约束条件的最好的可能模式或排列方式。此类问题的数目非常巨大，编写这种程序的技艺通常特别重要又令人着迷，一个好的想法就可省去几年甚至数个世纪的计算时间。
　　实际上，对于组合问题，好的算法有着极大的回报，这也导致了目前该领域研究上的快速发展。许多原先被认为是不可解的难题现在被修正为容易被解决的问题，许多原先被认为是好的算法也变得更加有效了。大约从1970年开始，计算机科学家开始了解到一种被称为“弗洛伊德引理”的现象：似乎需要n3步操作才能解决的问题实际上可在O(n2)步内得到答案，似乎需要n2步操作才能解决的问题实际上可在O(nlogn)步内得到答案，而nlogn通常可归约为O(n)。对于更困难的问题，运行时间也可以从O(2n)降为O(1.5n)再降为O(1.3n)等。一些一般来说仍是困难的问题，也有很简单的重要特例。许多我曾经认为不会有答案的组合问题现在已被解决，当然，问题的突破主要是由于算法的改善而非处理器速度的改进。
到了1975年，这个领域的研究进展突飞猛进，计算机科学重要期刊上发表的很大一部分文章都是针对组合算法的。这些成果不完全是由计算机科学的核心人士做出的，许多重要的贡献是由电子工程、人工智能、运筹学、数学、物理学、统计学和其他领域的工作者做出的。正尝试着完成《计算机程序设计艺术》第4卷写作的我，感到自己似乎是坐在一个水正烧开的水壶盖上，我面临另一种类型的组合爆炸，新的思想正如泉涌般迸发。
　　本系列丛书诞生于1962年初，当时我写下了12章的标题临时列表。那时，仅仅是为了乐趣，我才决定将组合算法的短暂篇章包含其中。“嗨，看一下，大多数人使用计算机来处理数值，而我们能编写处理模式的程序。”在那个时代，给出所有已知的组合算法的完整描述也是容易的事。甚至在1966年，在我完成了大约3000页手写书稿的时候，在业已膨胀的篇幅之中也只有100页是关于第7章的。至于原先以为的一碟“沙拉点心”最后是如何变成一道大餐的，我却完全没有概念。
　　由于越来越多的人参与，起始于1975年的组合研究热仍方兴未艾。旧的思想不断被新的思想所改进，但却很少被取而代之或过时。当然，我不得不放弃我曾经的希望，即围绕整个领域撰写一本最完美、最可靠的著作，使所有的素材都井然有序，给所有希望解决组合问题的人提供一站式的购物便利。在讨论一个小的主题的时候我也几乎无法宣称“这是最后的解决方案，故事到此结束。”取而代之的是，我必须将自己局限于解释大多数目前所遇到的有效组合技术的重要基础原理。到目前为止，我为写作第4卷而搜集的素材比为撰写第1～3卷而准备的材料要多上一倍不止。
　　大量的内容意味着曾经规划的“第4卷”实际上会变成多个自然卷。你现在看的是4A卷，如果我身体健康，4B卷和4C卷也会在某个时日出现，而且（谁知道呢？）也可能会有4D卷、4E卷……但肯定不会有4Z卷。
　　我的计划是系统地浏览我从1962年就开始积累的素材，尽我所能，告诉大家我认为大家还期待着被告知的事情，我并不追求完美，但我想给那些对组合思想作出贡献的所有先驱者们应该享有的荣誉，因此我不会吝啬任何历史细节。此外，对于那些我认为50年之后也是重要的素材，我不会将其舍去，我会使用一到两段的篇幅优雅地对其加以解释；相反，需要冗长证明的困难问题，除了真正基本的主题之外，我就不放在本书进行讨论了。
　　好吧，组合算法的研究范围是如此广泛，显然我是无法涉足所有领域的。哪些重要的东西会被略掉呢？我认为我最大的盲点是几何。因为，比起空间对象，我能更好地想象并操作代数公式。因此在本书中，我不想去尝试处理和计算几何相关的组合问题，如球的紧密堆积问题、n维欧几里得空间中数据点的聚类问题，甚至平面上的Steiner树问题等。更重要的是，在本书我倾向于不涉及多面体组合学问题和基于线性规划、整数规划或半定规划的组合学问题。这些主题在许多书籍已充分讨论，但它们依赖于几何直觉，而对我来说，纯粹的组合学问题则更容易理解。
　　我必须坦白，我对那些仅仅在渐近意义上是有效的算法存有偏见，这些算法直到问题的规模超出了宇宙的边界才有可能呈现出性能上的优越性。目前发表的许多文章都致力于此类算法的研究。我能理解挑战终极极限的诱惑以及建立学术威望对学者的吸引力，但在《计算机程序设计艺术》一书中，对那些我从未考虑过在实际编程中自身会采用的方法，我倾向于只给出简短的说明（当然，对此也有例外，特别是一些涉及核心主题的基本概念，还有一些不切实际但漂亮且/或富有洞察力的方法也包含在书中，其他则是用于说明什么是不该做的指导性例子）。
　　而且，如本书早期出版的其他各卷，本书几乎完全专注于串行算法的讨论，这是有意而为之的。尽管计算机能越来越好地并行执行任务，但我无法判断，涉及并行的这些思想从现在开始的5年或10年之后是否还有用，因此我乐意将此问题留给那些比我睿智的人。串行方法已经挑战了我的智力极限，我不想去辨明未来的精明程序设计者想要知道什么。
当规划如何将素材呈现给读者时，我需要作出的主要决定是应该按问题还是按技术进行内容的组织。例如，第3卷第5章，主要讨论的是一个单独的问题，即如何将数据按序进行排列，对于问题的不同方面，我们应用了几十种不同的技术。与之相反，组合算法涉及许多问题，而可施用的技术种类却很少。最后我认为混合策略应比任何纯粹的策略都要好。因此，你会看到，7.3节处理寻找最短路径问题，7.4.1节讨论图的连通性问题，而其他章节则涉及一些基本技术的讨论，如布尔代数（7.1节）、回溯技术（7.2节）、拟阵理论（7.6节）和动态规划（7.7节）等。著名的旅行商问题虽然没有属于自己的独立小节，但可被不同的方法解决，因此会在不同的地方出现多次。
　　前面提及，在组合计算的研究上已经取得了巨大的进展，但这并非意味着所有的组合问题都已被解决。当一个计算机程序的运行时间变得无法控制时，程序设计者不要期望在本书能找到他所需要的灵丹妙药。虽然本书描述的方法通常会比程序设计者前期自行尝试的方法快上很多，但我们必须面对现实：组合问题很快就会变得极大。我们甚至可以严格证明，某些小而常见的问题，尽管理论上可解，但在现实世界中是不可能得到解的（参见7.1.2节中的Stockmeyer和Meyer定理）。对于其他一些问题，我们甚至无法证明是否会有令人满意的算法存在，但我们知道对于这些问题存在解决方法是不大可能的，因为任何一个有效算法都将导致成千其他问题的解的出现，而这些问题已经难倒了世界上最杰出的专家学者（参见7.9节NP完全问题的讨论）。
　　经验提示，针对新组合问题或旧组合问题的变体或特例，新的组合算法会不断涌现，而人们对于这种算法的需求也将不断增长。面对挑战，程序设计者将使计算机程序设计艺术不断跨越新的巅峰。但是，今天的方法很可能仍有价值。
　　尽管和第1～3卷讨论的主题常有联系，本书的大部分内容是自足的。在前面几卷中，与机器语言相关的底层细节被广泛涉及，但本卷中的算法则独立于任何机器，通常只在抽象层次上进行阐述。然而，组合编程的某些方面严重依赖于底层细节，这在前面是未曾出现过的。在这种情况下，本书都是基于MMIX计算机进行讨论的。MMIX取代了在第一卷早期版本中所定义的MIX机器。关于MMIX机器的细节可参阅《计算机程序设计艺术》第1卷第1册的补充材料，读者也可从因特网下载这些材料，同时可下载的还有MMIX汇编程序和仿真器。
另一个可下载的资源是称为斯坦福图库（The Stanford GraphBase）的程序集和数据集，它们被本书例子所大量引用。我认为学习组合算法最有效、最有意思的方式就是使用该图库，因此我在此鼓励读者充分使用它们。
　　顺便提一下，在撰写作为第7章开场白的介绍性内容时，我很高兴能自然地提及我的博士论文导师Marshall Hall, Jr.（1910—1990）、Hall的论文导师Oystein Ore（1899—1968）和Ore的论文导师Thoralf Skolem（1887—1963）的一些工作。而Skolem的导师Axel Thue（1863—1922）的工作则已在第3卷第6章提及。
　　非常感谢数以百计的读者，他们帮助我在本卷早期的版本中发现了众多的错误，这些版本最初发布于因特网后来再以纸质分册的形式印刷出版。我恐怕还有其他错误仍然潜伏于字里行间，我希望能尽可能地将所有错误予以改正。因此，对于每个技术上的、印刷上的还是历史上的错误的第一个发现者，我都很乐意给予2.56美元的酬谢。在封底的TAOCP网址，你可找到当前已被报告的所有错误的列表。

D. E. K .
加利福尼亚，斯坦福
2008年4月

　　尽管，依我看来，错误是我朋友造成的，但自然地，我要对所有出现的错误负责。　
　　　　—奎斯托·帕察措格卢（Christos H. Papadimitriou），《计算复杂性》（1995）
　　关于引用　对IEEE Transactions杂志的引用由一个用于标识杂志类型的黑体字符后接杂志卷号构成，如“IEEE Trans. C-35”表示IEEE Transactions on Computers第35卷。IEEE不再使用这些便利的字符编码，但对这些编码的辨认并不太难：如“EC”曾用于表示“电子计算机”（Electronic Computers），“IT”表示“信息理论”（Information Theory），“SE”表示“软件工程”（Software Engineering），“SP”表示“信号处理”（Signal Processing），“CAD”表示“集成电路系统的计算机辅助设计”（Computer-Aided Design of Integrated Circuits and Systems）等。

计算机程序设计艺术
第4卷，第0册
本册揭开了计算机程序设计艺术目前最长一章的序幕，而论述组合算法的这章将包括完整的3卷。非正式地说，组合算法是对量非常大的对象，如排列或图元素，进行高速处理的技术。组合模式或排列技术可解决大量的现实问题，而处理这些问题的现代方法比起以前所采用的直接过程快上千倍。本册是后面章节的基础，这里首先讨论的是组合学的本质，接着介绍在计算机内部如何有效处理0和1的基本思想，包括布尔基础和布尔求值等内容。如常，为了强化作者的阐述，书中包括了大量细心组织、包括使用说明和详细解答的新的习题。
Donald E. Knuth由于在算法和程序设计技术方面的先驱性工作，由于发明了计算机排版系统TEX和METAFONT，以及由于他的富于创造力的，影响深远的论著，Knuth名扬全球。作为斯坦福大学计算机程序设计艺术荣誉退休教授，Knuth现在正投入全部的精力来完成这些分册以及包含这些分册的七卷著作。

关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
　　为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。

（说明：http://www-cs-faculty.stanford.edu/~knuth/taocp.html包含了与本书及相关图书有关的当前信息。http://www-cs-faculty.stanford.edu/~knuth/sgb.html上有关于斯坦福图库的信息，包括可下载的软件，可用于处理第7章的许多例子中的图。）

（美）Donald E.Knuth 著：暂无简介

黄林鹏 等译：200240上海市闵行东川路800号上海交通大学计算机系

本书是克努特（Knuth，中文名为高德纳，亦翻译为克鲁特）巨著《计算机程序设计艺术》第4卷第0册的双语版（中文版），自从第4卷第2、3、4册的双语版出版以来，众多读者翘首以待第4卷前面各册双语版的出版已经有一段时日了，希望本书不会让大家失望。
　　译者最早是在20世纪80年代初在图书馆看到标为“克鲁特著，管纪文、苏运霖译”的《计算机程序设计技巧》多卷本的，那时译者在浙江大学上大学，正学习Aho等著的《计算机算法的设计与分析》（由译者翻译的该书中文版已由机械工业出版社出版），由于当时用的是原版书籍，许多概念一头雾水，正是该书帮我澄清了很多概念，打发了许多时间，也培养了我阅读的兴趣。
　　后来写些小论文，经常使用LaTeX这个软件，惊叹于它的美丽，看了软件的说明，知道是从事分布式计算研究的著名学者兰伯特（Leslie Lamport）在克努特的TeX上构建的宏集，也了解了克努特暂时中断巨著撰写的原因，明白了“工欲善其事，必先利其器”的道理。
　　事实上，克努特从来就没有中断过巨著的写作计划，几十年来他孜孜不倦地搜集素材，了解计算机科学各方面的进展，我们期望他身体康健，厚积博发（这里没有写错）。
2000年我在哈佛大学进修的时候，研究程序设计语言的Ramsey教授邀请克努特到哈佛来做个讲座，我才遇到他本人，看到的是无腿水晶眼镜后面那双睿智的眼睛，听到的是娓娓道来的各种典故新说，他介绍的是他自行设计的MMIX计算机，虽然一开始克努特就说道，我要讲到没有一个人想听的时候为止。可教室的十多个人都倾心听讲并不时发问，直到晌午，大家吃了主持者叫来的外卖比萨，还孜孜不倦地继续讨论着他设计的新千年RISC机器。
　　借此机会再谈一下本书，本书是第4卷第0册，介绍的是组合搜索的一些预备知识，要阅读第4卷后面各册的读者最好先读一下本书。另外，《计算机程序设计艺术》一书的很多习题富有挑战性，按照作者的标记，0是最容易的题目，45是已解决的难题，如费马大定理等，而大于45的基本是未知答案的难题，这也给大家设立算法研究目标提供了参考。
本书的习题和解答由杜思奇、曾慧清、张王朋和恽筱源初译，最后由黄林鹏整理。本书的翻译还得到孙永强教授和梅宏、童维勤、陆朝俊、陈翌佳等的帮助，在此表示真挚的谢意。
对于此书的翻译，说实在话，一是英语非译者母语，新翻译卷册的质量恐难延续苏运霖教授翻译的广受好评的三卷；二是整书涉及内容非常广泛，译者肯定力有不逮。无奈出版社多次提及，译者只能勉强为之。错误难免，如果读者发现敬请发到lphuang@sjtu.edu.cn，以便再版修改，不胜感激。

黄林鹏
于上海交通大学
2009年12月

PREFACE iii
PREFACE TO VOLUME 4 v
Chapter 7　 Combinatorial Searching
7.1　 Zeros and Ones 47
7.1.1　 Boolean Basics 47
7.1.2　 Boolean Evaluation 96
Answers to Exercises 134
Index and Glossary 201


译者序 219
前言 221
第4卷前言 223
第7章　 组 合 搜 索
7.1　0和1 274
7.1.1　布尔基础 274
7.1.2　布尔求值 321
习题答案 356