算法设计与分析第4章

1、 设有设有n n个活动的集合个活动的集合E=1,2,nE=1,2,n，其中每个活动都，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动一个活动能使用这一资源。每个活动i i都有一个要求使用都有一个要求使用该资源的起始时间该资源的起始时间sisi和一个结束时间和一个结束时间fi,fi,且且si fisi fi 。如果。如果选择了活动选择了活动i i，则它在半开时间区间，则它在半开时间区间si, fi)si, fi)内占用资源。内占用资源。若区间若区间si, fi)si, fi)与区间与区间sj, f

2、j)sj, fj)不相交，则称活动不相交，则称活动i i与活与活动动j j是相容的。也就是说，当是相容的。也就是说，当sifjsifj或或sjfisjfi时，活动时，活动i i与与活动活动j j相容。相容。下面给出解活动安排问题的贪心算法GreedySelectorGreedySelector 描述:各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时间的非减序排列序排列 所谓所谓是是指所求问题的指所求问题的可以可以通过一系列通过一系列的选择的选择，即贪心选择来达到。这是，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也

3、是贪心算法与动态贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。规划算法的主要区别。 动态规划算法通常以动态规划算法通常以的方式解各子问题，的方式解各子问题，而贪心算法则通常以而贪心算法则通常以的方式进行，以迭代的方的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整质，必须证明每一步所作的贪心选择最终导致问题的整体最优解

4、。体最优解。3、贪心算法与动态规划算法的差异 这这2 2类问题都具有类问题都具有性质，极为相似，但性质，极为相似，但背包问题可以用贪心算法求解，而背包问题可以用贪心算法求解，而0-10-1背包问题却不能背包问题却不能用贪心算法求解。用贪心算法求解。 用贪心算法解背包问题的基本步骤： 算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O O（nlognnlogn）。）。为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明

5、背包问题具有贪心选择性问题具有贪心选择性质质。102030501.￥60 2.￥100 3.￥120 4.背包 =￥220=￥160=￥180=￥240100201203060101002060101203060101002080201202030 0-1背包问题 背包问题 11max011niiniiiixw xcxin=危，1min |1ii nki x=1111nnniikiiiiiiiw ywww xw xc=-+邋11nniiiiyx=邋( )( )( )Tc CB Tf c dc= DijkstraDijkstra算法的迭代过程：算法的迭代过程： 赋权图的邻接表赋权图的邻接表)(n

6、O)(2nO)(2nO 可以用反证法来证明这个MST性质： 假设不存在这样一棵包含边（u , v）的最小生成树。 任取一棵最小生成树T，将（u , v）加入T中。根据树的性质，此时T中必形成一个包含（u , v）的回路， 且回路中必有一条边（u, v）的权值大于或等于（u , v）的权值。 删除（u, v），则得到一棵代价小于等于T的生成树T，且T为一棵包含边（u , v）的最小生成树。 这与假设矛盾， 故该性质得证。 uuvvV1V2V4V5V3V66555662134V1V2V4V5V3V61V1V2V4V5V3V614V1V2V4V5V3V6142V1V2V4V5V3V61425V1V2V4V5V3V614253)(2nOV1V2V4V5V3V66555662134V1V2V