ChatGPT掀起了現(xiàn)象級(jí)的風(fēng)暴，趕超ChatGPT潮流，算法突破是關(guān)鍵。
本書介紹了若干常見算法，涉及排序、哈希、動(dòng)態(tài)規(guī)劃與近似算法、高斯消去法、圖論與線性規(guī)劃、無約束優(yōu)化、迭代法、插值與擬合等。本書在介紹算法的同時(shí)，結(jié)合了作者自己對(duì)數(shù)學(xué)背景、應(yīng)用場景的理解，便于讀者把握算法的核心思想。而且，本書不僅指出了哪些算法可以解決問題，還指出了哪些算法可以更好地解決問題，便于讀者深入理解算法。本書盡可能地避開了以應(yīng)試為導(dǎo)向的灌輸式講解，力求引起讀者的興趣并擴(kuò)大其視野，例如在介紹哈希時(shí)，講解了如何將哈希的算法思想運(yùn)用于相似性搜索、負(fù)載均衡等多個(gè)實(shí)際問題中；又如在介紹高斯消去法時(shí)，講解了相關(guān)的數(shù)學(xué)理論及編程實(shí)現(xiàn)上的具體技巧，并將其運(yùn)用于對(duì)大規(guī)模稀疏線性方程組的求解，等等。
本書面向有一定高等數(shù)學(xué)、編程語言基礎(chǔ)及對(duì)算法有初步了解的讀者，包括高等院校的學(xué)生、程序員、算法分析人員及設(shè)計(jì)人員等，旨在幫助讀者進(jìn)一步學(xué)習(xí)算法，理解與算法相關(guān)的理論基礎(chǔ)和應(yīng)用實(shí)例。
ChatGPT掀起了現(xiàn)象級(jí)的風(fēng)暴，趕超ChatGPT潮流，算法突破是關(guān)鍵。
許多經(jīng)典的算法教科書都詳盡地介紹了算法的各個(gè)知識(shí)點(diǎn)，但在覆蓋面廣的同時(shí)難免會(huì)忽略許多細(xì)節(jié)問題。例如，哪些算法真正值得運(yùn)用到實(shí)際問題中，算法有哪些變種值得我們了解，算法背后有哪些數(shù)學(xué)理論支撐，等等。
本書討論了計(jì)算機(jī)算法相關(guān)的若干話題，在介紹算法的同時(shí)結(jié)合了作者自己對(duì)數(shù)學(xué)背景、應(yīng)用場景的理解，便于讀者把握算法的核心思想。而且，本書不僅指出了哪些算法可以解決問題，還指出了哪些算法可以更好地解決問題，這有助于我們對(duì)算法的深入理解。
本書總計(jì) 8 章，除了講解基本知識(shí)，還回答了許多相關(guān)的有趣問題。
- 排序：排序算法有很多種，在比較流行的編程語言中都有提供排序算法的庫函數(shù)，直接調(diào)用這些庫函數(shù)會(huì)非常簡單。但它們所使用的算法為何有效，這些算法與一些經(jīng)典的排序算法又有什么區(qū)別？
- 哈希：在講解哈希算法時(shí)一般主要介紹哈希函數(shù)的作用及哈希表的不同實(shí)現(xiàn)方法。但將哈希函數(shù)運(yùn)用于不同的問題時(shí)，最為巧妙的地方在于哈希函數(shù)的設(shè)計(jì)。對(duì)于不同領(lǐng)域的問題，哈希函數(shù)都有哪些有趣的形式？
- 動(dòng)態(tài)規(guī)劃與近似算法：通常這兩類算法并不會(huì)放在一起去探討。在面對(duì)不同復(fù)雜性的問題時(shí)，它們會(huì)有怎樣的互補(bǔ)作用？
- 高斯消去法：算法的基本過程是很簡單的，但在實(shí)際使用中遠(yuǎn)遠(yuǎn)沒有那么簡單。如何保持計(jì)算的穩(wěn)定性？如何解決稀疏矩陣的計(jì)算效率問題？
- 圖論與線性規(guī)劃：圖論中的許多問題都可以用線性規(guī)劃去解決。圖論中的一些經(jīng)典結(jié)論實(shí)質(zhì)上也可以用線性規(guī)劃的相關(guān)定理去解釋。線性規(guī)劃作為一個(gè)更一般的工具，如何用于處理圖論問題？ 無約束優(yōu)化：無約束優(yōu)化主要用于求解函數(shù)的最大值或最小值的問題。常用的這些方法為何有效？它們之間的差別在哪里？
- 迭代法：常見的迭代算法都有哪些？它們?yōu)槭裁从行В?/li>
- 插值與擬合：插值與擬合的思想是什么？有什么異同？如何運(yùn)用于圖像處理？
本書已建立讀者交流群，歡迎加入該群，與更多同道中人互動(dòng)。具體加群方式，請(qǐng)參見本書封底的讀者服務(wù)。
由于作者水平有限，書中難免有錯(cuò)誤和不足之處，歡迎讀者批評(píng)和指正。
刁瑞、謝妍
? 刁瑞，畢業(yè)于中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院，博士期間的研究方向?yàn)樽顑?yōu)化方法。曾獲2009年英特爾杯全國計(jì)算機(jī)多核程序設(shè)計(jì)大賽第1名，以及2011年KDD Cup第2名等。
? 謝妍，畢業(yè)于中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院，博士期間的研究方向?yàn)椴⑿杏邢拊?jì)算。曾在微軟互聯(lián)網(wǎng)工程院從事搜索研發(fā)相關(guān)工作。
第1章 排序 1
1.1 比較排序 ................................................................................................................ 1
1.1.1 梳排序.......................................................................................................... 2
1.1.2 堆排序.......................................................................................................... 4
1.1.3 歸并排序 ...................................................................................................... 5
1.1.4 快速排序 ...................................................................................................... 8
1.1.5 內(nèi)省排序 ...................................................................................................... 10
1.1.6 Timsort ......................................................................................................... 11
1.2 非比較排序............................................................................................................. 14
1.2.1 桶排序.......................................................................................................... 14
1.2.2 基數(shù)排序 ...................................................................................................... 15
1.3 總結(jié)........................................................................................................................ 16
第2章 哈希 17
2.1 基本概念與實(shí)現(xiàn)..................................................................................................... 17
2.1.1 哈希函數(shù) ...................................................................................................... 17
2.1.2 哈希表.......................................................................................................... 19
2.2 哈希的應(yīng)用............................................................................................................. 20
2.2.1 相似性搜索 .................................................................................................. 20
2.2.2 信息安全 ...................................................................................................... 23
2.2.3 比特幣.......................................................................................................... 25
2.2.4 負(fù)載均衡 ...................................................................................................... 26
第3章 動(dòng)態(tài)規(guī)劃與近似算法 29
3.1 基本概念 ................................................................................................................ 29
3.1.1 動(dòng)態(tài)規(guī)劃 ...................................................................................................... 29
3.1.2 計(jì)算復(fù)雜性 .................................................................................................. 30
3.2 字符串的編輯距離 ................................................................................................. 30
3.2.1 問題引入 ...................................................................................................... 31
3.2.2 動(dòng)態(tài)規(guī)劃算法............................................................................................... 33
3.2.3 滾動(dòng)數(shù)組優(yōu)化............................................................................................... 35
3.2.4 上界限制 ...................................................................................................... 36
3.2.5 解的回溯 ...................................................................................................... 37
3.2.6 分治算法 ...................................................................................................... 38
3.2.7 多個(gè)字符串的編輯距離 ............................................................................... 41
3.3 子集和問題............................................................................................................. 43
3.3.1 問題引入 ...................................................................................................... 43
3.3.2 子集和問題的動(dòng)態(tài)規(guī)劃算法........................................................................ 43
3.3.3 最優(yōu)化問題 .................................................................................................. 44
3.3.4 滾動(dòng)數(shù)組的技巧........................................................................................... 45
3.3.5 貪婪算法 ...................................................................................................... 46
3.3.6 松弛動(dòng)態(tài)規(guī)劃............................................................................................... 47
3.3.7 相關(guān)問題 ...................................................................................................... 48
3.4 旅行商問題............................................................................................................. 50
3.4.1 問題引入 ...................................................................................................... 50
3.4.2 動(dòng)態(tài)規(guī)劃算法............................................................................................... 52
3.4.3 一筆畫問題 .................................................................................................. 52
3.4.4 Christofides算法 .......................................................................................... 54
3.4.5 Lin-Kernighan算法 ...................................................................................... 55
3.5 總結(jié)........................................................................................................................ 58
第4章 高斯消去法 59
4.1 問題引入 ................................................................................................................ 59
4.2 矩陣編程基礎(chǔ)......................................................................................................... 60
4.3 三角方程組............................................................................................................. 62
4.3.1 三角矩陣 ...................................................................................................... 62
4.3.2 三角矩陣的存儲(chǔ)........................................................................................... 63
4.3.3 三角方程組求解........................................................................................... 64
4.4 高斯消去法的原理 ................................................................................................. 66
4.4.1 算法概述 ...................................................................................................... 66
4.4.2 高斯變換 ...................................................................................................... 68
4.4.3 LU分解 ........................................................................................................ 69
4.4.4 Cholesky分解............................................................................................... 70
4.5 主元選擇 ................................................................................................................ 71
4.5.1 列選主元 ...................................................................................................... 71
4.5.2 全選主元 ...................................................................................................... 73
4.5.3 主元與計(jì)算量............................................................................................... 74
4.6 稀疏矩陣的編程基礎(chǔ) ............................................................................................. 75
4.6.1 稀疏向量 ...................................................................................................... 76
4.6.2 稀疏矩陣 ...................................................................................................... 79
4.7 稀疏LU分解.......................................................................................................... 82
4.7.1 Markowitz算法 ............................................................................................ 82
4.7.2 最小度算法 .................................................................................................. 83
第5章 圖論與線性規(guī)劃 86
5.1 線性規(guī)劃基礎(chǔ)......................................................................................................... 86
5.1.1 Fourier Motzkin 消去法............................................................................... 89
5.1.2 基.................................................................................................................. 91
5.1.3 單純形方法 .................................................................................................. 93
5.1.4 對(duì)偶.............................................................................................................. 95
5.2 全單模矩陣詳解..................................................................................................... 98
5.2.1 關(guān)聯(lián)矩陣 ...................................................................................................... 98
5.2.2 全單模矩陣 .................................................................................................. 99
5.2.3 全單模矩陣與圖論....................................................................................... 100
5.2.4 全單模矩陣與線性規(guī)劃 ............................................................................... 103
5.3 圖論中的經(jīng)典問題 ................................................................................................. 104
5.3.1 單源最短路問題........................................................................................... 104
5.3.2 二分圖的最大匹配與最小覆蓋問題 ............................................................ 106
5.3.3 最大流與最小割問題 ................................................................................... 108
5.4 延伸閱讀 ................................................................................................................ 109
5.4.1 逐步線性規(guī)劃............................................................................................... 109
5.4.2 半正定規(guī)劃 .................................................................................................. 111
第6章 無約束優(yōu)化 113
6.1 單峰函數(shù)的最值..................................................................................................... 114
6.1.1 三分法.......................................................................................................... 115
6.1.2 對(duì)分法.......................................................................................................... 115
6.1.3 黃金分割法 .................................................................................................. 116
6.1.4 小結(jié).............................................................................................................. 117
6.2 無導(dǎo)數(shù)優(yōu)化方法..................................................................................................... 118
6.2.1 模式搜索法 .................................................................................................. 118
6.2.2 坐標(biāo)下降法 .................................................................................................. 119
6.2.3 代理模型法 .................................................................................................. 120
6.3 導(dǎo)數(shù)優(yōu)化方法......................................................................................................... 121
6.3.1 線搜索.......................................................................................................... 122
6.3.2 梯度下降法 .................................................................................................. 123
6.3.3 共軛梯度法 .................................................................................................. 124
6.3.4 牛頓法.......................................................................................................... 127
6.3.5 擬牛頓法 ...................................................................................................... 128
6.4 最小二乘 ................................................................................................................ 132
6.4.1 線性最小二乘............................................................................................... 133
6.4.2 非線性最小二乘........................................................................................... 133
第7章 迭代法 136
7.1 線性方程組的迭代法 ............................................................................................. 136
7.1.1 一階定常格式迭代法 ................................................................................... 136
7.1.2 Krylov子空間算法....................................................................................... 142
7.1.3 無約束優(yōu)化方法........................................................................................... 147
7.2 非線性方程組的迭代法.......................................................................................... 147
7.2.1 不動(dòng)點(diǎn)迭代 .................................................................................................. 148
7.2.2 Newton-Raphson迭代.................................................................................. 149
7.2.3 無約束優(yōu)化方法........................................................................................... 152
第8章 插值與擬合 153
8.1 插值........................................................................................................................ 153
8.1.1 常見的插值算法........................................................................................... 154
8.1.2 插值的應(yīng)用 .................................................................................................. 158
8.2 擬合........................................................................................................................ 163
8.2.1 常見的擬合算法........................................................................................... 164
8.2.2 擬合的應(yīng)用 .................................................................................................. 166
參考文獻(xiàn) 169
書單推薦
