愛德思知識點串講D1（一）

今天給大家帶來的是愛德思的D1，這部分內(nei) 容因為(wei) 和國內(nei) 的課綱差距較大，所以很多從(cong) 初中在轉移到高中的小夥(huo) 伴在學這門科目的時候會(hui) 有些困難。今天就把D1的場考試知識點給大家做一個(ge) 串講，幫助大家更好的掌握D1 的內(nei) 容。我把D1的知識點簡單的分為(wei) 兩(liang) 類，一類是與(yu) 圖，也就是數學分支中的圖論相關(guan) 的，一類是其他。

其中第一章算法Algorithms 和第七章算法Linear regression是其他類，而剩下2-6章都和圖相關(guan) 。 今天我們(men) 就著重講解與(yu) 圖論相關(guan) 的這一部分。在2-6章中，第二章是圖的基礎知識，介紹一些概念。3-5章相對更加緊密，主要是通過算法來研究一個(ge) 圖。

大家看到一個(ge) 圖，可以問問自己下麵這幾個(ge) 問題，這樣你就能知道你的基礎知識的掌握程度了。這個(ge) 圖是Eulerian graph ,Semi-Eulerian?還是 non-eulerian?如果這個(ge) 圖之間的連線有weight的話？我們(men) 怎麽(me) 寫(xie) 出這張圖的distance matrix? 我們(men) 怎麽(me) 找到這張的圖的Minimum spanning tree? 我們(men) 用三種不同的方法找到的MST的總weights是多少？我們(men) 如何找到從(cong) A點出發回到A點的最短路徑？從(cong) A 點出發的到任意一點呢？如果要求從(cong) A 點出發回到A點，但是要經過每一個(ge) 點呢？

這裏給出幾個(ge) 常考算法的本質和一些獨創的記憶方法，希望對大家有幫助。 Kruskal’a algorithm(國王算法)：每次都選擇最短的，除非成圈了。你在做選擇的時候就像一個(ge) 國家國王一樣巡視你的領地，一樣，能夠清楚的看到每個(ge) 路線的長度，正好，撲克牌中King，本來也是王的意思。

Prim’s algorithm(黑幫算法)：每次都在組織成員裏能發展的最方便的下線,注意這裏每次選的時候是“已經加入黑幫的所有人中，再拉一個(ge) 下線最短的距離是多少”，就像黑幫每次發展下線時會(hui) 開會(hui) 一樣。

Nearest neighbor algotirhm(間諜算法）：每次都由新的組織成員發展最方便的下線，這就像是間諜一樣，你發展了一個(ge) 下線之後，就派這個(ge) 下線去敵國發展下一個(ge) 下線，整個(ge) 組織單線聯係，你的下線在發展下一個(ge) 下線的時候也隻能找離他最近的，而不能和他的上級商議。

Dijkstra algorithm（警察算法）：‍‍最短路徑中的路徑也是最短的，這個(ge) 非常適合題目做完了去驗算你的結果。你可以把自己想象成一個(ge) 法官，需要破獲你們(men) 城市的一個(ge) 犯罪團夥(huo) 。第一個(ge) 點就是你抓到的第一個(ge) 犯人，而目標點就是你要抓的大BOSS。你可以把每次檢查和你已經有的點的其他點的距離想象成對這個(ge) 犯人的審訊，要求他供出其他的同夥(huo) ，然後咱根據他的供詞找到抓起來最方便的那一個(ge) （通過找到最短的路徑），然後繼續審訊抓到的下一個(ge) 同夥(huo) ，直到抓到最終的大BOSS。

歐拉圖：起點和終點隻能解決(jue) 兩(liang) 個(ge) 奇數點，因此再多了路線必然重複，每重複一次就解決(jue) 兩(liang) 個(ge) 點，因此選擇重複路徑最短的組合。

而一般考試都會(hui) 考非歐拉圖，這裏要注意兩(liang) 個(ge) 點：第一是，奇數點兩(liang) 兩(liang) 配對之後，注意選擇總距離更少的，加上全圖的距離總和就是總長第二就是，再回答描述路徑的時候要注意一種情況，就是配對的奇數點之間如果沒有路程，那麽(me) 你要寫(xie) 出這兩(liang) 個(ge) 點之間的路徑（也就是你選擇的最短路徑）之間，需要繞過哪幾個(ge) 點。

比如如果BE之間沒有直接的路線，而B-C-E 才是可行的最短路徑，那麽(me) 就一定記得要把C點寫(xie) 在上麵。Salesman這一章也是讓很多同學頭痛的一章，這一章主要的問題就是求 Upper bound 和 Lower bound,這裏upper bound 有兩(liang) 種算法，而Lower Bound 隻有一種。

UP第一種：Upper bound: 用之前的算法計算出MST，加倍之後再優(you) 化

UP第二種：Upper bound Nearest neighbor：輪崗選間諜頭子，每一點都作為(wei) 起點，然後選路徑最短的。就像選擇每個(ge) 點當一次“間諜頭子”，然後再在所有的結果裏麵選擇最優(you) 秀的。注意有的時候題目未必讓你把圖形中所有的點都選擇一遍。

Lower bound:RMST residual minimum spanning tree 先去掉一個(ge) 點，找MST，然後再把去掉的點通過兩(liang) 條線以最小成本接回來，最後選路徑最長的那個(ge) 。我稱為(wei) “火葬場”算法，為(wei) 啥?因為(wei) “虐妻一時爽，追妻火葬場”，先把人踢出去，然後再追回來，是不是特別像某些網絡小說的常見套路。

第一部分就先說這麽(me) 多，下次再給大家講解剩餘(yu) 知識點的內(nei) 容~