基本信息
- 原书名:The Art of Computer Programming,Volume 4 A:Combinatorial Algorithms,Part 1
- 原出版社: Addison-Wesley
编辑推荐
这是一部包含一切基础算法的宝典,是它教给了这一代软件开发人员关于计算机程序设计的绝大多数知识
高德纳编著的《计算机程序设计艺术(卷4A组合算法1英文版)》主要介绍了组合算法,内容涉及布尔函数、按位操作技巧、元组和排列、组合和分区以及所有的树等。
内容简介
作译者
1938 年1月10日出生于美国明尼苏达州的米尔沃基,著名计算机科学家,算法与程序设计技术的先驱,斯坦福大学计算机系荣誉退休教授,计算机排版系统TEX和 METAFONT字体系统的发明人,最年轻的图灵奖得主。他在计算机科学及数学领域出版和发表了多部具有广泛影响的著作和论文。
他获得了很多奖项和荣誉:
1971年获首届美国计算机协会(ACM) Grace Murray Hopper奖
1973年当选为美国科学艺术学院院士
1974年获美国计算机协会图灵奖
1975年当选为美国国家科学院院士,同年荣获美国数学协会(MAA)福特奖(Lester R. Ford Award)
1979年获卡特总统颁发的美国科学奖
1981年当选为美国工程院院士
1982年获计算机先锋奖(Computer Pioneer Award)
1982年成为IEEE荣誉会员
1986年荣获美国数学学会(AMS)斯蒂尔奖(Steele Award)
1988年获富兰克林奖章(Franklin Medal)
1994年获瑞典科学院Adelskold奖
1995年获IEEE冯?诺依曼奖
1996年获稻盛基金会京都奖(Kyoto Prize)
Knuth的中文名字高德纳广为人知,这是1977年他访问中国之前由姚期智教授的夫人姚储枫所取。
目录
Chapter 7—Combinatorial Searching 1
7.1. Zeros and Ones 47
7.1.1. Boolean Basice 47
7.1.2. Boolean Evaluation 96
7.1.3 Bitwise Tricks and Techniques 133
7.1.4. Binary Decision Diagrams 202
7.2. Generating All Possibilities 281
7.2.1. Generating Basic Combinatorial Patterns 281
7.2.1.1. Generating all n-tuples 281
7.2.1.2. Generating all permutations 319
7.2.1.3. Generating all combinations 355
7.2.1.4. Generating all partitions 390
7.2.1.5. Generating all set partitions 415
7.2.1.6. Generating all trees 440
7.2.1.7. History and further references 486
Answers 59 Exercises 514
Appendix A—Tables of Numerical quantities 818
1. Fundamental Constants(decimal) 818
2. Fundamental Constants(hexadecimal) 819
前言
——Gerald B. Folland,“编者之角”(2005)
卷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 Type 650计算机快10万倍以上,而且现在这台电脑的存储容量也比那时大10万倍以上。明天的计算机还会更快并具备更大的容量。然而,这些惊人的进展没有减少人们对于回答组合问题的渴求,情况恰好相反。从前无法想象的如此快速的计算能力提高了我们的期待,并且激起我们更大的欲望——事实上,n只要增加1,组合问题的规模都有可能增加10万倍以上。
可以把组合算法非正式地定义为对排列或图这样一些组合对象的高速处理方法。我们向来试图找出一些模式或排列作为满足约束条件的最佳方法。这种问题的数量非常大,而且编写这类程序的技巧特别重要,很吸引人,因为有时只要一个好主意就可能节省几年乃至几百年计算机时间。
组合问题的优良算法具有巨大回报,这个事实激励了技术水平的突飞猛进。许多过去认为很难处理的问题现在可能迎刃而解,许多过去以优良著称的算法现在变得更好。大约从1970年起,计算机科学家们经历了所谓的“Floyd引理”现象:看似需用n3次运算的问题实际上可能用O(n2)次运算就能求解,看似需用n2次运算的问题实际上可能用O(n lg n)次运算就能处理,而且n lg n通常还可以减少到O(n)。一些更难的问题的运行时间也从O(2n)减少到O(1.5n),再减少到O(1.3n),等等。一般说来,剩下的问题依然是很困难的,但是已经发现它们有一些非常简单的重要特例。我曾经以为在我有生之年不会看到答案的许多组合问题,如今已经获得解决,而且那些突破的取得主要归功于算法的改进而不是处理器速度的提高。
截至1975年,这方面的研究进展神速,主要的计算机期刊上发表的大量论文竟然都是有关组合算法的。同时,这些进展不仅是由核心的计算机科学领域的研究人员取得的,而且大量成果也来自电子工程、人工智能、运筹学、数学、物理学、统计学等各领域的研究人员。我曾想尽快完成《计算机程序设计艺术,卷4》的写作,但是感觉自己就像坐在烧开了直冒汽的一壶水旁边,只不过我面对的是层出不穷的新主意的大爆炸!
这套书诞生于1962年之初,当时我天真地拟好一共12章的提纲。未经深思熟虑,我便决定用其中一章来简述组合算法,心想:“请看,大多数人利用计算机处理数字,而我还能够编写处理计算模式的程序!”在那个时期,对于已知的每个组合算法,都能很容易给出一个非常完备的描述。即使到1966年,当我把这本已经过度膨胀的书写好约3000页初稿的时候,其中第7章的内容还不到100页。我绝对不会想到,当初预计作为“沙拉”的小菜最终竟然会升格成一道主菜。
1975年兴起的组合学热潮,在越来越多人的参与下一浪高过一浪。新思想不断改善着旧思想,但是很少取而代之,或者使其过时。所以,我自然就得抛弃曾经的希望,已经不可能围绕这个领域撰写一本一劳永逸的书,把一切题材组织得井然有序,让需要解决组合问题的每个人“一册在手,别无他求”。各种各样可用的技术如雨后春笋般破土而出,我几乎对任何支节问题都不可能做到说:“这是最后的解决方案:故事结束了。”相反,我必须把自己严格限制在只阐明一些最重要的原理,而这些原理应该是迄今我所遇见的所有有效的组合方法的基础。现在我为卷4积累的原始资料是卷1至卷3全部资料的两倍还不止。
这些堆积如山的资料意味着实际上必须把我以往计划的“卷4”变成若干卷。读者现在见到的是卷4A。假设我身体健康,以后还会有卷4B和卷4C,并且(天知道?)可能还有卷4D、卷4E……当然肯定不会出现卷4Z。
现在的计划是通过自1962年以来积累的文档,尽我所能,系统地讲述(其实仍然有待进一步讨论的)组合方法。我无意追求完美,但是一定要把应有的荣誉归于所有那些提出关键思想的先驱,所以对于历史情况我不会惜墨如金。除此之外,凡是我以为在今后50年仍然具有重要性的某些内容,以及能用一两段文字简洁说明的某些内容,我都不能割爱。反过来,我没有把那些需要长篇累牍证明的艰深话题收录进来,除非它确实是基础性的。
不错,组合算法这个领域显然是广阔的,我不能顾及它的所有方面。那么,我忽视了什么最重要的东西呢?我以为我的最大盲点是在几何上,因为我最擅长的始终是呈现和操作代数公式而非空间对象。所以,在这几本书中,我不准备讨论与计算几何有关的组合问题,如球的密堆积,n维欧几里得空间中数据点的分类,甚至也不讨论平面内的Steiner树问题。更重要的是,我力求避开多面体组合学,以及主要基于线性规划、整数规划或半定规划的各种方法。那些内容在有关这个主题的其他很多书中已被较好地涉及,而且它们依赖于几何直觉知识。单纯从组合问题展开讨论对我来说是更容易理解的。
我还必须承认,对于那些仅在渐近意义下有效的组合算法,以及优越性能直到问题规模超越乎想象时才开始显现的组合算法,我不太感冒。现在有大量出版物讨论这类算法。我能理解有的人喜欢思考极限问题,认为它是个智力挑战并且能带来学术声望,但是我这本书对于我自己在实际程序中不考虑使用的任何方法,一般只是轻描淡写。这条规则的运用自然也有例外,特别是对那些处于主题中心的基本概念就不是这样。(某些不实用的方法实在是非常优美或者含义深刻,让我不能割舍,还有些方法则被我作为反例引用。)
此外,在这套书的前几卷中,我有意讲的都是顺序算法,尽管计算机的并行计算能力日益增强。对于哪些并行算法可能在今后5年或者10年中会很有用,我判断不好,更不用说50年后了,所以我乐于把这样的问题留给那些比我聪明的人。明日才华横溢的程序员们应该具备什么样的顺序算法知识,单是这个问题就足够考验我自己的能力了。
在陈述这些材料时,我需要作出的一个主要决定是按问题还是按方法组织它们。例如,卷3中的第5章专门讨论一个问题,即数据排序,我们从不同方面应用了20余种方法。相比之下,组合算法涉及许多不同的问题,而解决问题的方法则少很多。最终我断定,采用一种混合策略会比任何一种单纯的方法能够更好地组织材料。于是在这几本书中,7.3节处理求最短路径问题,7.4.1节处理连通性问题,但是其他许多节则专门讨论基本方法,如布尔代数的应用(7.1节)、回溯(7.2节)、拟阵理论(7.6节)或者动态规划(7.7节)。著名的流动推销员问题,以及与覆盖、着色和填充有关的其他经典组合问题,没有单辟章节讨论,但是它们在书中多次出现,每次都用不同的方法处理。
我已经提到过组合计算技术的巨大进步,但是我并不是暗示人们已经解决了所有的组合问题。在计算机程序的运行时间难以掌控之际,程序员们不能指望从本书中找到无坚不摧的“银弹”。这里描述的方法通常会比一个程序员先期尝试的方法快很多,但是让我们面对这样一个现实:组合问题一不小心就会迅速地成为巨大的问题。我们甚至可以严格证明,就连一个自然的小问题也不存在现实的可解,尽管原则上它是可行解的(参见7.1.2节的Stockmeyer和Meyer定理)。还有些情况下,我们尚不能证明一个给定问题不存在合适的算法,只是知道可能没有这样的算法,因为任何有效的算法将会产生一种有效方法,帮我们解决一大批难倒世上无数英雄好汉的问题(参见7.9节关于NP问题的讨论)。
媒体评论
这是一部包含一切基础算法的宝典,是它教给了这一代软件开发人员关于计算机程序设计的绝大多数知识。
——Byte杂志1995年9月刊
无数的读者谈到过Knuth的著作对于自己的深刻影响。从事研究的人惊讶于他精美优雅的分析,而普通程序员则一直在卓有成效地利用书中提供的各种方案解决日常问题。这些书展现了作者的博观、清晰、精确和幽默,所有的人都钦佩不已。
我简直说不清楚这些书给我的学习和娱乐带来了多少欢乐时光。我在各种场合一有空就仔细研读,在车上,在餐馆,上班 时,回到家里??甚至有次观看我儿子的球赛,趁他没上场的时候,我还拿出来看了一阵子。
——Charles Long
它本来是当参考书写的,但有些人却发现每一卷都可以兴致勃勃地从头读到尾。有位中国的程序员甚至把它比做读诗。
如果你自以为是一个很好的程序员,请去读读Knuth的《计算机程序设计艺术》吧??要是你真把它读下来了,就毫无疑问可以给我递简历了。
——比尔.盖茨
不管你的背景如何,只要你想认真地编写计算机程序,都有很好的理由把这套书的每一卷抱回家,便于研究和工作时随时翻阅。
20年来Knuth第一次全部修订了这3卷。我发现,只要翻一翻这些书,就会立竿见影地“镇住”计算机。
——Jonathan Laventhol