《計算機程序設計藝術》堪稱計算機科學領域的瑰寶。從事研究的人驚艷于其精美優(yōu)雅的分析，而普通程序員則一直在卓有成效地利用書中提供的各種方案解決日常問題。這些書展現(xiàn)了作者的博觀、清晰、精確和幽默，所有的人都欽佩不已。高德納是算法和程序設計領域的先驅者，對計算機科學發(fā)展史也有著深入的研究，書中在介紹眾多理論的同時，也給出了相關的歷史和發(fā)展歷程，成為本書的一大特色。 《計算機程序設計藝術》系列被公認為計算機科學領域的權威之作，深入闡述了程序設計理論，對計算機領域的發(fā)展有著極為深遠的影響。本書是該系列的第4卷B，書中第4卷A的基礎上，進一步介紹了組合算法相關的核心知識，內容涉及布爾函數(shù)、按位操作技巧、元組和排列、組合和分區(qū)以及所有的樹等。

《計算機程序設計藝術》堪稱計算機科學領域的瑰寶。從事研究的人驚艷于其精美優(yōu)雅的分析，而普通程序員則一直在卓有成效地利用書中提供的各種方案解決日常問題。這些書展現(xiàn)了作者的博觀、清晰、精確和幽默，所有的人都欽佩不已。高德納是算法和程序設計領域的先驅者，對計算機科學發(fā)展史也有著深入的研究，書中在介紹眾多理論的同時，也給出了相關的歷史和發(fā)展歷程，成為本書的一大特色。



《計算機程序設計藝術》系列被公認為計算機科學領域的專業(yè)之作，深入闡述了程序設計理論，對計算機領域的發(fā)展有著極為深遠的影響。本書是該系列的第4卷B，書中第4卷A的基礎上，進一步介紹了組合算法相關的核心知識，內容涉及布爾函數(shù)、按位操作技巧、元組和排列、組合和分區(qū)以及所有的樹等。

高德納（Donald E. Knuth） 1974年圖靈獎得主，斯坦福大學計算機系榮休教授，美國國家科學院院士，美國工程院院士。 計算機科學家，算法與程序設計技術的先驅者、計算機排版系統(tǒng)TEX和METAFONT字體系統(tǒng)的發(fā)明人，因諸多成就以及大量富于創(chuàng)造力和具有深遠影響的著作（19部書，160篇論文）而譽滿全球。 近些年，他將精力全部投入到計算機程序設計藝術七卷集的史詩般創(chuàng)作中。 Knuth教授獲得過許多獎項和榮譽，包括美國國家科學獎章、計算機先鋒獎、美國數(shù)學學會的斯蒂爾獎、IEEE馮·諾依曼獎，以及因發(fā)明先進技術于1996年榮獲的京都獎。1996年，Donald E. Knuth獎設立，授予那些為計算機科學基礎做出杰出貢獻的人。

重溫預備數(shù)學知識 1

不等式 3

鞅 5

從鞅得到的尾部不等式 6

應用 8

幾乎必然和確乎必然的陳述 9

習題 10

第7 章組合查找 [4A.1]

7.2 生成所有可能的組合對象 [4A.234]

7.2.1 生成基本組合模式 [4A.234]

7.2.2 回溯編程 26

數(shù)據(jù)結構 27

沃克方法 28

排列與蘭福德對 29

單詞矩形 31

無逗點碼 32

選擇的動態(tài)排序 33

重溫順序分配 33

無逗點碼問題的列表 35

行動和撤銷的一般機制 36

無逗點碼的回溯 38

運行時間估計 39

*估計解的個數(shù) 42

分解問題 43

歷史注記 45

習題 46

7.2.2.1 舞蹈鏈 55

精確覆蓋問題 56

副項 60

進度報告 61

數(shù)獨 62

多聯(lián)骨牌 67

多聯(lián)立方 69

分解精確覆蓋問題 70

受限顏色覆蓋. 73

引入重數(shù) 78

*新的舞步 81

*分析算法X 83

*分析匹配問題 86

*保持適當?shù)膶Ｗ?88

利用局部等價性 90

*預處理選項 91

最小成本解 93

*實現(xiàn)最小成本截斷 97

*使用ZDD 的舞蹈鏈 99

總結 102

歷史注記 102

習題（第 1 組） 103

習題（第 2 組） 130

習題（第3 組） 145

7.2.2.2 可滿足性 154

一個簡單的例子 156

精確覆蓋 157

圖著色 158

因式分解整數(shù) 160

故障測試 161

學習布爾函數(shù) 165

有界模型檢測 167

互斥中的應用 169

數(shù)字體層成像 173

SAT 實例總結 175

回溯求解可滿足性問題 175

惰性數(shù)據(jù)結構 177

從單元子句強制移動 179

算法的比較 181

*通過更加努力地工作來獲得提速 182

*通過前瞻來獲得提速 185

*更進一步的前瞻 190

隨機可滿足性問題 191

分析隨機2SAT 問題 195

歸結法 197

*一般歸結法的下界 199

使用歸結的SAT 求解 202

由沖突驅動的子句學習 203

不可滿足性證書 209

*清除無用的子句 211

*刷新文字并重新開始 214

蒙特卡羅算法 215

局部引理 218

跡與板塊 220

跡上的算術 221

*跡與局部引理 223

*消息傳遞 226

*預處理子句 230

將約束編碼為子句 231

單元傳播與強制 236

對稱性破缺 238

保可滿足性的映射 240

100個測試樣例 244

調整參數(shù) 253

利用并行化 257

簡史 257

習題 260

習題答案 303

附錄A 數(shù)值表 544

附錄B 記號索引 548

附錄C 算法、定理、引理、推論和程序索引 553

附錄D 組合問題索引 554

附錄E 習題解答中謎題的答案 557

人名索引 560

索引 570