算法设计与分析 课件 6.3-贪心法应用-活动安排问题.pptx

;活动安排问题：

设有n个活动的集合S={1,2,…,n}，其中每个活动都要求使用同一资源，如教室、会场等，而在同一时间内只有一个活动能使用这个资源。

si，fi分别为活动i的开始和结束时间，且sifi。

活动i与j相容?si?fj或sj?fi。

求：最大的两两相容的活动集A。;问题的解需要满足以下条件：

是n个活动的一个子集

任何两个活动都是相容的

活动个数最多;活动的属性：开始时间、结束时间、持续时间

可能的贪心策略：

尽早开始，优先安排开始时间早的活动

占用时间短，优先安排持续时间短的活动

使剩余时间更多，优先安排结束时间早的活动;选择题。

你觉得以下哪种贪心选择策略可以得到活动安排问题的最优解？;策略1：优先安排开始时间早的活动;策略2：优先安排持续时间短的活动;策略3：优先安排结束时间早的活动;?;S={1,2,…,n}是活动集，且f1?…?fn。

定理：算法GreedySelect执行到第k步，选择k项活动i1=1,i2,…,ik，那么存在最优解A包含i1=1,i2,…,ik。;归纳步骤：假设命题对k为真，证明对k+1也为真。

算法执行到第k步，选择了活动i1=1,i2,…,ik，根据归纳假设存在最优解A包含i1=1,i2,…,ik。

最优解A中剩下的活动子集B来自集合S′={i|i?S,si?fk}，且A={i1,i2,…,ik}?B。

其中B是S′的最优解。;将S′看做一个子问题，根据归纳基础，存在S′的最优解B′含有S′中的第一个活动，即ik+1,且|B′|=|B|,于是;活动安排问题的主要特征：

使用一个共享资源，安排尽可能多的活动。