目錄 第1 章算法設(shè)計與分析基礎(chǔ)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1 1. 1 算法概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． l 1. 1. 1 什么是算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1 1. 1. 2 學習算法的重要性．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7 1.2 問題的求解過程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8 1. 2. 1 問題及問題的求解過程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8 1. 2. 2 算法設(shè)計與算法表示．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9 1. 2. 3 算法確認和算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 10 1. 3 數(shù)學基礎(chǔ)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 13 1. 3. 1 函數(shù)的漸近的界．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 14 1. 3. 2 利用極限求函數(shù)的漸近的界．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．．．．． ．．．．．．．．．17 1. 3. 3 常用的求和級數(shù)及推導方法…………………………………………… 19 1. 3. 4 基本漸近效率類型．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 21 1. 4 算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2 2 1. 4. 1 算法的時間復雜度分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 22 1. 4. 2 算法的空間復雜度分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 28 1. 4. 3 非遞歸算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 29 1. 4. 4 遞歸算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 30 1.5 關(guān)千P類、NP類和NPC類問題……………………………………… ……… 33 1. 6 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 34 1. 7 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 35 1.8 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 36 第2章算法工具STL ················································································· 38 2. 1 STL概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 38 2. 1. 1 什么是STL容器.................................................................. 39 2. 1. 2 什么是STL算法.................................................................. 39 2. 1. 3 什么是STL迭代器............................................................... 40 2. 2 常用的STL容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 41 2. 2. 1 順序容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 41 2.2. 2 關(guān)聯(lián)容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 49 2. 2. 3 適配器容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 52 2. 3 STL在算法設(shè)計中的應用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 55 2.4 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 67 2. 5 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 68 2. 6 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 69 第3章蠻力法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72 3. 1 蠻力法概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72 3. 1. 1 蠻力法的基本思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72 3. 1. 2 蠻力法解題格式．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 75 3. 2 蠻力法的應用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 83 3. 2. 1 百錢百雞問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 84 3. 2. 2 獄吏問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 85 3. 2. 3 順序查找．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 88 3.2.4 簡單排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 89 3. 2. 5 求解幕集問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 95 3. 2. 6 求解0/1 背包問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 98 3. 2. 7 求解最大連續(xù)子序列和問題………………………………………… 102 3. 3 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 104 3. 4 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105 3. 5 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105 第4章遞歸與分治法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 108 ，． 急尸··`· ＇ ， ! 2 ; 魚 ． ...., }， 4. 1 遞歸算法的思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 108 4. 1. 1 遞歸算法的特性．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 109 4. 1. 2 遞歸算法的執(zhí)行過程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 110 4. 1. 3 遞歸適用場合．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 112 4. 2 遞歸設(shè)計實例．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 117 4. 2. 1 幾個簡單的遞歸程序．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 117 4.2.2 排序問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 119 4.2.3 斐波那契數(shù)列問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 121 4. 2. 4 n皇后問題........................................................................ 123 4. 2. 5 漢諾塔問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 125 4. 3 分治法的思想化整為零．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 127 4. 4 分治法的應用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 129 4. 4. 1 二分查找算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 129 4. 4. 2 歸并排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 131 4. 4. 3 快速排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 134 4. 4. 4 堆排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 136 4. 4. 5 棋盤覆蓋問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 139 4. 4. 6 最大子段和問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 142 4. 5 本章小結(jié)．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 144 4. 6 習題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 145 4. 7 實驗題．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 145 第5 章貪心法．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 148 5. 1 貪心法概述．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 148 5. 1. 1 問題的提出．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 148 5. 1. 2 貪心法設(shè)計思想．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 150 5. 1. 3 貪心法的基本要素．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 150 5. 1. 4 貪心法的求解過程．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 151 5. 2 貪心法的應用．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．． 152 5. 2. 1 活動安排問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 152 5. 2. 2 幣種統(tǒng)計問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 159 5. 2. 3 背包問題．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．． 160 5. 2. 4 多機調(diào)度問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 163 5. 2. 5 哈夫曼編碼．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 165 5. 2. 6 最小生成樹．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 172 5. 2. 7 求解流水作業(yè)調(diào)度問題．．． ．．．．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． 178 5. 2. 8 求解川忌賽馬問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 182 5. 3 本章小結(jié)．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 185 5. 4 習題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 186 5. 5 實驗題．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 187 第6 章動態(tài)規(guī)劃法．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 190 6. 1 動態(tài)規(guī)劃法概述．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 190 6. 1. 1 動態(tài)規(guī)劃法的基本思想．．． ．．．．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． 190 6. 1. 2 動態(tài)規(guī)劃的設(shè)計技術(shù)．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 192 6. 2 最優(yōu)決策表．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 195 6.2. 1 0/1 背包問題．．．．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 196 6.2. 2 0/1 背包的相關(guān)問題．．．．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 200 6. 3 動態(tài)規(guī)劃法的應用．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．． 202 6. 3. 1 斐波那契數(shù)列．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 202 6. 3. 2 排隊買票問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 203 6. 3. 3 湊硬幣問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 204 6. 3. 4 數(shù)字塔問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 207 6. 3. 5 最長公共子序列問題．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 211 6. 3. 6 流水作業(yè)調(diào)度問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 214 6. 3. 7 資源分配問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 217 6. 3. 8 最短路徑問題．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 220 6. 4 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 225 6. 5 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 225 6. 6 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 227 第7 章回溯法與分支限界法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 233 7. 1 回溯法的設(shè)計技術(shù)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 233 7. 1. 1 回溯法的算法思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 234 7. 1. 2 回溯法的算法框架．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 236 7. 1. 3 回溯法的適用條件．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 239 7. 2 回溯法的應用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 243 7. 2. 1 0/1 背包問題..................................................................... 243 7. 2. 2 n皇后問題........................................................................ 248 7.2.3 旅行商問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 250 7.2.4 圖的m著色問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 253 7. 2. 5 求解子集和問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 255 7. 3 分支限界法的設(shè)計技術(shù)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 258 7. 3. 1 分支限界法的思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 258 7. 3. 2 分支限界法與回溯法對比．．．．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．．．．． ．．．．．．．．． 258 7. 3. 3 分支限界法解決的關(guān)鍵問題………………………………………… 259 7. 3.4 分支限界法的時間性能．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262 7. 4 分支限界法的應用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262 7. 4. 1 0/1 背包問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262 7. 4. 2 旅行商問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 269 7. 5 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 282 7. 6 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 283 7. 7 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 284 第8 章圖的搜索算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288 ，． 急尸··`· ＇ ， ! 4 ; 魚 ． ...., }， 8. 1 廣度優(yōu)先搜索．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288 8. 1. 1 算法描述與分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288 8. 1. 2 程序?qū)崿F(xiàn)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 292 8. 2 深度優(yōu)先搜索．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 297 8. 2. 1 算法描述與分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 297 8.2.2 程序?qū)崿F(xiàn)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 299 8. 3 有向圖的強連通分支．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 303 8. 4 無向圖的雙連通分支．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 307 8. 5 網(wǎng)絡(luò)流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 310 8. 5. 1 相關(guān)概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 310 8. 5. 2 求最大流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 312 8. 5. 3 割集與割量．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 316 8. 5. 4 求最小費用最大流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 317 8. 6 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 32 2 8. 7 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 32 2 8. 8 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 323 第9 章計算幾何算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 327 9. 1 線段的性質(zhì)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 327 9. 2 向量運算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 328 9. 2. 1 向扯加減運算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 329 9. 2. 2 向批點積運算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 330 9. 3 叉積．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 331 9. 3. 1 叉積的計算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 331 9. 3. 2 判斷相繼兩直線段左轉(zhuǎn)或右轉(zhuǎn)……………………………………… 332 9. 3. 3 兩個點的距離．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 333 9. 3. 4 點到線段的距離．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 333 9. 4 線段的應用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 334 9.4. 1 判斷一個點是否在一個矩形內(nèi)……………………………………… 334 9.4. 2 判斷一個點是否在一條線段上……………………………………… 335 9.4. 3 判斷兩條線段是否平行．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 335 9.4. 4 判斷兩條線段是否相交．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 336 9.4. 5 判斷一個點是否在多邊形內(nèi)………………………………………… 336 9.4. 6 求3 個點構(gòu)成的三角形面積………………………………………… 338 9.4. 7 求一個多邊形的面積．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 338 9. 5 求解凸包問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 340 9. 5. 1 卷包裹算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 341 9. 5. 2 葛立恒掃描法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 342 9. 6 求解最近點對問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 344 9. 7 求解最遠點對問題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 349 9. 8 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 352 9. 9 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 353 9. 10 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 353 第10 章隨機算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356 10.] 同余的概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356 10. 2 隨機數(shù)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 358 10. 3 隨機算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360 10. 3. 1 隨機算法的概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360 10. 3. 2 隨機算法的分類．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360 10.4 經(jīng)典隨機算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 361 10. 4. 1 蒙特卡羅算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 361 10. 4. 2 舍伍德算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 362 10. 4. 3 拉斯維加斯算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 364 10. 5 本章小結(jié)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366 10. 6 習題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366 10. 7 實驗題．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 367 參考文獻．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 368 ，． 急尸··`· { 氣.6)