"深入探讨计算机程序设计艺术：第4卷第5册C Dancing Links1"

需积分: 0 194 浏览量更新于2024-04-11 收藏 1.07MB PDF 举报

The fourth volume of "The Art of Computer Programming" by Donald E. Knuth, titled "Dancing Links", delves into the intricacies of computer program design. This volume explores the concept of Dancing Links, a data structure used in algorithm implementation and problem-solving. Knuth, a renowned computer scientist from Stanford University, provides readers with a comprehensive guide to understanding and utilizing this powerful tool. In "Dancing Links", Knuth delves deep into the principles behind this data structure, explaining its applications in various areas of computer science. From algorithm optimization to Sudoku solving, Dancing Links offer a versatile and efficient method for tackling complex computational problems. Through detailed examples and thorough explanations, Knuth guides readers through the intricacies of implementing and utilizing Dancing Links in their own programs. The book emphasizes the importance of efficient and elegant program design, highlighting the significance of well-constructed algorithms in computer science. Knuth's expertise and insight shine through as he provides readers with valuable techniques for improving code quality and performance. By mastering the concepts presented in "Dancing Links", programmers can enhance their problem-solving skills and develop more efficient solutions to a wide range of challenges. Overall, "Dancing Links" is a valuable resource for any programmer looking to deepen their understanding of computer program design. Knuth's expertise and comprehensive approach make this volume an essential addition to the library of any serious programmer. Whether you are a novice or an experienced coder, this book offers valuable insights and practical guidance for honing your skills and becoming a more effective and efficient programmer.

April 15, 2017

7.2.2.1

DANCING LINKS

Fig. 72.

Solution to the puzzle of the

hidden mathematiians (Fig. 71). No-

tie that the entral letter

atually

partiipates in six dierent names:

BERTRAND

GLAISHER

HERMITE

HILBERT

KIRCHHOFF

WEIERSTRASS

The

to its left partiipates in ve.

Here's what the leftover letters say:

These authors of early papers in

Ata

Mathematia

were ited years later

The Art of Computer Program-

ming

O T H E S C A T A L A N D A U

T S E A P U S T H O R S R O F

T L S E E A Y R R L Y H A P A

E P E A R E L R G O U E M S I

N N A R R C V L T R T A A M A

I T H U O T E K W I A N D E M

L A N T N B S I M I C M A A W

L G D N A R T R E B L I H C E

E R E C I Z E C E P T N E D Y

M E A R S H R H L I P K A T H

E J E N S E N H R I E O N E T

H S U I N E B O R F E W N A R

T M A R K O F F O F C S O K M

P L U T E R P F R O E K G R A

G M M I N S E J T L E I T S G

April 15, 2017

COMBINATORIAL SEARCHING (F5C: 15 Apr 2017  0919)

7.2.2.1

baktrak tree

distane

Hamming distane

diversity

uniform

quasi-uniform

NP-hard

unique solution

instant insanity

grope

binary operation

multipliation tables

EXERCISES | First Set

[

℄ Let

be any tree. Construt an unsolvable exat over problem for whih

is the baktrak tree traversed by Algorithm D; a

unique

olumn should have the mini-

mum size whenever step D? is enountered. Illustrate your onstrution when

[

℄ Continuing exerise 5, let

be a tree in whih ertain leaves have b een

distinguished from the others and designated as \solutions."

a) Show that some suh trees never math the behavior of Algorithm D.

b) Charaterize all suh trees that

arise, having solutions where indiated.

10.

[

℄ Mo dify Algorithm D so that it doesn't require the presene of any primary

olumns in the rows. A valid solution should not ontain any purely seondary rows;

but it must interset every suh row. (For example, if only olumns 1 and 2 of (

)

were primary, the only valid solutions would b e to hoose rows

;

15.

[

M21

℄ The solution to an exat over problem with matrix

an b e regarded as

a binary vetor

suh that

= 11

: : :

1. The

distane

between two solutions

and

an then be dened as the Hamming distane

(

x; x

) =



(



), the numb er of

plaes where

and

dier. The

diversity

is the minimum distane b etween two

of its solutions. (If

has at most one solution, its diversity is innite.)

a) Is it possible to have diversity 1?

b) Is it p ossible to have diversity 2?

) Is it possible to have diversity 3?

d) Prove that if

represents a

uniform

exat over problem, the distane b etween

solutions is always even.

e) Most of the exat over problems that arise in appliations are at least

quasi-

uniform

, in the sense that they have a nonempty subset

of primary olumns

suh that

has the same numb er of 1s in every row. (For example, every

polyomino or polyub e paking problem is quasi-uniform, b eause every row of the

matrix sp eies exatly one piee name.) Can suh problems have odd distanes?

19.

[

M16

℄ Given an exat over problem

, onstrut an exat over problem

that

has exatly one more solution than

does. [Consequently it is NP-hard to determine

whether an exat over problem with at least one solution has more than one solution.℄

Assume that

ontains no all-zero rows.

20.

[

M25

℄ Given an exat over problem

, onstrut an exat over problem

suh

that (i)

has at most three 1s in every olumn; (ii)

and

have exatly the same

numb er of solutions.

21.

[

M21

℄ Continuing exerise 20, onstrut

having

exatly

three 1s p er olumn.

24.

[

℄ Given an



exat over problem

with exatly three 1s p er olumn,

onstrut a generalized \instant insanity" problem with

(

) ubes and

olors

that is solvable if and only if

is solvable. (See 7.2.2{(

) .)

26.

[

M24

℄ A

grope

is a set

together with a binary op eration

, in whih the identity

(

) =

is satised for all

and

a) Prove that the identity (

)

also holds, in every grop e.

b) Whih of the following \multipliation tables" dene a grop e on

;

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

;

0 3 2 1

3 2 1 0

2 1 0 3

1 0 3 2

;

0 1 3 2

1 0 2 3

3 2 1 0

2 3 0 1

;

0 2 3 1

3 1 0 2

1 3 2 0

2 0 1 3

;

0 3 1 2

2 1 3 0

3 0 2 1

1 2 0 3

April 15, 2017

7.2.2.1

DANCING LINKS

idempotent

ommutative

identity element

Dominosa

solitaire

game

Pijanowski solitaire, see Dominosa

dominoes

3D MATCHING

permutations of the multiset

queen graph

olored

(In the rst example,



; in the seond,

= (



) mo d 4. The

last two have



(



) for ertain funtions

) For all

, onstrut a grope whose elements are

;

; : : : ; n



d) Consider the exat over problem that has

olumns (

x; y

) for 0



x; y < n

and

the following

+ (



)

3 rows:

(

x; x

)

, for 0



x < n

;

ii)

(

x; x

)

;

(

x; y

)

;

(

y ; x

)

, for 0



x < y < n

;

iii)

(

x; y

)

;

(

y ; z

)

;

(

z ; x

)

, for 0



x < y ; z < n

Show that its solutions are in one-to-one orrespondene with the multipliation

tables of gropes on the elements

;

; : : : ; n



e) Element

of a grope is

idempotent

. If

elements are idemp otent and



are not, prove that



(modulo 3).

27.

[

℄ Mo dify the exat over problem of exerise 26(d) in order to nd the mul-

tipliation tables of (a) all idempotent grop es | gropes suh that

for all

;

(b) all ommutative gropes | grop es suh that

for all

and

; () all

gropes with an identity element | grop es suh that

0 = 0

for all

30.

[

℄

Dominosa

is a solitaire game in whih you \shue" the 28 piees

<0>0

<0>1

: : :

<6>6

of double-six domino es and plae them at random into a 7



8 frame.

Then you write down the numb er of spots in eah ell, put the domino es away, and try

to reonstrut their positions based only on that 7



8 array of numbers. For example,

^0^0^5<2>1<4>1^²

v1v4v5<3>5<3>5v¶

<1>1<5>6<0>0^4^4

^4<4>5^¶<2>2v²v³

v0^0^5v¶<1>3<3>6

^¶v¶v²<0>3^²<5>1

v1<5>0<4>4v0<3>2

yields the array



0 0 5 2 1 4 1 2

1 4 5 3 5 3 5 6

1 1 5 6 0 0 4 4

4 4 5 6 2 2 2 3

0 0 5 6 1 3 3 6

6 6 2 0 3 2 5 1

1 5 0 4 4 0 3 2

a) Show that

another

plaement of domino es also yields the same matrix of numb ers.

b) What domino plaement yields the array



3 3 6 5 1 5 1 5

6 5 6 1 2 3 2 4

2 4 3 3 3 6 2 0

4 1 6 1 4 4 6 0

3 0 3 0 1 1 4 4

2 6 2 5 0 5 0 0

2 5 0 5 4 2 1 6

31.

[

℄ Show that Dominosa reonstrution is a speial ase of

3D MATCHING

32.

[

M22

℄ Generate random instanes of Dominosa, and estimate the probability of

obtaining a 7



8 matrix with a unique solution. Use two models of randomness: (i) Eah

matrix whose elements are p ermutations of the multiset



;



; : : : ;



is equally

likely; (ii) eah matrix obtained from a random shue of the dominoes is equally likely.

39.

[

℄ By setting up an exat over problem and solving it with Algorithm D, show

that the queen graph

(exerise 7.1.4{241) annot b e olored with eight olors.

40.

[

℄ In how many ways an

be olored in a \balaned" fashion, using eight

queens of olor 0 and seven eah of olors 1 to 8?

剩余57页未读，继续阅读

ShenPlanck

粉丝: 951
资源: 343

"深入探讨计算机程序设计艺术：第4卷第5册C Dancing Links1"

dlx.js:JavaScript中实现的Knuth Dancing Links与算法X

Dancing Links：搜索优化与Sudoku解法

Dancing Links算法中文解析

计算机程序设计艺术

suduku_mfc-ver.5.zip_Links_MFC数独_dancing links数独

dancing links 模板

dancing links 骑士遍历

Dancing Links 中文版

Dancing links 学习资料

Dancing Links中文版

最新资源