【贪心算法】活动安排问题Python实现

文章目录

• • @[toc]
  • • 问题描述
    • 贪心算法
    • 解的最优性
    • `Python`实现
    • 时间复杂性

问题描述

• 设有$n$个活动的集合 E = {   1 , 2 , ⋯   , n   } E = \set{1 , 2 , \cdots , n} E={1,2,⋯,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能选择使用这一资源

• 每个活动$i$都有要求使用该资源的起始时间$s_i$和结束时间$f_i$，且$s_i<f_i$，如果选择了活动$i$，则它在半开时间区间$[s_i,f_i)$内占用资源

• 若区间$[s_i,f_i)$与区间$[s_j,f_j)$不相交，则称活动$i$与活动$j$是相容的，也就是说，当$s_i\ge f_j$或$s_j\ge f_i$时，活动$i$与活动$j$相容

• 在所给的活动集合中选出最大的相容活动子集合

贪心算法

• 用一个集合$A$来存储所选择的活动，用一个变量$j$来记录最近一次加入到$A$中的活动
• 由于输入的活动是按其结束时间的非减序排列的，$f_j$总是当前集合$A$中所有活动的最大结束时间，即 f j = max ⁡ k ∈ A {   f k   } f_{j} = \max\limits_{k \in A}{\set{f_{k}}} fj​=k∈Amax​{fk​}
• 贪心算法一开始选择活动$1$，并将$j$初始化为$1$，然后依次检查活动$i$是否与当前已选择的所有活动相容，若相容，则将活动$i$加入到已选择活动的集合$A$中，否则不选择活动$i$，而继续检查下一活动与集合$A$中活动的相容性
• 由于$f_j$总是当前集合$A$中所有活动的最大结束时间，故活动$i$与当前集合$A$中所有活动相容的充分必要条件是其开始时间$s_i$不早于最近加入集合$A$中的活动$j$的结束时间$f_j$，即$s_i\ge f_j$
• 由于输入的活动以其完成时间的非减序排列，因此算法每次总是选择具有最早完成时间的相容活动加入集合$A$中
• 直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间，也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动

解的最优性

• 贪心算法并不总能求得问题的整体最优解，但对于活动安排问题，贪心算法总能求得整体最优解，即它最终确定的相容活动集合$A$的规模最大，可以用数学归纳法证明
• 事实上，设 E = {   1 , 2 , ⋯   , n   } E = \set{1 , 2 , \cdots , n} E={1,2,⋯,n}为所给定的活动集合，由于$E$中活动按结束时间的非减序排序，故活动$1$具有最早完成时间
• 首先证明活动安排问题有一个最优解以贪心算法选择开始，即该最优解包含活动$1$
  • 设$A\subseteq E$是所给的活动安排问题的一个最优解，且$A$中活动也按结束时间非减序排列，$A$中的第一个活动是活动$k$
    • 若$k=1$，则$A$就是一个以贪心选择开始的最优解
    • 若$k>1$，则设 B = ( A − {   k   } ) ∪ {   1   } B = (A - \set{k}) \cup \set{1} B=(A−{k})∪{1}，由于$f_1\le f_k$且$A$中活动是相容的，故$B$中活动也是相容的，又由于$B$中活动个数与$A$中活动个数相同，且$A$是最优的，故$B$也是最优的，也就是说，$B$是以贪心选择活动$1$开始的最优活动安排
  • 由此可见，总存在以贪心选择开始的最优活动安排方案
• 进一步，在做了贪心选择，即选择了活动$1$后，原问题就简化为对$E$中所有与活动$1$相容的活动进行活动安排的子问题，即若$A$是原问题的最优解，则 A ′ = A − {   1   } A^{'} = A - \set{1} A′=A−{1}是活动安排问题 E ′ = {   i ∣ i ∈ E , s i ≥ f 1   } E^{'} = \set{i \mid i \in E , s_{i} \geq f_{1}} E′={i∣i∈E,si​≥f1​}的最优解
  • 事实上，如果能找到$E^{{}^{\prime }}$的一个解$B^{{}^{\prime }}$，包含比$A^{{}^{\prime }}$更多的活动，则将活动$1$加入到$B^{{}^{\prime }}$中将产生$E$的一个解$B$，它包含比$A$更多的活动，与$A$的最优性矛盾
• 因此，每步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题
• 对贪心选择次数用数学归纳法即知，算法最终产生原问题的最优解

Python实现

def activity_selection(start_times, finish_times):
    n = len(start_times)

    # 创建一个列表用于存储选中的活动
    selected_activities = []

    # 将第一个活动添加到选中列表中
    selected_activities.append(0)

    # 记录上一个选中的活动的索引
    prev_activity = 0

    # 从第二个活动开始进行遍历
    for i in range(1, n):
        # 如果当前活动的开始时间大于等于上一个选中的活动的结束时间, 则将其添加到选中列表中
        if start_times[i] >= finish_times[prev_activity]:
            selected_activities.append(i)

            prev_activity = i

    return selected_activities


start_times = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
finish_times = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

res = activity_selection(start_times, finish_times)

print(f'选中的活动索引: {res}')

选中的活动索引: [0, 3, 7, 10]

时间复杂性

• 当输入的活动已按结束时间的非减序排列时，算法只需$\theta (n)$时间