Swift常用算法：經(jīng)典計算機科學問題的Swift實現(xiàn)

目　　錄

第1章 小型問題 1
1.1 斐波那契數(shù)列 1
1.1.1 嘗試遞歸方法 1
1.1.2 利用基本情形 2
1.1.3 計算緩存技術 4
1.1.4 保持斐波那契簡單 5
1.2 簡單數(shù)據(jù)壓縮 6
1.3 牢不可破的加密 9
1.3.1 數(shù)據(jù)排序 10
1.3.2 加密和解密 11
1.4 π的計算 12
1.5 漢諾塔 13
1.5.1 漢諾塔的建模 14
1.5.2 解決漢諾塔問題 15
1.6 實際應用 16
1.7 練習 17
第2章 搜索問題 19
2.1 DNA搜索 19
2.1.1 存儲DNA 20
2.1.2 線性搜索 21
2.1.3 二分搜索 22
2.1.4 泛型示例 24
2.2 迷宮求解 25
2.2.1 生成隨機迷宮 25
2.2.2 其他迷宮細節(jié) 26
2.2.3 深度優(yōu)先搜索 28
2.2.4 廣度優(yōu)先搜索 32
2.2.5 A*搜索 34
2.3 傳教士和食人族 39
2.3.1 問題表示 39
2.3.2 問題解決 42
2.4 實際應用 43
2.5 練習 44
第3章 約束滿足問題 45
3.1 構建約束滿足問題的解決 框架 46
3.2 澳大利亞地圖著色問題 50
3.3 八皇后問題 53
3.4 單詞搜索問題 55
3.5 SEND+MORE=MONEY問題 59
3.6 電路板布局問題 61
3.7 實際應用 61
3.8 練習 62
第4章 圖問題 63
4.1 構建圖框架 65
4.1.1 Edge的具體實現(xiàn) 70
4.1.2 Graph的具體實現(xiàn) 70
4.2 尋找最短路徑 73
4.2.1 定義路徑 73
4.2.2 廣度優(yōu)先搜索(BFS)回顧 74
4.3 最小化網(wǎng)絡建設成本 77
4.3.1 權 77
4.3.2 尋找最小生成樹 82
4.4 在帶權圖中尋找最短路徑 88
4.5 實際應用 93
4.6 練習 94
第5章 遺傳算法 95
5.1 生物學背景知識 95
5.2 預備知識 96
5.3 通用遺傳算法 98
5.4 簡單測試 105
5.5 重新討論SEND+MORE=MONEY問題 108
5.6 遺傳算法面臨的挑戰(zhàn) 112
5.7 實際應用 112
5.8 練習 113
第6章 k-均值聚類算法 115
6.1 預備知識 115
6.2 k-均值聚類算法 120
6.3 基于年齡和地理經(jīng)度的州長聚類算法 124
6.4 k-均值聚類問題及其擴展 128
6.5 實際應用 129
6.6 練習 130
第7章 簡單神經(jīng)網(wǎng)絡 131
7.1 來自生物學的靈感 131
7.2 人工神經(jīng)網(wǎng)絡 133
7.2.1 神經(jīng)元 133
7.2.2 層 134
7.2.3 反向傳播 135
7.2.4 整體情況 137
7.3 預備知識 138
7.3.1 借助隨機化 138
7.3.2 快速算法 140
7.4 激活函數(shù) 141
7.5 構建神經(jīng)網(wǎng)絡 142
7.5.1 實現(xiàn)神經(jīng)元 143
7.5.2 層的實現(xiàn) 144
7.5.3 神經(jīng)網(wǎng)絡的實現(xiàn) 146
7.6 分類問題 149
7.6.1 歸一化數(shù)據(jù) 149
7.6.2 經(jīng)典的iris(鳶尾屬植物)數(shù)據(jù)集 150
7.6.3 葡萄酒分類問題 154
7.7 神經(jīng)網(wǎng)絡問題及其擴展 156
7.8 實際應用 157
7.9 練習 158
第8章 其他問題 159
8.1 背包問題 159
8.2 旅行推銷員問題 163
8.2.1 簡單方法 164
8.2.2 深層考慮 170
8.3 電話號碼助記符 170
8.4 井字棋 172
8.4.1 管理狀態(tài) 173
8.4.2 極小極大算法 175
8.5 實際應用 179
8.6 練習 180
附錄A 術語表 181
附錄B 更多資源 187
附錄C Swift簡史 193