关于贪心算法的非专业向证明

当前位置：首页 > 滚动 > 正文

关于贪心算法的非专业向证明

来源 : 哔哩哔哩时间：2023-06-15 13:02:16

这是计算机算法课结课作业的一部分，因为比较有意思，所以放了上来。希望自己以后也可以在需要用到的时候想起还有这么一回事。这里的文字大抵也谈不上证明，仅仅只算是自己的思考过程吧。

在实现贪心算法来解决活动安排问题之前，我们先证明一下为什么贪心算法可以在活动安排问题中一定可以获得最优解。

【资料图】

首先我们先来看看活动安排问题的定义，在一系列开始和结束时间不同的活动中选择出最大的相容活动子集合。

以下是比较细节的定义：

问题描述设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

利用我们的数学归纳法：

当问题的n=1时，及按照贪心算法的选择，自然只会选择唯一的那一个活动。而又因为集合最大为1，因此此时贪心算法一定为最优解。

接下来，我们需要证明：假设n=k时贪心算法能获得最优解(集合容量=a)，那么n=k+1能获得最优解(及集合容量为a/a+1)。

对于n=k+1组成的活动集合A，我们先去掉结束时间s最小的元素。

此时，n=k，那么根据我们的假设，根据贪心法获得的最大子集B，为此时最优解。

此时再加入b1:

若不冲突，直接加入，保持最优解性质。

若冲突，此时b1一定在新的最优解集合中。那么我们去掉此时在原最优解集合中的第一个元素，及那个与b1冲突的元素，此时n=k，一定获得最优解。(假设在最优解中，我们选择了与 A1 冲突的另一个活动 Ak（k > 1）。那么我们可以将 Ak 替换为 A1，得到一个新的解，该解与最优解的活动数量相同或更多，并且满足互不冲突的条件。)

保持原性质，证毕。

因此，得证n=k+1时可获得最优解。

然而，这真的结束了吗。其实不然。第二天再次回顾，发现了一处逻辑的不完整：我没有证明当活动按照结束时间s从小到大排序时，此时最优解中一定可以包含b1。(即某个最优解不一定会包含b1，但是全部最优解集合中一定存在包含b1的最优解集合).

那么接下来我们可以证明这件事：

我们假设按照结束时间从小到大排序的活动集合E={1,2,…,n}存在一个最优解A，且A中也按照结束时间从小到大排序。设A的第一个活动为K1.那么有

若K1=1，此时证毕。

若K1≠1，那么此时由于1的结束时间一定小于K1，因此当我们将该集合中的K1替换为1时，由于A为最优解，其最大相容子集合的元素数量在E中就是该集合的最大相容子集合的元素数量。因此，由于数量不改变，此时的集合仍然为最大相容子集合，证毕。

不得不承认，我的语言比较不严谨，但是我认为所有的逻辑应当已经不存在谬误。

如发现逻辑谬误，请随意指出。

X 关闭

精心推荐

关于贪心算法的非专业向证明