算法設計與分析（簡體書）

本書是普通高等教育“十一五”國家級規劃教材。本書以算法設計策略為知識單元，系統地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術專業的學生提供廣泛而堅實的計算機基礎知識。主要內容包括算法分析技術，算法設計技術，P類、NP類及NPC類，證明問題屬于NPC類的技術，NPC問題子問題的復雜性，擬多項式變換和圖靈歸約，NP-難解問題近似算法，近似算法設計技術，等等。本書包括了算法與復雜性領域的主要內容，可以作為高等學校計算機專業高年級本科生和研究生學習計算機算法設計的教材，也可供廣大工程技術人員和自學者學習參考。

計算機是一種現代化的信息處理工具，它對信息進行處理並提供所需結果，其結果取決於所接受的信息及相應的處理算法。算法是以計算機能夠理解的語言描述的解題過程。當算法作用於所求解問題的給定輸入集或作用於問題自身的描述上，將產生唯一確定的有限動作序列。此序列或終止於給定問題的解，或終止於對此輸入信息無解。對於給定的問題，基於對其的深刻理解，可設計出解答該問題的一個算法。在這個意義上，設計算法是將有關問題的知識，轉化為解決問題的智慧。知識誠可貴，智慧價更高。設計算法就是揭示所研究問題的基本特徵，以尋求其解答策略的過程，這是一項艱苦的創造性工作。
對於給定的問題，有可能設計出多個算法，但不同的算法質量會不一樣。衡量算法質量的主要因素是算法執行所耗費的時間和所需存儲空間，以及算法適用範圍等。對算法質量的分析研究稱為算法分析。算法設計和算法分析是計算機科學的核心基礎。國內外大學的計算機專業中，都將“算法設計與分析”作為專業基礎課。
近半個世紀以來，算法研究始終是計算機科學的一個研究熱點。以EWDijkstra、SACook、RMKarp、JHHopcroft及RETarjan等為代表的一批計算機科學家，以創造性工作推動著算法研究不斷深入發展。在研究過程中，算法理論研究與軟件技術研究之間產生了鴻溝，使得算法研究缺乏足夠的實驗支持，而實驗工作又沒有充分的理論分析。這種現狀引起了人們的憂慮。在1996年的ACM計算理論學術年會（STOC'96）上，一些計算機科學家提出“算法工程”的概念，強調研究算法實現技術的重要性，呼籲算法研究者應重視理論與實踐的結合，將算法設計、分析、實現、測試及改進等過程一體化、工程化。這種研究思路越來越受到人們的關注，促使算法研究健康發展。
本書原稿寫於20世紀80年代中期、筆者在山東大學為計算機專業研究生講授“算法設計與分析”課程期間，先後幾經修改，於1992年定稿並由山東大學出版社正式出版。此後一直使用本書作為計算機科學與技術專業的學位課教材，由筆者和朱大銘教授共同為研究生講授，效果尚好。經過20多年的研究沉澱，算法設計與分析雖然沒有太多變遷，但其研究內容更加豐富和成熟。這期間我們始終堅持在這個研究方向上從事教學和科研工作，連續主持了10多項國家自然科學基金課題，培養了一批博士、碩士研究生。為適應培養創新型人才的需要，經過反复醞釀，決定由朱大銘教授執筆，重新修改編著這本書，增加近10年來的研究成果，使之能反映21世紀以來算法設計與分析的研究現狀。可以說，本書是山東大學計算機科學與技術學院兩代人堅持不懈、刻苦努力完成的。在本書寫作過程中，得到朱洪教授的指導和幫助，在此表示感謝。
本書主要面向計算機相關專業的高年級本科生和研究生。全書共分8章，其中：第1、2章討論算法分析技術和算法設計技術；第3、4、5、6章論述NP-完全性理論，特別強調多項式變換和多項式圖靈歸約的方法及應用；第7章論述NP-難解問題近似算法的基本概念和設計NP-難解問題近似算法的基本方法；第8章討論近似算法設計的基本理論與技術。
算法研究是一項富有挑戰性的工作，對提高計算機學科的研究水平極為重要，希望能有更多的有識之士投身這項工作。由於我們學術水平有限，本書內容必有疏漏、欠妥、謬誤之處，敬請讀者指正。

第1章 算法分析技術
§1.1 算法及其復雜性
§1.2 漸近估計技術及基本規則
§1.3 遞歸算法分析
1.3.1 合并排序算法分析
1.3.2 一類遞推方程的一般解
§1.4 大整數相乘的遞歸算法
§1.5 練習
第2章 算法設計技術
§2.1 分而治之
§2.2 貪心技術
§2.3 動態規劃
§2.4 回溯技術
2.4.1 對策樹搜索與a／B-刪除
2.4.2 一般樹的回溯搜索與分支定界
§2.5 局部搜索技術
§2.6 練習
第3章 P類、NP類及NPC類
§3.1 問題與算法
§3.2 確定型圖靈機與P類
§3.3 非確定型計算與NP類
§3.4 多項式變換與NPC類
§3.5 庫克定理
§3.6 練習
第4章 證明問題屬于NPC類的技術
§4.1 基本的NPC問題
§4.2 證明NP-完全性的典型技術
4.2.1 限制技術
4.2.2 局部替換技術
4.2.3 分支設計技術
§4.3 練習
第5章 NPC問題子問題的復雜性
§5.1 2SAT問題屬于P類
§5.2 幾個NPC問題在三角化圖上的解
5.2.1 三角化圖的特征
5.2.2 用字典編輯廣度優先搜索識別三角化圖
5.2.3 三角化圖上著色、團、獨立集及團覆蓋問題的算法
§5.3 子問題中P和NPC的分界
§5.4 練習
第6章 擬多項式變換和圖靈歸約
§6.1 判定問題、語言和編碼方案
§6.2 擬多項式時間算法和強NPC類
§6.3 用擬多項式變換證明強NP-完全性
§6.4 復雜性類之間的關系
§6.5 圖靈歸約和NP-難解問題
§6.6 練習
第7章 NP-難解問題近似算法
§7.1 近似算法及其性能評估
§7.2 近似算法設計
7.2.1 滿足三角不等式的貨郎問題及其近似算法
7.2.2 滿足三角不等式的貨郎問題的最小生成樹算法
7.2.3 多任務排工問題的近似算法
7.2.4 獨立任務排工問題
§7.3 NP-難解問題可近似計算復雜性
§7.4 多項式時間近似方案
§7.5 練習
第8章 近似算法設計技術
§8.1 組合技術
8.1.1 MaxSAT問題
8.1.2 Maxk-SAT問題
8.1.3 圖頂點覆蓋問題
8.1.4 整數排列與換位移動排序
8.1.5 集合覆蓋問題
§8.2 線性規劃技術
8.2.1 頂點覆蓋近似算法
8.2.2 集合覆蓋近似算法
§8.3 原始對偶技術
8.3.1 集合覆蓋
8.3.2 擊中集問題
8.3.3 最短路問題
8.3.4 Steiner樹問題
§8.4 局部搜索技術
8.4.1 Max-3SAT問題的局部搜索算法
8.4.2 K-median問題的局部搜索算法
8.4.3 設施定位問題的局部搜索近似算法
§8.5 隨機近似算法
8.5.1 MaxSAT問題的隨機算法
8.5.2 歐氏平面上貨郎問題的隨機算法
§8.6 練習
參考文獻