7. 贪心算法 Greedy

排课问题

假设开学季的某一个下午多个社团都想要占用霍体开设招新活动，每个活动的时间长度各不相同且开始和结束的时间都各不相同，那么，学校方希望能尽可能多的开设活动，而并不考虑总活动时长的影响因素

最早结束时间算法 Earliest Ending Time EET

将这些活动按照时间结束的早晚进行排序，然后选中最前面那个，然后去除所有重叠的活动，然后递归选取下一个

选择的可靠性 (safe)

我们需要证明我们选择的这个活动确实是能带来最多活动数量的，或者用数学术语来说，存在最优解集 $I_{OPT}$, 我们要证明 我们选择的 first ends $I \in I_{OPT}$
由于根据定义，结束时间 $end(I) \le end(I_{OPT})$
那么由于 $I_{OPT}$ 的下一个元素开始时间一定晚于当前的结束时间，所以 $end(I) < start(I_{OPT, next})$ 因此我们可以将 OPT 选中的改成我们自己选中的
上面的证明说明了第一个元素如果不同，那么逐步替换，逐个找到每个不同的点就可以证明全数组可替代性

最小生成树 Minimum Spanning Tree MST

从图的角度认识树，我们可以将树定义为 无向连通图无循环

生成树 spanning tree

我们将图 G 的子图囊括所有节点且不存在循环 edge 称为 生成树

Kruskal 算法 （加边法）

我们要遵循的最主要原则就是：选边的权值最小的，并且加起来，只要不构成 cycle就行

Prim 算法 （加点法）

首先选取一个节点 $V_1$ 并且观察其终点的可能性，在众多可能性中选取权最小的路径，选中新的节点 $V_2$ 并且继续在 $V_1, V_2$ 的所有可能在未选中的节点连接的路径中权最小的一条继续选择，从而形成递归逻辑

多重解问题

最小生成树的解有多个，但是边权和一定是唯一的

算法对比

以上两种算法，要根据图的具体形状来进行选择，如果稀疏图（边少点多）选择 Kruskal，而 稠密图（点少边多）就选择 Prim 算法