贪心(一)——活动安排问题

佚名 6年前 (2019-05-10) 随笔 1922人围观抢沙发百度已收录

　　求最优解的问题可看作是通过一系列步骤，每一步有一选择的集合，对于较简单的问题，动态规划显得过于复杂，可用较简单有效的算法求解之，如贪心。贪心算法总是在当前步骤上选取最好的方案，即它是一种局部最优的选择，并希望它导致一个全局最优(但有时是不可能导致全局最优，例如，求v到w的一条最短路径，若从v搜索到邻点t最短，未必是v到w最短)。但是，仍有许多问题贪心法将产生全局最优解，如MST，单源最短路径等。

贪心算法的思想

　　贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　每一步只考虑一个数据，他的选取应该满足局部优化的条件。

　　若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

活动安排问题

　　活动安排问题是用贪心算法有效求解的一个典型的例子，进行高效地安排一系列争用某一公共资源的活动。

　　设待安排的11个活动的开始与结束时间按结束时间增序排列如下：

　　问题的解：A1={a3,a9,a11}，A2={a1,a4, a8,a11}，A3={a2,a4,a9,a11}

　　最优解： A2 和 A3

　　此问题可用迭代方法直接给出贪心算法，但为比较和动态规划之关系，下面先考虑动态规划解法。

活动安排问题的最优子结构

　　子问题空间可描述为：

　　Sij 是 S 的子集，它包含那些 (在 ai 完成后开始)&&(在 aj 开始前完成) 的活动 ak。

　　亦即：Sij中所有活动ak与活动 ai、aj 相容，不妨称 ai、aj 和子集 Sij 相容，因此 ak 也与所有不迟于 fi 完成的活动以及与所有不早于 sj 开始的活动相容。(Sij中可能有冲突的活动)

　　为方便处理，设有两个虚拟的活动 a0 和 an+1，并且假定，因此，

　　为了更严格定义 i 和 j 的范围，假定所有活动已按完成时间的单调增有序：

　　分解问题：

　　设子问题。若 Sij 的解中选择了ak，使用 ak 产生 Sij 的两个子问题 Sik 和 Skj：

　　Sik是包括在 ai 完成之后开始，在 ak 开始之前完成的那些活动；Skj 包括在 ak 完成之后开始，在 aj 开始之前完成的那些活动。两者均是 Sij 的子集，这两子集与 ak 相容。

　　Sij 的解显然是 Sik 和 Skj 解的并，再加上ak (Sik和Skj已去掉了那些与ak冲突的活动，而这些活动原来可能在Sij中)

　　最优子结构：

　　当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

　　设 Sij 的最优解是 Aij，ak∈Aij，则两子问题的解 Aik 和 Akj 也必须是最优的(反证法易证)。

　　用问题的最优子结构构造原问题的最优解：把子问题的解、局部最优解合成原来解问题的一个解。

一个递归解

　　设C[i,j] 表示 Sij 的最优解的值，即 Sij 中相容活动最大子集的 size：C[i,j] = |Aij|

动态规划到贪心法的转化

　　到了这里，就可以用动态规划进行求解。

　　当然，可以通过下面的定理化简其解，同时也可以说明贪心算法的正确性。

　　定理：设 Sij 是任一非空子问题，am 是 Sij 中具有最早完成时间的活动：fm = min{ fk: ak∈Sij} ，则：

　　　　①活动 am 必定被包含在 Sij 的某个最优解中；

　　　　②子问题 Sim 是空集，使Smj 是唯一可能的非空集。 ✳选am的目的

　　在动态规划求解时，原问题Sij 分解为两个子问题Sik 和 Skj 求解，且这种分解有 j-i-1 种可能。

　　该定理将其简化为：

　　　　①求Sij 的最优解时只用到一个子问题，另一个子问题为空；

　　　　②只须考虑一种选择：即选Sij中最早完成的活动。

　　该定理带来的另一个好处是：能以自顶向下的方式解每一个子问题：

贪心选择(具体内容下一篇中会提到)：

　　当某个 ami 加入解集合后，我们总是在剩余的活动中选择第一个不与 ami 冲突的活动加入解集合，该活动是能够最早完成且与 ami 相容。这种选择为剩余活动的调度留下了尽可能多的机会。即留出尽可能多的时间给剩余的尚未调度的活动，以使解集合中包含的活动最多。每次选一个最早完成并与刚加入解集元素相容的活动。