算法设计与分析期末考试复习（四）

贪心算法（Greedy Algorithm）

找零钱问题
假设有4种硬币，面值分别为：二角五分、一角、五分和一分，现在要找给顾客六角三分钱，如何找使得给出的硬币个数最少？

首先选出1个面值不超过六角三分的最大硬币，即两角五分
然后从六角三分中减去两角五分，剩下三角八分
再选出1个面值不超过三角八分的最大硬币
即又一个两角五分。如此一直做下去……
这里用到的方法就是贪心算法

在这个例子中，找硬币算法得到的结果是整体最优解，问题本身具有最优子结构性质，可以用动态规划算法求解，用贪心算法更简单、更直接、且解题效率更高分。

贪心算法的基本思想

• 贪心算法在每一步选择中都采取在当前状态下最优的选择：目的是希望由此导出的结果是最优的。
• 贪心算法在求解问题时并不着眼于整体最优，它所做出的选择仅仅是当前看来最优的。
• 最优子结构性质：局部最优解能决定全局最优解。
• 问题能够分成子问题来解决。
• 子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的区别

动态规划

1. 每一步的最优解是由上一步的局部最优解进行选择得到的。
2. 因此需要保存（之前求解的）所有子问题的最优解备查。

贪心算法

1. 下一步的最优解是由上一步的最优解推导得到的。
2. 当前最优解包含上一步最优解，之前的最优解不作保留。
3. 在贪心算法中做出的每步决策都无法改变（不能回退）。

二者关系

1. 贪心算法本质上是一种更快的动态规划算法。
2. 贪心法正确的条件：每一步的最优解一定包含上一步的最优解。
3. 如果可以证明：在递归求解的每一步，按贪心选择策略选出的局部最优解，最终可导致全局最优解，则二者是等价的。

**贪心算法对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前结果进行选择，有回退功能。对某些问题动态规划算法并不是最简便的方法，因为有时候确实没有必要知道所有子问题的解。
**

贪心算法得到的结果不能保证全局最优

活动安排问题

设：有n个活动的集合E={1,2,…,n}，其中：每个活动都要求竞争使用同一资源（如演讲会场等），而在同一时间内只有一个活动能使用这一资源，每个活动 i 都有一个请求使用该资源的起始时间 si ，每个活动 i 都有一个使用资源的结束时间 fi，且 si < fi ，如果选择了活动 i，则它在半开时间区间[si, fi)内占用资源，若区间[si, fi)与[sj, fj)不相交，则称活动i与活动j是相容的，也就是说，当 si ≥ fj 或 sj≥fi 时，活动i与活动j相容。
活动安排问题就是要在所给的活动集合中，选择最大的相容活动子集合，使尽可能多的活动能使用资源。

证明：按F[1:n]递增顺序进行贪心选择可得到全局最优解
首先证明活动安排问题有一个最优解以贪心选择开始

1. 设E={1,…,n}为给定活动集合（按结束时间非减序排列），显然活动1具有最早的完成时间。
2. 设集合A是该问题的一个最优解，同时第一个活动是活动k。
3. 若k=1，则A就是一个以贪心选择开始的最优解。
4. 若k>1，则设(A-{k})∪{1}，由于由于F[1]≤F[k]，且A中活动相容，故B中活动也相容，由于B和A中包含的活动个数相同，故B也是最优的。

得证：总存在一个以贪心选择开始的最优活动安排方案。

用数学归纳法证明贪心算法的解是全局最优解

1. 设E={1,2,…,n}为所给的活动集合，在做了贪心选择，即选择了活动1后，原问题就简化为对E中所有与活动1相容的活动进行活动安排的子问题。
2. 若A是原问题的最优解，则A`=A-{1}是活动安排问题E’={i∈E : si ≥ f1}的最优解。
3. 证明：如果能找到E’的一个解集B’，它包含比A’更多的活动，则将活动1加入到B`将产生A的一个解，它包含比A更多的活动，这与A的最优性矛盾！
4. 因此：在做出贪心选择（活动1）之后，原问题N简化为：子问题N’：对E中所有与活动1相容的活动进行安排

每一步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。

算法设计

1. 用数组A[1:n]来存储所选择的活动（设活动总数为n），若活动i在集合A中，则A[i]=1，否则A[i]=0.
2. 各活动的起始时间和结束时间存储于数组S[1:n]和F[1:n]中，数组F[1:n]已按结束时间的非减序排列。
3. 依次从F[1:n]中选择活动i，尝试加入集合A，设：变量k记录A中最近一次加入的活动：由于F[1:n]有序，所以F[k]总是当前集合A中所有活动的最大结束时间。
4. 依次检查活动i是否与当前已选择的所有活动相容，若相容则将活动i加入集合A中，若不相容，则放弃活动i。
5. 继续检查F[1:n]中下一个活动与集合A中活动的相容性。
6. 直到所有活动均已检查完毕，程序结束。

新增的活动i和当前集合A中所有活动相容的充分必要条件是

• S[i]≥F[k]，活动i的开始时间不早于k的结束时间，k为最近加入集合A的活动，若条件满足，则活动i取代k成为最近加入的活动。
• 若S[i]<F[k]，则放弃活动i，转而考虑下一个活动。

这种方式为后续活动预留尽可能多的时间

• 由于输入的活动按照其完成的时间非减序排列
• 所以每次总是选择具有最早完成时间的相容活动加入集合A
• 贪心选择的意义在于：使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

int greedySelector(int s[],int f[],int a[],int n){a[1] = 1;int j = 1;int count = 1;for(int i=2; i<=n; i++){if(s[i] >= f[j]){count++;j = i;a[i] = 1;}else{a[i] = 0;}}return count;
}

贪心算法求解背包问题

1. 首先计算每种物品单位重量价值Vi/Wi
2. 然后按照贪心选择策略：将尽可能多的单位重量价值最高的物品装入背包。
3. 若将这种物品全部装入后，背包内的物品总重量未超过C
4. 则选择单位重量价值次高的物品并尽可能多地装入背包
5. 依次策略一直进行下去，直到背包装满为止。

算法复杂度分析：计算时间主要用于对各种物品按单位重量价值排序，因此算法的计算时间上界为O(nlogn)

对于0-1背包问题，贪心选择为什么不能得到最优解

• 因为对该问题采用贪心选择策略无法确保最终将背包装满
• 部分闲置的背包空间降低了每公斤背包空间的价值

最优装载问题

有一批集装箱要装船，其中：集装箱 i 的重量为wi ，轮船最大载重量为c，要求：在不受体积限制的情况下，将尽可能多的集装箱装船。
给定：c>0, wi>0, 1≤i≤n
要求：找出一个n元0/1向量x=(x1,x2,…,xn) 其中 xi∈{0,1}
时间复杂度O(nlogn)

void loading(int x[],int w[],int c,int n){int *R = (int *)malloc(sizeof(int)*(n+1));//根据w从小到大排序，数组R记录调整后的序号sort(w,R,n);for(int i=1; i<=n; i++){x[i] = 0;}for(int i=1; i<=n; i++){int id = R[i];if(w[id] > c){break;}x[id] = 1;c -= w[id];}	
}

单源最短路径

单源最短路径 Single-Source Shortest Path (Dijkstra算法)
所有顶点对间的最短路径问题 All-Pairs Shortest paths （Floyd算法）

在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题。

单源最短路径问题
给定：带权有向图G=(V,E)，其中：每条边的权是非负实数，给定顶点集合V中的一个顶点v，称为源点，求解：从源点v到G中其余各顶点之间的最短路径

Dijkstra算法是求解单源最短路径问题的一种有效算法

1. 将图中所有顶点分成两组：S，V-S
2. S：已确定最短路径的顶点的集合
3. T=V-S：尚未确定最短路径的顶点集合
4. 初始时，集合S中仅包含源点V0
5. 不断在集合T中做贪心选择扩充集合S
6. 直到S中包含了V中的所有顶点

算法设计思想：

1. 初始时，S仅包含源v0
2. 定义“特殊路径”：从源v0到G中某一顶点u且中间只经过S中顶点的路径称为从源到u的路径。
3. 用数组元素dist[u]记录源v0到u的最短特殊路径的长度。

Dijkstra算法每次从T中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到其它所有顶点之间的最短路径长度。

Dijkstra算法的数据结构设计

• 使用带权邻接矩阵表示有向图G
• 辅助数组：Snvex：表示已找到从V0出发的最短路径的终点的集合。
• 辅助数组：dist[nvex]：存放当前找到的从V0到每个Vi的最短路径长度。
• 辅助数组：prev[next]：数组元素为从V0到路径各顶点的最短上该顶点的前一顶点的序号

算法伪代码：

1. 令S={V0}，T={其余顶点}
2. T中顶点Vi对应的距离值dist[i]为：若存在<V0,Vi>：dist[i]为<V0,Vi>弧上的值；若不存在<V0,Vi>：dist[i]为∞
3. 从T中选取一个dist矩阵值最小的顶点u加入S
4. 对T中每一个顶点Vj的距离值dist[j]进行修改，若增加u作为中间顶点之后，从V0到Vj的距离比不加u的路径要短，则更新Vj距离值。
5. 重复上述步骤，直到S中包含所有顶点（S=V）为止

void Dijkstra(int n,int v,int dist[],int prev[],int **c){int s[n];for(int i=1; i<=n; i++){dist[i] = c[v][i];s[i] = false;if(dist[i] == maxint){prev[i] = 0;}else{prev[i] = v;}}dist[v] = 0;s[v] = true;for(int i=1; i<n; i++){int temp = maxint;int u = v;for(int j=1; j<=n; j++){if(!s[j] && dist[j]<temp){u = j;temp = dist[j];}}s[u] = true;for(int j=1; j<=n ;j++){if(!s[j] && (c[u][j] < maxint)){int newdist = dist[u] + c[u][j];if(newdist < dist[j]){dist[j] = newdist;prev[j] = u;}}}}
}

算法复杂度分析：对于具有n个顶点和e条边的带权有向图G，需O(n²)

多机调度问题

设：有n个独立的作业{1,2…n}，这n个作业由m台相同的机器进行加工处理，作业 i 所需要的执行时间为：ti，每个作业均可以在任何一个机器加工处理，但作业未完成之前不容许中断处理，作业也不能拆分为更小的子作业。

多机调度问题要求：给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

这个问题是NP完全问题，目前为止还没有十分有效的解法，用贪心选择策略有时可以设计出较好的近似算法。

具体来说：采用最长处理时间优先的贪心选择策略

• 当n≤m时，只要将机器i的[0,ti]时间区间分配给作业i即可。算法只需要O(1)时间
• n＞m时，首先将n个作业依其所需的处理时间从大到小排序，然后依次顺序将作业分配给空闲的处理机，算法所需的计算时间为O(nlogn)