爱德思知识点串讲D1（一）

今天给大家带来的是爱德思的D1，这部分内容因为和国内的课纲差距较大，所以很多从初中在转移到高中的小伙伴在学这门科目的时候会有些困难。今天就把D1的场考试知识点给大家做一个串讲，帮助大家更好的掌握D1 的内容。我把D1的知识点简单的分为两类，一类是与图，也就是数学分支中的图论相关的，一类是其他。

其中第一章算法Algorithms 和第七章算法Linear regression是其他类，而剩下2-6章都和图相关。 今天我们就着重讲解与图论相关的这一部分。在2-6章中，第二章是图的基础知识，介绍一些概念。3-5章相对更加紧密，主要是通过算法来研究一个图。

大家看到一个图，可以问问自己下面这几个问题，这样你就能知道你的基础知识的掌握程度了。这个图是Eulerian graph ,Semi-Eulerian?还是 non-eulerian?如果这个图之间的连线有weight的话？我们怎么写出这张图的distance matrix? 我们怎么找到这张的图的Minimum spanning tree? 我们用三种不同的方法找到的MST的总weights是多少？我们如何找到从A点出发回到A点的最短路径？从A 点出发的到任意一点呢？如果要求从A 点出发回到A点，但是要经过每一个点呢？

这里给出几个常考算法的本质和一些独创的记忆方法，希望对大家有帮助。 Kruskal’a algorithm(国王算法)：每次都选择最短的，除非成圈了。你在做选择的时候就像一个国家国王一样巡视你的领地，一样，能够清楚的看到每个路线的长度，正好，扑克牌中King，本来也是王的意思。

Prim’s algorithm(黑帮算法)：每次都在组织成员里能发展的最方便的下线,注意这里每次选的时候是“已经加入黑帮的所有人中，再拉一个下线最短的距离是多少”，就像黑帮每次发展下线时会开会一样。

Nearest neighbor algotirhm(间谍算法）：每次都由新的组织成员发展最方便的下线，这就像是间谍一样，你发展了一个下线之后，就派这个下线去敌国发展下一个下线，整个组织单线联系，你的下线在发展下一个下线的时候也只能找离他最近的，而不能和他的上级商议。

Dijkstra algorithm（警察算法）：‍‍最短路径中的路径也是最短的，这个非常适合题目做完了去验算你的结果。你可以把自己想象成一个法官，需要破获你们城市的一个犯罪团伙。第一个点就是你抓到的第一个犯人，而目标点就是你要抓的大BOSS。你可以把每次检查和你已经有的点的其他点的距离想象成对这个犯人的审讯，要求他供出其他的同伙，然后咱根据他的供词找到抓起来最方便的那一个（通过找到最短的路径），然后继续审讯抓到的下一个同伙，直到抓到最终的大BOSS。

欧拉图：起点和终点只能解决两个奇数点，因此再多了路线必然重复，每重复一次就解决两个点，因此选择重复路径最短的组合。

而一般考试都会考非欧拉图，这里要注意两个点：第一是，奇数点两两配对之后，注意选择总距离更少的，加上全图的距离总和就是总长第二就是，再回答描述路径的时候要注意一种情况，就是配对的奇数点之间如果没有路程，那么你要写出这两个点之间的路径（也就是你选择的最短路径）之间，需要绕过哪几个点。

比如如果BE之间没有直接的路线，而B-C-E 才是可行的最短路径，那么就一定记得要把C点写在上面。Salesman这一章也是让很多同学头痛的一章，这一章主要的问题就是求 Upper bound 和 Lower bound,这里upper bound 有两种算法，而Lower Bound 只有一种。

UP第一种：Upper bound: 用之前的算法计算出MST，加倍之后再优化

UP第二种：Upper bound Nearest neighbor：轮岗选间谍头子，每一点都作为起点，然后选路径最短的。就像选择每个点当一次“间谍头子”，然后再在所有的结果里面选择最优秀的。注意有的时候题目未必让你把图形中所有的点都选择一遍。

Lower bound:RMST residual minimum spanning tree 先去掉一个点，找MST，然后再把去掉的点通过两条线以最小成本接回来，最后选路径最长的那个。我称为“火葬场”算法，为啥?因为“虐妻一时爽，追妻火葬场”，先把人踢出去，然后再追回来，是不是特别像某些网络小说的常见套路。

第一部分就先说这么多，下次再给大家讲解剩余知识点的内容~