活动选择问题

Scheduling several competing activites that require exclusive use of a common resource,with a goal of selecting a maximum-size set of mutually compatible activities.Suppose we have a set $S=\{a_1,a_2,…,a_n\}$ of n proposed activities that wish to use a resource,such as a lecture,which can serve only one activity at a time.Each activity $a_i$ has a start time $s_i$ and a finish time $f_i$,where $0 \leq s_i < f_i < \infty$.If selected,activity $a_i$ takes place during the half-open time interval $[s_i,f_i)$.Activities $a_i$ and $a_j$ are compatible if the intervals $[s_i,f_i)$ and $[s_j,f_j)$ do not overlap.i.e.,$a_i$ and $a_j$ are compatible if $f_i \le s_j$ or $f_j \le s_i $.

为了操作方便，我们做出如下假设：

活动时间表如下：

i 1 2 3 4 5 6 7 8 9 10 11
$s_i$ 1 3 0 5 3 5 6 8 8 2 12
$f_i$ 4 5 6 7 9 9 10 11 12 14 16

DP

我们先用动态规划的方法解决，那么得先找到最优子结构。

我们令$S_{ij}=\{a_k \in S :s_k \ge f_i \ and \ f_k \le s_j \}$,并令$A_{ij}$为其最大兼容子集，且$a_k \in A_{ij}$，因为$a_k$包含在最优解中，我们可以将原问题分解成两个子问题：$S_{ik}$和$S_{kj}$,自然地，令（这里并没有说$A_{ik}$和$A_{kj}$就是最大兼容子集）

很明显，$A_{ik}$和$A_{kj}$都没有包含$a_k$，因此$A_{ij}=A_{ik} \cup A_{kj} \cup \{ a_k \}$,故

我们可以通过cut-and-paste方法证明：$A_{ij}$一定包含$S_{ik}$和$S_{kj}$的最优解，即证明$A_{ik}$和$A_{kj}$是子问题的最大兼容子集

$Proof$

假设$A’_{ik}$是$S_{ik}$的最优解，$|A’_{ik}| > |A_{ik}|$.

则$|A’_{ik}|+|A_{kj}|+1>|A_{ik}|+|A_{kj}|+1$与$A_{ij}$为最优解矛盾

$A_{ik}$是$S_{ik}$的最优解

对于$A_{kj}$也是一样 $\blacksquare$

我们用$c[i,j]$表示$S_{ij}$的最优解，则

(你可能会对$a_k \in S_{ij}$感到疑问，但是注意max，我们并不知道$a_k$在哪个最大兼容子集中，因此选其最大者就是$A_{ij}$)

首先明确什么时候$S_{ij}=\emptyset$，由其定义可知：

换言之，当$j-i<2$时，$S_{ij}= \emptyset$

我们还需要准备两个虚拟事件$a_0$和$a_{n+1}$，因为$S_{ij}$并不包含$a_i$和$a_j$

我们用一个变量$l$表示序列长度，$l \in [2,n+1]$，子问题通过$l$的大小排序，我们可以通过自底向上的方法解决子问题。

设左边界为$i$，则右边界为$j=i+l$，当$l$最大时，$i_{max}=0=\underbrace{n+1}_{j_{max}}-l_{max}$，当$l$最小时，$i_{max}=n-1=n+1-l_{min}$

左边界大小受$l$约束，关系为$i_{max}=n+1-l$，这个并不难理解，我们将右边界放在最右边，此时左边达到最大值，距离为$l$。

综上，$i \in [0,n+1-l]$。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
DYNAMIC-ACTIVITY-SELECTOR(s,f,n)
let c[0...n+1,0...n+1] and act[0...n+1,0...n+1] to be new table
for i ← 0 to n do
	c[i,i] ← 0
	c[i,i+1] ← 0

c[n+1,n+1] ← 0

for l ← 2 to n+1 do
	for i ← 0 to n+1-l do
		j=i+l
		c[i,j]=0
		k ← j-1
		while k>i do
			if f[i] <= s[k]  and f[k] <= s[j] and c[i,j]<c[i,k]+c[k,j]+1 then
				c[i,j] ← c[i,k]+c[k,j]+1
				act[i,j] ← k
			k ← k-1
print c[0][n+1]
PRINT-ACT(c,act,i,j)

PRINT-ACT(c,act,i,j)
if c[i][j]>0
	PRINT-ACT(act,i,k)
	PRINT-ACT(act,k,j)
	print 'a'
	print k

C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void Activity_Selection(int* s, int* f, int n) {
    auto c=newArray2<int>(n+2,n+2);
    auto act=newArray2<int>(n+2,n+2);

    for(int i=0;i<=n;++i){
        c[i][i]=0;
        c[i][i+1]=0;
    }
    c[n+1][n+1]=0;
    int j,k;
    for(int l=2;l<=n+1;++l){
        for(int i=0;i<=n+1-l;++i){
            j=i+l;
            c[i][j]=0;
            k=j-1;
            for(k=j-1;k>i;--k){
                if(f[i]<=s[k] && f[k]<=s[j] && c[i][j]<c[i][k]+c[k][j]+1){
                        c[i][j]=c[i][k]+c[k][j]+1;
                        act[i][j]=k;
                }	//if
            }	//for of k
        }	// for of i
    }	//for of l

    std::cout<<c[0][n+1];
    print_act(c,act,0,n+1);

    deleteArray2(c,n+2);
    deleteArray2(act,n+2);
}

void print_act(int** c,int** act,int i,int j){
    if(c[i][j]>0){
        int k=act[i][j];
        print_act(c,act,i,k);
        print_act(c,act,k,j);
        std::cout<<"a"<<k<<" ";
    }
}

int main(){
    vector<string> act;

    vector<intPair> time{
            {0,0},
            {1,4},
            {3,5},
            {0,6},
            {12,16},
            {2,14},
            {5,7},
            {5,9},
            {3,9},
            {6,10},
            {8,12},
            {8,11},
            {INT_MAX,INT_MAX}
    };
    sort(time.begin(), time.end(), iP_comp());
    int s[13],f[13];
    auto b=time.begin();
    for(int i=0;i<time.size();++i){
        s[i]=b->first;
        f[i]=b->second;
        ++b;
    }
    
    Activity_Selection(s,f,11);
}

由三重循环不难得知该算法时间复杂度为$O(n^3)$

接下来考虑用贪心算法优化该问题

Greedy Choice

根据直觉，我们要选择集合S中最先完成的活动，因为这样就可以尽可能的留下其他（兼容）活动去选择。而根据前面的假设，完成时间$f_i$是单调递增的，因此我们做出第一个贪心选择：$a_1$

现在的子问题是：在$a_1$完成后开始的活动中选择第一个完成的活动。我们并不需要考虑在$a_1$开始前完成的活动，因为满足该条件的活动必然不兼容：$a_1 < f_1 \ but \ f_j(j>1) >f_1 \ $ 所以 $\ f_j>a_1$。

令$S_k=\{a_i \in S :s_i \ge f_k\}$，$S_k$既是个活动集合，也是个子问题。原问题是在S中找到最大兼容子集，这里为了编码方便，令$S_0=S,f_0=0$。由最优子结构可知，原问题的最优解包含$a_1$和相关子问题最优解中的所有活动。

接下来，验证该直觉是否正确:

Theorem

Consider $\forall S_k \ne \emptyset$，and let $a_m \in S_k$ with the earlist finish time.Let $A_k$ be a maximum-size subset of mutually compatible activites of $S_k$,then $a_m$ is included in some $A_k$.

$Proof:$

设$A_k$中最先完成活动为$a_j$,

if $a_m = a_j$，显然，$a_m \in A_k$

else，令$A’_k=A_k- \{ a_j \} \cup \{a_m\}$，因为$A_k$即使将$a_j$剔除也相互兼容，而$a_m$是$S_k$中最先完成的活动（比$a_j$先），因此加入到$A_k$中能保证相互兼容。因为$|A_k|=|A’_k|$,所以$A’_k$也是一个最大兼容子集，$a_m \in A’_k$满足条件

命题得证。

这个定理告诉我们：子问题（原问题）的最先完成活动必然是其最大兼容子集的元素。

依次考虑每个活动，其中兼容的活动加入到$S$的最大兼容集合中，不是每个子问题的最先完成活动都是$A_0$的元素，但是$A_0$的元素一定在子问题中，我们只要取舍就行了。

依次做出贪心选择：与$A_0$中（最后一个）元素兼容且最先完成的活动，选择最合适的路径，得到更为直接的最优子结构（对比DP）。

由于完成时间是单调递增的，因此每个活动只需要考虑一次，也正因此，时间复杂度为$O(n)$。

递归版本

1
2
3
4
5
6
7
RECURSIVE-ACTIVITY-SELECTOR(s,f,k,n)
m ← k+1
while m <= n and s[m]<f[k] do
	m ← m+1
if  m <= n then
	return {a_m} ∪  RECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)
else return ∅

翻译成C++如下：

1
2
3
4
5
6
7
8
9
void Activities_Choice(int* s,int* f,int k,int n,std::vector<std::string>& act){
    int m=k+1;
    while(m<=n&&s[m]<f[k])
        ++m;
    if(m<=n) {
        act.emplace_back("a" + std::to_string(m));
        Activities_Choice(s,f,m,n,act);
    }
}

示意图如下：

image.png

迭代版本

实际上，由“尾递归”转换为迭代是十分容易的：

1
2
3
4
5
6
7
8
9
ITERATIVE-ACTIVITY-SELECTIOR(s,f)
n ← s.length
A ← {a_1}
k ← 1
while m ← 2 to n do
if s[m] >= f[k] then
	A ← A ∪ {a_m}
	k ← m
return A

小结

贪心算法并不关注重叠子问题，而是做出贪心选择，然后继续执行对应的子问题从而达到最优解，因此它并不会像bottom-up那样遍历所有先决子问题最后来解决自己，而是选择一条路径来解决