贪心策略

信息学奥赛⼀本通（提⾼组）⼀、贪⼼算法

选择不相交区间问题：给定n个开区间，选择尽量多个区间，是得这些区间两两没有公共点。（例：活动安排）

按照结束时间由⼩到⼤的顺序排列，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

区间选点问题：给定n个闭区间，在数轴上选尽量少的点，是得每个区间内都⾄少有⼀个点（不同区间内含的点可以是同⼀个）。

（例：种树）

⾸先按照区间的结束位置从⼩到⼤排列。然后在区间中进⾏选择：对于当前区间，若集合中的点不能覆盖它，则将区间末尾的数加⼊集合。 贪⼼策略：取最后⼀个。

区间覆盖问题：给定n隔壁区间，选择尽量少的区间覆盖⼀条指定的线段区间。（例：喷⽔装置）

将所有区间按照左端点由⼩到⼤排序，依次处理每个区间。每次选择覆盖点s的区间中右端点坐标中最⼤的⼀个，并将s更新为该区间的右端点

坐标，直到选择的区间包含t。

贪⼼策略：在某时刻的s，找出⼀个满⾜a[i]<=s的b[i]最⼤值即可。

流⽔作业调度问题：n作业，两机器，先a后b，求总时间最短。（例：加⼯⽣产调度）

直观：让a没有空闲，让b空的少

Johnson算法：对于a=b的集合，按照b⾮升序排列

带期限和罚款的单位时间任务调度：n任务，每个都能在单位时间内完成，每个都有对应的完成期限及完成不了的罚款数额，确定执⾏

顺序使罚款最少。（例：智⼒⼤冲浪）

按照罚款数额由⼤到⼩排序，然后依次进⾏安排。安排规则为：使处理当前任务的时间在既在期限之内，⼜尽量靠后，如果都已经排满，则放

弃处理并扔在最后.⼆、⼆分（单调性）与三分（单峰性）

⼆分的边界问题：

⼆分常见模型：⼆分答案（将最优化问题转为判定性问题），⼆分查找（求解分界点），代替三分（⼆分导函数求极值，定义域通常定为整数域）。

三分：任取两点判断好坏不断缩⼩区间。三，搜索

dfs的优化技巧：优化搜索顺序（对象），排除等效冗余，可⾏性剪枝（上下界剪枝），最优性剪枝，记忆化。

例：数的划分，⽣⽇蛋糕，⼩⽊棍，weight，Addition Chains。

五大基础算法

算法是计算机科学中的一个重要概念，它是指为解决某一问题而设计的一系列计算步骤的有序集合。在计算机科学中，算法是非常重要的，它们是计算机程序的核心部分，可以解决各种计算机科学问题，从简单到复杂都有。基础算法是算法学习中最基本、最常用的一类算法，在日常生活当中也得到广泛应用。接下来我们就来介绍五大基础算法。

一、排序算法

排序算法是将一组数据按照某种规则进行排序的算法。在日常生活中，我们经常使用排序算法来对一些数据进行排序，例如比赛名次，商品价格等等。常见的排序算法有冒泡排序、快速排序、选择排序和插入排序等。

冒泡排序是一种较为简单的排序算法，它的基本思想是对相邻的数据进行比较和交换，从而达到排序的目的。具体实现过程中需要通过两个嵌套的循环来进行比较和交换。快速排序则是一种比较高效的排序算法，它的基本思想是采用“分治”策略，将数据分为两个子序列，一个比关键字小，一个比关键字大。通过递归的方式不断进行分治，最终完成排序。选择排序是通过选择最小的元素放到前面的位置，从而达到排序的目的。插入排序则是通过将元素插入到已经排好序的序列中，使得整个序列有序。

二、递归算法

递归算法是指函数调用自身的一种算法。在计算机科学中，递归算法是一种基本的算法思想，它可以解决一些复杂的问题。例如，二叉树的遍历、图的遍历、背包问题等等都可以使用递归算法来解决。

三、查找算法

查找算法是在一个数据集中查找某一个元素的算法。常见的查找算法有线性查找、二分查找和哈希查找等。

线性查找是将数据集中的元素与目标元素逐一比较，直到找到目标元素为止。二分查找也叫折半查找，它的基本思想是先找到中间元素，再与目标元素进行比较。通过每次缩小查找范围，最终找到目标元素。哈希查找则是通过哈希函数将数据集映射到不同的散列表中，从而进行查找的算法。

四、贪心算法

贪心法

贪心法(Greedy Approach)又称贪婪法, 在对问题求解时，总是做出在当前看来是最好的选择，或者说是：总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心法的设计思想

当一个问题具有以下的性质时可以用贪心算法求解:每一步的局部最优解，同事也说整个问题的最优解。

如果一个问题可以用贪心算法解决，那么贪心通常是解决这个问题的最好的方法。 贪婪算法一般比其他方法例如动态规划更有效。但是贪婪算法不能总是被应用。例如，部分背包问题可以使用贪心解决，但是不能解决0-1背包问题。

贪婪算法有时也用用来得到一个近似优化问题。例如，旅行商问题是一个NP难问题。贪婪选择这个问题是选择最近的并且从当前城市每一步。这个解决方案并不总是产生最好的最优解，但可以用来得到一个近似最优解。

让我们考虑一下任务选择的贪婪算法的问题, 作为我们的第一个例子。问题：

给出n个任务和每个任务的开始和结束时间。找出可以完成的任务的最大数量，在同一时刻只能做一个任务。

例子:

下面的6个任务：

start[] = {1, 3, 0, 5, 8, 5};

finish[] = {2, 4, 6, 7, 9, 9};

最多可完成的任务是：

{0, 1, 3, 4}

贪婪的选择是总是选择下一个任务的完成时间至少在剩下的任务和开始时间大于或等于以前选择任务的完成时间。我们可以根据他们的任务完成时间，以便我们总是认为下一个任务是最小完成时间的任务。

1)按照完成时间对任务排序

2)选择第一个任务排序数组元素和打印。

Frégier定理证明及推广

Frégier定理证明及推广

Frégier定理是图论中的一个重要结论，它提供了关于二分图的一个重要性质。本文将分别介绍Frégier定理的证明方法、定理推广、应用领域以及相关定理。

 定理证明方法

Frégier定理的证明方法基于贪心算法和数学归纳法。以下是具体的证明步骤：

 初始化：令$G$为待处理的二分图，$A$和$B$分别为图的两个子集。选择一个节点$x$，将其放入$A$中。

 贪心策略：对于每个未处理的节点$y$，如果$y$与$A$中的节点相邻接，则将$y$放入$B$中；否则将$y$放入$A$中。

 数学归纳法：假设经过k轮处理后，已经将节点$x_1, x_2, \ldots, xk$分别放入了$A$和$B$中。对于第k+1个节点$x{k+1}$，根据贪心策略进行处理。

在证明过程中，需要证明经过贪心策略处理后，得到的二分图是平衡的，即两个子集的节点数量相差不超过1。为了证明这一点，可以使用数学归纳法，通过对节点数目的归纳来逐步推导。

 定理推广

Frégier定理的推广主要集中在两个方面：一是将定理应用于更广泛的图类，二是寻找更高效的算法实现。

在应用范围方面，Frégier定理的结论可以扩展到一般图论中的平衡二分问题。例如，对于一个给定的图，可以尝试使用Frégier算法将其分成两个平衡的子图。此外，还可以将平衡二分的概念推广到超图上，研究超图的平衡二分问题。 在算法优化方面，贪心策略的核心是将每个节点放入与其相邻接的节点较少的子集中。这一策略可以在实际应用中进行优化，例如使用优先队列等数据结构来加速查找相邻节点的过程。此外，还可以研究使用启发式算法来改进Frégier算法的性能，例如使用模拟退火等优化方法来避免局部最优解。

 应用领域

Frégier定理的应用领域广泛，主要包括以下几方面：

 社交网络分析：社交网络中的用户可以抽象为图的节点，用户之间的互动关系可以抽象为边的连接。通过平衡二分算法，可以将社交网络分成两个子集，便于分析用户群体特征和社交行为模式。