Donald Knuth的《计算机程序设计艺术》第4卷第5册B：回溯编程简介

需积分: 0 126 浏览量更新于2024-07-01 1 收藏 887KB PDF 举报

"计算机程序设计艺术.第4卷.第5册B（英文） Backtrack Programming1" 《计算机程序设计艺术》是计算机科学领域的经典之作，由Donald E. Knuth教授撰写。这本书的第四卷，预 fascicle 5B，专注于介绍回溯编程技术。回溯是一种用于解决约束满足问题的算法策略，它通过尝试逐步构建解决方案并撤销在无法找到有效解时做出的选择来工作。这种方法常用于优化问题、组合问题和搜索问题，如八皇后问题、图着色问题和旅行商问题。在这部分内容中，Knuth教授可能探讨了回溯编程的基本概念，包括： 1. **回溯编程的核心思想**：回溯是一种试探性解决问题的方法，它尝试沿着多种可能的路径探索解空间。当发现当前路径无法到达目标时，算法会“回溯”到一个决策点，选择另一条路径继续尝试。 2. **回溯与深度优先搜索**：回溯通常结合深度优先搜索（DFS）策略来实现，因为它能有效地在决策树中探索。DFS会尽可能深地沿着一条路径走下去，直到遇到障碍或达到目标，然后回溯到上一个决策点。 3. **剪枝技术**：为了提高效率，回溯算法通常使用剪枝技术来避免无效的分支。剪枝可以通过预测试条件或在过程中设置约束来实现，以减少不必要的计算。 4. **回溯算法的步骤**：通常包括四个主要步骤：(i) 定义问题的解空间，(ii) 选择一个未尝试的解元素，(iii) 应用该元素并检查是否可行，以及(iv) 如果可行，则继续深入，否则回溯并尝试下一个元素。 5. **应用实例**：书中可能包含多个示例，如八皇后问题，展示如何使用回溯方法来放置皇后，确保没有两皇后在同一行、列或对角线上。其他可能的例子包括图着色问题，寻找最少颜色数来为图中的所有节点着色，以及旅行商问题，寻找访问所有城市并返回起点的最短路径。 6. **MMIX计算机模拟软件**：Knuth教授提到了MMIX计算机及其模拟软件，这可能与书中某些示例的实现有关。MMIX是Knuth设计的一种简化版的RISC架构，用于教学目的，它的软件可以用来理解计算机内部如何处理回溯算法。 7. **Stanford GraphBase**：这是一个图形数据库，可能在第七章的示例中用于存储和处理与回溯算法相关的图数据。读者可以通过提供的链接下载软件来处理这些图形数据。 8. **版权信息**：最后，这段内容包含了出版物的版权信息，强调未经许可不得复制、存储或传输此书的任何部分，这是出版界的标准做法，保护作者的知识产权。《计算机程序设计艺术》是程序员和计算机科学家的重要参考文献，对于深入理解和应用回溯编程有着深远的影响。通过学习这一部分，读者可以掌握回溯算法的设计和优化技巧，从而解决复杂问题。

November 12, 2016

7.2.2

BACKTRACK PROGRAMMING

registers

Walker

uto prop erties

visits

bitwise op erations

historial notes+

Sprague

although there is some exibility; we ould, for example, have restored

before



and





, beause those arrays are indep endent.

The auxiliary arrays



make it easy to test prop erty

at the beginning

of step B3*, but we must also aess memory when we update them and downdate

them. Do es that ost us more than it saves? Fortunately, no: The running time

for

= 16 go es down to ab out 34 billion mems, roughly 30 mems per no de.

Furthermore we ould keep the bit vetors



entirely in registers, on a

mahine with 64-bit registers, assuming that



32. Then there would b e just

two memory aesses p er no de, namely to store

and later to feth

;

however, quite a lot of in-register omputation would b eome neessary.

Walker's method.

The 1950s-era programs of R. J. Walker organized bak-

traking in a somewhat dierent way. Instead of letting

run through all

elements of

, he alulated and stored the set





(

; : : : ; x



; x

) holds

(

)

upon entry to eah node at level

. This omputation an often b e done eÆiently

all at one, instead of pieemeal, b eause some uto prop erties make it p ossible

to ombine steps that would otherwise have to b e rep eated for eah

. In

essene, he used the following variant of Algorithm B:

Algorithm W

(

Walker's baktrak

). Given domains

and utos

as ab ove,

this algorithm visits all sequenes

: : : x

that satisfy

(

; x

; : : : ; x

W1.

[Initialize.℄ Set

1, and initialize the data strutures needed later.

W2.

[Enter level

.℄ (Now



(

; : : : ; x



) holds.) If

l > n

, visit

: : : x

and go to W4. Otherwise determine the set

as in (

W3.

[Try to advane.℄ If

is nonempty, set

min

, up date the data

strutures to failitate omputing

, set

+ 1, and go to W2.

W4.

[Baktrak.℄ Set



1. If

l >

0, downdate the data strutures by

undoing hanges made in step W3, set

, and retreat to W3.

Walker applied this method to the

queens problem by omputing

, where

; : : : ; n

and



j < l

; B





j < l

; C





j < l

(

)

He represented these auxiliary sets by bit vetors



, analogous to (but

dierent from) the bit vetors of Algorithm B* above. Exerise 9 shows that

the up dating in step W3 is easy, using bitwise op erations on

-bit numb ers;

furthermore, no downdating is needed in step W4. The orresponding run time

when

= 16 turns out to be just 9.1 gigamems, or 8 mems per node.

Let

(

) b e the number of solutions to the

queens problem. Then we have

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

(

) = 1 1 0 0 2 10 4 40 92 352 724 2680 14200 73712 365596 2279184 14772512

and the values for



11 were omputed independently by several p eople during

the nineteenth entury. Small ases were relatively easy; but when T. B. Sprague

November 12, 2016

COMBINATORIAL SEARCHING (F5B: 12 Nov 2016  1636)

7.2.2

Sprague

Onnen

Ahrens

Walker

SWAC

omputer

UCLA

Kennedy

University of Tennessee

IBM 1620

Bunh

University of Illinois

IBM System 360-75

Bitner

Preuer

Engelhardt

distributed omputation

FPGA

permutation

data strutures

Langford pairs

dual

linked list

had nished omputing

(11) he remarked that \This was a very heavy piee of

work, and oupied most of my leisure time for several months.

: : :

It will, I imag-

ine, b e sarely possible to obtain results for larger b oards, unless a numb er of

persons o-operate in the work." [See

Pro. Edinburgh Math. So .

(1899), 43{

68; Sprague was the leading atuary of his day.℄ Nevertheless, H. Onnen went on

to evaluate

(12) = 14

;

200 | an astonishing feat of hand alulation | in 1910.

[See W. Ahrens,

Math. Unterhaltungen und Spiele

, seond edition (1918), 344.℄

All of these hard-won results were onrmed in 1960 by R. J. Walker,

using the

SWAC

omputer at UCLA and the metho d of exerise 9. Walker also

omputed

(13); but he ouldn't go any further with the mahine available to

him at the time. The next step,

(14), was omputed by Mihael D. Kennedy at

the University of Tennessee in 1963, ommandeering an IBM 1620 for 120 hours.

S. R. Bunh evaluated

(15) in 1974 at the University of Illinois, using about

two hours on an IBM System 360-75; then J. R. Bitner found

(16) after ab out

three hours on the same omputer, but with an improved metho d.

Computers and algorithms have ontinued to get better, of ourse, and suh

results are now obtained almost instantly. Hene larger and larger values of

lie

at the frontier. The whopping value

(27) = 234,907,967,154,122,528, found in

2016 by Thomas B. Preuer and Matthias R. Engelhardt, probably won't be ex-

eeded for awhile! [See

J. Signal Proessing Systems

(2017), to appear. This

distributed omputation oupied a dynami luster of diverse

FPGA

devies for

383 days; those devies provided a total peak of more than 7000 ustom-designed

hardware solvers to handle 2,024,110,796 indep endent subproblems.℄

Permutations and Langford pairs.

Every solution

: : : x

to the

queens

problem is a p ermutation of

; : : : ; n

, and many other problems are permu-

tation-based. Indeed, we've already seen Algorithm 7.2.1.2X, whih is an ele-

gant baktrak pro edure sp eially designed for speial kinds of p ermutations.

When that algorithm b egins to hoose the value of

, it makes all of the appropri-

ate elements

;

; : : : ; n

g n f

; : : : ; x



onveniently aessible in a linked list.

We an get further insight into suh data strutures by returning to the

problem of Langford pairs, whih was disussed at the very b eginning of Chap-

ter 7. That problem an be reformulated as the task of nding all p ermutations

;

; : : : ; n

g [ f

;



; : : : ;



with the prop erty that

implies



k ;

for 1



and 1



. (

)

For example, when

= 4 there are two solutions, namely 234



4 and 413



(As usual we nd it onvenient to write



1 for





2 for



2, et.) Notie that if

: : : x

is a solution, so is its \dual"



= (



)

: : :

(



)(



Here's a Langford-inspired adaptation of Algorithm 7.2.1.2X, with the for-

mer notation mo died slightly to math Algorithms B and W: We want to main-

tain p ointers

: : : p

suh that, if the positive integers not already present in

: : : x



are

< k

  

< k

when we're hoosing

, we have the linked list

; p

; : : : ; p



; p

= 0

(

)

Suh a ondition turns out to b e easy to maintain.

November 12, 2016

7.2.2

BACKTRACK PROGRAMMING

undoes

deletion operation

daning links

searh tree

uto priniple

Algorithm L

(

Langford pairs

). This algorithm visits all solutions

: : : x

to (

) in lexiographi order, using p ointers

: : : p

that satisfy (

), and also

using an auxiliary array

: : : y

for baktraking.

L1.

[Initialize.℄ Set

: : : x

: : :

+ 1 for 0



k < n

L2.

[Enter level

.℄ Set

. If

= 0, visit

: : : x

and go to L5.

Otherwise set

0, and while

0 set

+ 1.

L3.

[Try

.℄ (At this p oint we have

.) If

+ 1

, go to L5.

Otherwise, if

= 0, set



+ 1, and return to L2.

L4.

[Try again.℄ (We've found all solutions that begin with

: : : x



something smaller.) Set

and

, then go to L3 if

= 0.

L5.

[Baktrak.℄ Set



1. If

l >

0 do the following: While

0, set



1. Then set

, and go

bak to L4. Otherwise terminate the algorithm.

Careful study of these steps will reveal how everything ts together niely. Notie

that, for example, step L3 removes

from the linked list (

) by simply setting

. That step also sets



, in aordane with (

), so that we

an skip over p osition

+ 1 when we enounter it later in step L2.

The main point of Algorithm L is the somewhat subtle way in whih step L5

undoes the deletion op eration by setting

. The p ointer

still retains the

appropriate link to the next element in the list,

beause

has not been hanged

by any of the intervening updates

. (Think ab out it.) This is the germ of an idea

alled \daning links" that we will explore in Setion 7.2.2.1.

To draw the searh tree orresp onding to a run of Algorithm L, we an label

the edges with the positive hoies of

as we did in (

), while lab eling the

nodes with any previously set negative values that are passed over in step L2.

For instane the tree for

= 4 is

1 1

213 2

314

21 132 13 1

432

2 3

3 2 3

3 4

1 4

2 4

1 2

(

)

Solutions app ear at depth

in this tree, even though they involve 2

values

: : : x

Algorithm L sometimes makes false starts and do esn't realize the problem

until probing further than neessary. Notie that the value

an app ear

only when

+ 1



; hene if we haven't seen

by the time

reahes



1, we're

fored

to hoose

. For example, the branh 12



1 in (

)

needn't be pursued, b eause 4 must app ear in

; x

. Exerise 20 explains

how to inorp orate this uto priniple into Algorithm L. When

= 17, it

redues the number of no des in the searh tree from 1.29 trillion to 330 billion,

剩余57页未读，继续阅读

ask_ai_app

粉丝: 24

Donald Knuth的《计算机程序设计艺术》第4卷第5册B：回溯编程简介

计算机程序设计艺术第四卷第5册英文原版

The art of Computer Programming I II III IV 计算机程序设计艺术四卷全part5

计算机程序设计艺术 第 4 卷 B（中英文版）

数字符号串的算法世界：深度分析无重复数字序列的编程艺术

递归函数设计：Java编码规范与最佳实践

面向对象设计深度应用：深搜城堡问题中的算法模块构建（系统教程）

回溯算法的奥秘：探索计算机科学中的回溯世界（专业解码算法原理）

谭浩强C语言教程：算法基础与性能优化，让你的程序跑得更快

提升编码效率：唯一可译码尾随后缀判定的5大优化策略

【递归算法深度解读】：PTA第八章递归思想在算法中的高效应用

最新资源

计算机程序设计艺术第 4 卷 B（中英文版）