《计算机程序设计艺术》卷4A：组合算法（英文原版）

需积分: 45 67 浏览量更新于2024-07-17 1 收藏 10.62MB PDF 举报

"《计算机程序设计艺术》第四卷第1部分：组合算法，英文原版，带完整书签" 《计算机程序设计艺术》是Donald E. Knuth所著的一部计算机科学的经典巨著，该系列书籍深入探讨了算法的理论与实践。这本书的第四卷分为多个部分，其中"Volume 4A/Combinatorial Algorithms, Part 1"专注于组合算法，这是计算科学中至关重要的一部分，涉及如何有效地处理和分析大量数据。在这一部分中，Knuth教授会详细介绍如何运用数学和逻辑思维来设计和分析高效的算法，这对于计算机科学家和软件工程师来说是必备的知识。组合算法通常涉及到排列、组合、图论、搜索问题以及各种优化策略。这些算法在现代计算机科学中的应用广泛，包括数据挖掘、机器学习、网络路由、数据库索引等众多领域。书中可能涵盖了以下几个关键主题： 1. 排列与组合：学习如何计算给定对象的不同排列和组合方式，这是组合数学的基础，对于理解和设计算法至关重要。 2. 图论：研究图的性质和操作，如遍历算法、最短路径算法（如Dijkstra算法和Floyd-Warshall算法）以及最小生成树算法（如Prim算法和Kruskal算法）。 3. 搜索与优化：包括回溯法、分支限界法、动态规划等，这些都是解决复杂问题的有效方法。 4. 编码与数据结构：如何高效地存储和检索信息，如哈希表、二叉堆、B树等数据结构的设计和应用。 5. 概率和随机算法：有时，利用概率方法可以设计出高效的算法，如蒙特卡洛方法和拉斯维加斯方法。 6. 算法分析：通过时间复杂性和空间复杂性的分析，理解算法效率并优化算法性能。这本书的每一章都可能包含详细的实例、习题和复杂的分析，旨在帮助读者深入理解算法背后的原理。书签的存在使得读者能够方便地定位到特定的主题或问题，这对学习和参考非常有用。此外，书中引用了Vikram Seth的《The Golden Gate》中的一首诗，表明Knuth在严谨的学术论述中也融入了文学元素，这正是他作品的特色之一。尽管是英文原版，但书中的表述清晰，逻辑严密，即使是中文背景的读者也能从中受益匪浅。最后，这本书对批量购买提供了优惠，适合于企业、教育机构或个人作为学习和教学资料。通过定制内容和封面，可以更好地适应特定的培训目标、市场定位和品牌需求。《计算机程序设计艺术》第四卷第1部分是计算机科学领域不可多得的参考资料，对于想要提升算法设计和分析能力的读者来说，是一本必读之作。

CONTENTS

Chapter 7 — Combinatorial Searching . . . . . . . . . . . . . . . . 1

7.1. Zeros and Ones . . . . . . . . . . . . . . . . . . . . . . . . . 47

7.1.1. Boolean Basics . . . . . . . . . . . . . . . . . . . . . . . 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 to Exercises . . . . . . . . . . . . . . . . . . . . . . . . 514

Appendix A — Tables of Numerical Quantities . . . . . . . . . . . . 818

1. Fundamental Constants (decimal) . . . . . . . . . . . . . . 818

2. Fundamental Constants (hexadecimal) . . . . . . . . . . . . 819

3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers . . . 820

Appendix B — Index to Notations . . . . . . . . . . . . . . . . . . 822

Appendix C — Index to Algorithms and Theorems . . . . . . . . . . 828

Appendix D — Index to Combinatorial Problems . . . . . . . . . . . 830

Index and Glossary . . . . . . . . . . . . . . . . . . . . . . . . . 834

2 COMBINATORIAL SEARCHING 7

For example, consider the question of existence. Trial and error quickly

reveals that, when n = 5, we cannot place {1, 1, 2, 2, . . . , 5, 5} properly into ten

positions. The two 1s must both go into even-numbered slots, or both into odd-

numbered slots; similarly, the 3s and 5s must choose between two evens or two

odds; but the 2s and 4s use one of each. Thus we can’t ﬁll exactly ﬁve slots of

each parity. This reasoning also proves that the problem has no solution when

n = 6, or in general whenever the number of odd values in {1, 2, . . . , n} is odd.

In other words, Langford pairings can exist only when n = 4m−1 or n = 4m,

for some integer m. Conversely, when n does have this form, Roy O. Davies has

found an elegant way to construct a suitable placement (see exercise 1).

How many essentially diﬀerent pairings, L

, exist? Lots, when n grows:

= 1;

= 26;

= 17,792;

= 39,809,640;

= 256,814,891,280;

= 3,799,455,942,515,488;

= 1;

= 150;

= 108,144;

= 326,721,800;

= 2,636,337,861,200;

= 46,845,158,056,515,936.

(1)

[The values of L

and L

were determined by M. Krajecki, C. Jaillet, and A. Bui

in 2004 and 2005; see Studia Informatica Universalis 4 (2005), 151–190.] A seat-

of-the-pants calculation suggests that L

might be roughly of order (4n/e

)

n+1/2

when it is nonzero (see exercise 5); and in fact this prediction turns out to be

basically correct in all known cases. But no simple formula is apparent.

The problem of Langford arrangements is a simple special case of a general

class of combinatorial challenges called exact cover problems. In Section 7.2.2.1

we shall study an algorithm called “dancing links,” which is a convenient way to

generate all solutions to such problems. When n = 16, for example, that method

needs to perform only about 3200 memory accesses for each Langford pair

arrangement that it ﬁnds. Thus the value of L

can be computed in a reasonable

amount of time by simply generating all of the pairings and counting them.

Notice, however, that L

is a huge number — roughly 5 × 10

, or about

1500 MIP-years. (Recall that a “MIP-year” is the number of instructions exe-

cuted per year by a machine that carries out a million instructions per second,

namely 31,556,952,000,000.) Therefore it’s clear that the exact value of L

was determined by some technique that did not involve generating all of the

arrangements. Indeed, there is a much, much faster way to compute L

, using

polynomial algebra. The instructive method described in exercise 6 needs O(4

operations, which may seem ineﬃcient; but it beats the generate-and-count

method by a whopping factor of order ((n/e

)

n−1/2

), and even when n = 16

it runs about 20 times faster. On the other hand, the exact value of L

100

will

probably never be known, even as computers become faster and faster.

We can also consider Langford pairings that are optimum in various ways.

For example, it’s possible to arrange sixteen pairs of weights {1, 1, 2, 2, . . . , 16, 16}

that satisfy Langford’s condition and have the additional property of being “well-

7 COMBINATORIAL SEARCHING 3

balanced,” in the sense that they won’t tip a balance beam when they are placed

in the appropriate order:

16 6 9 15 2 3 8 2 6 3 13 10 9 12 14 8 11 16 1 15 1 5 10 7 13 4 12 5 11 14 4 7

. (2)

In other words, 15.5·16+14.5·6+···+0.5·8 = 0.5·11+···+14.5·4+15.5·7; and

in this particular example we also have another kind of balance, 16+6+···+8 =

11+16+ ···+ 7, hence also 16·16+ 15 ·6 +···+1·8 = 1 ·11+···+15·4 + 16 ·7.

Moreover, the arrangement in (2) has minimum width among all Langford

pairings of order 16: The connecting lines at the bottom of the diagram show

that no more than seven pairs are incomplete at any point, as we read from left

to right; and one can show that a width of six is impossible. (See exercise 7.)

What arrangements a

. . . a

of {1, 1, . . . , 16, 16} are the least balanced,

in the sense that



k=1

is maximized? The maximum possible value turns

out to be 5268. One such pairing — there are 12,016 of them — is

2 3 4 2 1 3 1 4 16 13 15 5 14 7 9 6 11 5 12 10 8 7 6 13 9 16 15 14 11 8 10 12. (3)

A more interesting question is to ask for the Langford pairings that are

smallest and largest in lexicographic order. The answers for n = 24 are

{abacbdecfgdoersfpgqtuwxvjklonhmirpsjqkhltiunmwvx,

xvwsquntkigrdapaodgiknqsvxwutmrpohljcfbecbhmfejl}

(4)

if we use the letters a, b, . . . , w, x instead of the numbers 1, 2, . . . , 23, 24.

We shall discuss many techniques for combinatorial optimization in later sec-

tions of this chapter. Our goal, of course, will be to solve such problems without

examining more than a tiny portion of the space of all possible arrangements.

Orthogonal latin squares. Let’s look back for a moment at the early days of

combinatorics. A posthumous edition of Jacques Ozanam’s Recreations math-

ematiques et physiques (Paris: 1725) included an amusing puzzle in volume 4,

page 434: “Take all the aces, kings, queens, and jacks from an ordinary deck of

playing cards and arrange them in a square so that each row and each column

contains all four values and all four suits.” Can you do it? Ozanam’s solution,

shown in Fig. 1 on the next page, does even more: It exhibits the full panoply

of values and of suits also on both main diagonals. (Please don’t turn the page

until you’ve given this problem a try.)

By 1779 a similar puzzle was making the rounds of St. Petersburg, and it

came to the attention of the great mathematician Leonhard Euler. “Thirty-six

oﬃcers of six diﬀerent ranks, taken from six diﬀerent regiments, want to march

in a 6 ×6 formation so that each row and each column will contain one oﬃcer of

each rank and one of each regiment. How can they do it?” Nobody was able to

剩余900页未读，继续阅读

tzc_yujunyong

粉丝: 1
资源: 17

《计算机程序设计艺术》卷4A：组合算法（英文原版）

C++经典之作：《计算机程序设计艺术》深度解析

深入理解《计算机程序设计艺术》与单片机开发经验分享

1982游戏设计经典：《The Art of Computer Game Design》电子版

The Art of Computer Programming Volume 3 , 2nd Edition(计算机程序设计艺术).pdf

The Art of Computer Programming Volume 2, 3rd Edition(计算机程序设计艺术).pdf

The Art of Computer Programming Volume 4, Fascicle 6(计算机程序设计艺术).pdf

The Art of Computer Programming Volume 4A, Combinatorial Algorithms

The Art of Computer Programming, Volume 4A, draft edition.

The.Art.of.Computer.Programming.计算机程序设计艺术.Vol1-3

计算机程序设计艺术The.art.of.computer.programming.Volume.3.英文版.part1

最新资源