关于贪心算法毕业论文的相关提问

•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。

贪心与动态规划： 与动态规划不同的是，贪心是 鼠目寸光 ；动态规划是 统揽全局 。

–动态规划：每个阶段产生的都是全局最优解

•第i阶段的“全局”： 问题空间为(a1, … , ai)

•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解

–贪心：每个阶段产生的都是局部最优解

•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai

•第i阶段的“局部最优解”： ai

•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。

–这是贪心算法与动态规划算法的主要区别。

•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

•要求高效地安排一系列争用某一公共资源（例如会议室）的活动（使尽可能多的活动能兼容使用公共资源）。

–设有n个活动的集合E={e1,e2…en}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si

–若区间[si,fi)与区间[sj,fj)不相交，则称ei和ej是相容的。也就是说，当si≥fj或sj≥fi时，活动i和活动j相容。

•活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。