贪心算法 主讲：朱佳 博士 华南师范大学计算机学院.

Presentation on theme: "贪心算法 主讲：朱佳 博士 华南师范大学计算机学院."— Presentation transcript:

1 贪心算法 主讲：朱佳 博士 华南师范大学计算机学院

2 贪心算法(Greedy method) 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 目的：用于求解最优化问题 用于交通和通讯,用于运输装船,有限期的作业调度和计算机调度

3 基本思想 将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体的最优解。 [常见应用] 背包问题,最小生成树,最短路径,作业调度等等 [算法优点]求解速度快,时间复杂性有较低的阶. [算法缺点]需证明是最优解.

4 [适用问题] 具备贪心选择和最优子结构性质的最优化问题 贪心选择性质：整体的最优解可通过一系列局部最优解达到，即贪心选择到达。
贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模更小的问题。 对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从 贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 子问题最优解也就是局部最优解

5 A(1) A(2) … A(n-1) A(n) … 某一问题的n个输入 是A的一 个子集 满足一定 的条件 约束条件 B1(1) B1(2)
算法设计与分析 > 贪心算法 某一问题的n个输入 A(1) A(2) … A(n-1) A(n) 是A的一 个子集 满足一定 的条件 约束条件 … B1(1) B1(2) … B1(m) Bk(1) Bk(2) … Bk(m) 取极值 理想情况，一个问题可能有很多可行解 该问题的一种解（可行解） 目标函数 最优解

6 算法设计与分析 > 贪心算法 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 [问题陈述]设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。 教室的排课 则称活动i与活动j是相容的。也就是说，当si≥fi； ，活动i．与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容 所给出的解活动安排问题的贪心算法中，且是所要求的最大相容活动子集，而已知 起始时间和结束时间存储于数组5和／中且按结束时间的非减序：f1≤f2≤...≤ 果所给出的活动未按此序排列，我们可以用第七章将介绍的算法在O(n1ogn)的时 )设有n个活动 ．贪心选择性质 L ’ ‘ ’ [集装箱已依其重量从小到大排序，(工1，刀2，…，工，2)是最优装载问题的一个最优解。又设 把㈠[Jf：1}。易知，如果给定的最优装载问题有解，则l≤是≤"。 1) 当是二1时，(J1，工2，…，工f2)是一个满足贪心选择性质的最优解。 1)·当是>1时，取y1二1；yA二0；y／二t／，1<i≤f2，2·乒是，则， ∑wiyi=仞：—吼+∑WiXi≤∑wixi≤c ‘· l’l i二1 i二1 如l，》／2，…，儿)是所给最优装载问题的一个可行解。 }一方面，由∑y／’∑Jf知，(y1，夕2，…，yn)是一个满足贪心选择性质的最优解。所以， I二1 j二1 减问题具有贪心选择性质。 最优子结构性质 ：! ． ：(卸，J2，…，z，1)是最优装载问题的一个满足贪心选择性质的最优解，则易知，刀3；1， ·，J，2)是轮船载重量为c—Wl且待装船集装箱为{2，3，…，ni时相应最优装载问题的一 解。也就是说，最优装载问题具有最优子结构性质。 最优装载问题的贪心选择性质和最优子结构性质，容易证明算法Loading的正确性。 珐Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时 )(，2logn)

7 [算法思路]将n个活动按结束时间非减序排列,依次考虑活动i, 若i与已选择的活动相容,则添加此活动到相容活动子集.
[例] 设待安排的11个活动起止时间按结束时间的非减序排列 i s[i] f[i] 最大相容活动子集(1, 4, 8, 11), 也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1) 时间不能冲突

8 各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列
算法设计与分析 > 贪心算法 活动安排问题贪心算法 template< class Type > void GreedySelector(int n, Type s[ ], Type f[ ], bool A[] ) { A[ 1 ] = true; int j = 1; //从第二个活动开始检查是否与前一个相容 for (int i=2;i< =n;i+ +) { if (s[i]>=f[j]) { A[i] = true; j=i;} else A[ i] = false;} } 各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 教室的排课 则称活动i与活动j是相容的。也就是说，当si≥fi； ，活动i．与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容 所给出的解活动安排问题的贪心算法中，且是所要求的最大相容活动子集，而已知 起始时间和结束时间存储于数组5和／中且按结束时间的非减序：f1≤f2≤...≤ 果所给出的活动未按此序排列，我们可以用第七章将介绍的算法在O(n1ogn)的时 )设有n个活动 ．贪心选择性质 L ’ ‘ ’ [集装箱已依其重量从小到大排序，(工1，刀2，…，工，2)是最优装载问题的一个最优解。又设 把㈠[Jf：1}。易知，如果给定的最优装载问题有解，则l≤是≤"。 1) 当是二1时，(J1，工2，…，工f2)是一个满足贪心选择性质的最优解。 1)·当是>1时，取y1二1；yA二0；y／二t／，1<i≤f2，2·乒是，则， ∑wiyi=仞：—吼+∑WiXi≤∑wixi≤c ‘· l’l i二1 i二1 如l，》／2，…，儿)是所给最优装载问题的一个可行解。 }一方面，由∑y／’∑Jf知，(y1，夕2，…，yn)是一个满足贪心选择性质的最优解。所以， I二1 j二1 减问题具有贪心选择性质。 最优子结构性质 ：! ． ：(卸，J2，…，z，1)是最优装载问题的一个满足贪心选择性质的最优解，则易知，刀3；1， ·，J，2)是轮船载重量为c—Wl且待装船集装箱为{2，3，…，ni时相应最优装载问题的一 解。也就是说，最优装载问题具有最优子结构性质。 最优装载问题的贪心选择性质和最优子结构性质，容易证明算法Loading的正确性。 珐Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时 )(，2logn)

9 由于输入的活动以其完成时间的非减序排列，所以 算法greedySelector每次总是选择具有最早完成时间的相 容活动加入集合A中。直观上，按这种方法选择相容活动 为未安排活动留下尽可能多的时间。也就是说，该算法的 贪心选择的意义是使剩余的可安排时间段极大化，以便安 排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按 结束时间的非减序排列，算法只需O(n)的时间安排n个活 动，使最多的活动能相容地使用公共资源。如果所给出的 活动未按非减序排列，可以用O(nlogn)的时间重排。 分两种情况，已排序和未排序 [算法证明] 算法达到最优解. [算法分析] T(n)=O(n) (排序时) T(n)=O(nlogn) (未排序时)

10 最优装载 [问题描述] 输入:(x1,x2,...xn), xi=0,货箱i不装船; xi=1,货箱i装船
算法设计与分析 > 贪心算法 最优装载 [问题描述] 输入:(x1,x2,...xn), xi=0,货箱i不装船; xi=1,货箱i装船 可行解: 满足约束条件 ≤c 的输入 优化函数: 最优解:使优化函数达到最大值的一种输入. [算法思路] 将装船过程划为多步选择，每步装一个货箱，每次从剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。 [例] 设n=8，[w1，…w8]=[100, 200, 50, 90, 150, 50, 20, 80]，c=400。 所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2。货箱7, 3, 6, 8, 4, 1的 总重量为390个单位且已被装载, 剩下的装载能力为10 ,小于任意 货箱.所以得到解[x1,...x8]=[ 1, 0, 1, 1, 0, 1, 1, 1] 先排序然后选最轻，按局部最优选择，c是船可货物量，后面不能放任何箱子

11 Sort(w, t, n) ; //按货箱重量排序/ for (int i = 1; i < = n; i ++) x[i] = 0;
算法设计与分析 > 贪心算法 1、最优装载的贪心算法 template < class Type > void Loading(int x[], Type w[], Type c, int n ) { int *t = new int [n + 1]; Sort(w, t, n) ; //按货箱重量排序/ for (int i = 1; i < = n; i ++) x[i] = 0; for (int i = 1;i<= n && w[t[i]] <= c; i++) x[t[i]] = 1; c-= w[t[i]]; //调整剩余空间 }

12 2、贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3、最优子结构性质 最优装载问题具有最优子结构性质。 算法证明:由最优装载问题的贪心选择性质和最优 子结构性质，容易证明算法loading的正确性。 算法分析:算法loading的主要计算量在于将集装箱 依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。

13 背包问题 (Knapsack Problem)
算法设计与分析 > 贪心算法 背包问题 (Knapsack Problem) [问题描述]设有n个物体和一个背包,物体i的重量为wi ,价值为vi ,背包的容量为C.若将物体i的xi部分(1in, 0xi1)装入背包,则具有价值为vi xi. 目标是找到一个方案,使放入背包的物体总价值最高. [最优化描述] 找一个n元向量(x1,…xn) 0 xi 1 使得 且 其中 C, Wi, vi>0 , 1  i  n 在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉 象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制p 机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个 的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平 点对问题。 最接近点对问题的提法是：给定平面上"个点，找其中的一对点，使得在，2 对中，该点对的距离最小。 严格地说，最接近点对可能多于l对。为了简单起见，这里只限于找其中的— 很容易理解，似乎也不难解决。我们只要将每一点与其他，2—1个点的距离算出， 距离的两个点即可。然而，这样做效率太低，需要O("’)的计算时间。稍后在第九 看到，该问题的计算时间下界为n1ogn。这个下界引导我们去找问题的一个‘ 很自然地我们会想到用分治法来解这个问题。也就是说，将所给的平面上，2个点 2个子集s1和S2：，每个子集中约有n/2个点，然后在每个子集中递归地求其最接进 里，一个关键的问题是如何实现分治法中的合并步骤，即由s1和S2的最接近点对 集合S中的最接近点对。如果组成5的最接近点对的2个点都在J1中或都在S2 易解决。但是，如果这2个点分别在s1和S2，中，则仍需做n2／4次计算和比较才 约 束 条 件 优化函数

14 背包问题实例 考虑下列情况的背包问题 n=3,M=20,(v1,v2,v3)=(25,24,15),
算法设计与分析 > 贪心算法 背包问题实例 考虑下列情况的背包问题 n=3,M=20,(v1,v2,v3)=(25,24,15), (w1,w2,w3)=(18,15,10) 其中的4个可行解是： (x1,x2,x3) ∑wi xi ∑vixi ① (1/2,1/3,1/4) 16.5 24.25 ② (1,2/15,0) 20 28.2 ③ (0,2/3,1) 31 ④ (0,1,1/2) 31.5 M是总重量，v是价值物体i的xi部分

15 算法设计与分析 > 贪心算法 贪心方法的数据选择策略(1) 1、用贪心策略求解背包问题时，首先要选出最优 的度量标准。可以选取目标函数为量度标准，每装入一 件物品就使背包获得最大可能的效益值增量。在这种量 度标准下的贪心方法就是按效益值的非增次序将物品一 件件放到背包中。 如上面的实例所示，可将物品按效益量非增次序排 序： (v1,v2,v3)=(25,24,15)。先装入物品1重量为18，即 x1=1；然后再装物品2，由于约束条为∑wi xi ≤M=20， 所以物品2只能装入重量为2的一小部分，即x2=2/15。 按上述的数据选择策略，装入顺序是按照物品的效 益值从大到小的输入，由刚才的方法可得这种情况下的 总效益值为∑vixi = 25+24*2/15=28.2，显然是一个次优解， 原因是背包容量消耗过快。

16 算法设计与分析 > 贪心算法 贪心方法的数据选择策略(2) 2、若以容量作为量度，可让背包容量尽可能慢地 被消耗。这就要求按物品重量的非降次序来把物品放入 背包，即(w3,w2,w1)=(10,15,18)。 先装入物品3, x3=1, p3x3 =15，再装入重量为10的物 品2， ∑vixi =15+24*10/15=31。 由刚才的方法可得这种情况下的总效益值为31，仍 是一个次优解，原因是容量在漫漫消耗的过程中，效益 值却没有迅速的增加。

17 算法设计与分析 > 贪心算法 贪心方法的数据选择策略(3) 3、采用在效益值的增长速率和容量的消耗速率之间取 得平衡的量度标准。即每一次装入的物品应使它占用的每一 单位容量获得当前最大的单位效益。这就需使物品的装入次 序按vi/wi比值的非增次序来考虑。 这种策略下的量度是已装入物品的累计效益值与所用 容量之比。 (v2/w2 , v3/w3 , v1/w1 )=(24/15,15/10, 25/18) 先装入重量为15的物品2，在装入重量为5的物品3， ∑pixi =24+15*5/10=31.5。此结果为最优解。

18 算法设计与分析 > 贪心算法 [例] n=3,c=20 (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) {x1,x2,x3} {1,2/15,0} { 0,2/3,1} {0,1,1/2} {...} 20 20 20 ... ... 28.2 31.5 31 [算法思路]1).将各物体按单位价值由高到低排序. 2).取价值最高者放入背包. 3).计算背包剩余空间. 4).在剩余物体中取价值最高者放入背包. 若背包剩余容量=0或物体全部装入背包为止

19 排序为主要算法时间,所以 T(n)=O(nlogn)
算法证明:该算法能得到在最优解 算法分析: 排序为主要算法时间,所以 T(n)=O(nlogn) 背包问题中的物体不能分拆,只能整个装入称为0-1背包问题. 用贪心算法能得到0-1背包的最优解吗? 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪 心选择策略，将尽可能多的单位重量价值最高的物品装入 背包。若将这种物品全部装入背包后，背包内的物品总重 量未超过C，则选择单位重量价值次高的物品并尽可能多 地装入背包。依此策略一直地进行下去，直到背包装满为 止。 具体算法可描述如下页： 无法得到，不满足性质

20 void Knapsack(int n,float M,float v[],float w[],float x[]) {
Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; 算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O（nlogn）。 为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

21 对于0-1背包问题，贪心选择之所以不能得到最优解 是因为在这种情况下，它无法保证最终能将背包装满，部 分闲置的背包空间使每公斤背包空间的价值降低了。事实 上，在考虑0-1背包问题时，应比较选择该物品和不选择 该物品所导致的最终方案，然后再作出最好选择。由此就 导出许多互相重叠的子问题。这正是该问题可用动态规划 算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0- 1背包问题。

22 算法设计与分析 > 贪心算法 思考题 找零钱问题：一个小孩买了价值为33美分的糖， 并将1美元的钱交给售货员。售货员希望用数目最少 的硬币找给小孩。假设提供了数目不限的面值为25 美分、10美分、5美分、及1美分的硬币。使用贪心 算法求解最优结果。并证明找零钱问题的贪心算法 总能产生具有最少硬币数的零钱。 先用数目最大

23 算法设计与分析 > 贪心算法 4.5 单源最短路径 问题: 给定带权有向图G=(V,E), 其中每条边的权是一个非负实数.要计算从V的一点v0(源)到所有其他各顶点的最短路长度. 路长指路上各边权之和。 例 题 例 题 算法思路(Dijkstra) :设最短路长已知的终点集合为S,初始时v0S, 其最短路长为0,然后用贪心选择逐步扩充S :每次在V-S中,选择路径长度值最小的一条最短路径的终点x加入S. 构造路长最短的最短路径:设已构造i条最短路径,则下一个加入S的终点u必是V-S中具有最小路径长度的终点, 其长度或者是弧(v0,u), 或者是中间只经过S中的顶点而最后到达顶点u的路径. 常见问题3种:定点到定点,定点到任意点,任意点到任意点. 对S中的每一点,各自扩充一条最短边(终点V-S), 得到下一步所能达到的终点x，则从v到x的当前最短路径或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点x的路径.从中找一条路长最短的终点x加入s. 将问题化为多步决策, 每步求出一条新的最短路径. 新的最短路径: 1地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短 i已知。初始时，S中仅含有源。设2J是G的某一个顶点，我们把从源到以且中间只经过 ；的路称为从源到u的特殊路径，并用数组dist来记录当前每个顶点所对应的最短特殊 ＼Dijkstra算法每次从y—S中取出具有最短特殊路长度的顶点c4，将“添加到S中， [组dist作必要的修改。一旦S包含了所有y中顶点，dist就记录了从源到所有其他顶 y最短路径长度。 stra算法可描述如下，其中输入的带权有向图是G=(y，正)，y二11，2…，，2}，顶点 ：是一个二维数组，cC 2，)[川表示边(2·，了)的权。当(2·，了)务正时，c㈠)[川是一个大数。 乏示当前从源到顶点I，的最短特殊路径长 即按路径长度顺序产生最短路径.

24 已知一个n 结点的有向图G=(V,E)和边的权函数c(e)，求 由G中某指定结点v0到其他各个结点的最短路径。
算法设计与分析 > 贪心算法 已知一个n 结点的有向图G=(V,E)和边的权函数c(e)，求 由G中某指定结点v0到其他各个结点的最短路径。 45 50 10 v4 路径 长度 (1) v0v2 10 (2) v0v2v3 25 (3) v0v2v3v1 45 (4) v0v4 v0 v1 15 10 35 30 20 20 举例图示 v2 v3 v5 15 3

25 产生最短路径的贪心方法 逐条构造这些最短路径，使用迄今已生成的所有路径 长度之和作为一种量度标准。
算法设计与分析 > 贪心算法 产生最短路径的贪心方法 逐条构造这些最短路径，使用迄今已生成的所有路径 长度之和作为一种量度标准。 为了使这一量度达到最小，其单独的每一条路径都必 须具有最小长度。 使用这标准时，假定已构造了i条最短路径，则下面要 构造的路径应该是下一条最短的最小长度路径。 生成从v0到所有其它结点的最短路径的贪心方法就是按 照路径长度的非降次序生成这些路径。

26 产生最短路径的贪心方法 设S表示对其已经生成了最短路径的那些结点(包 括v0)的集合。
算法设计与分析 > 贪心算法 产生最短路径的贪心方法 设S表示对其已经生成了最短路径的那些结点(包 括v0)的集合。 扩张S的过程：对于不在S中的结点w，设DIST(w) 是从v0开始只经过S中的结点而在结点w结束的那 条最短路径的长度，则有： 如果下一条最短路径是到结点u，则这条路径是从v0处开 始而在u处终止，并且只通过那些在S中的结点。 所生成的下一条路径的终点u必定是所有不在S内的结点 中具有最小距离DIST(u)的结点。

27 产生最短路径的贪心方法 选出了结点u并生成了从v0到u的最短路径之后，结点u 就成为S中的一个成员。
算法设计与分析 > 贪心算法 产生最短路径的贪心方法 选出了结点u并生成了从v0到u的最短路径之后，结点u 就成为S中的一个成员。 此时，那些从v0开始，只通过S中的结点并且在S外的结 点w处结束的最短路径可能会减小。 如果长度改变了，则它必定是由一条从v0开始，经过u 然后到w的更短路径所造成的。 其中从v0到u的路径是一条最短路径，从u到w的路径是 边<u,w>，于是这条路径的长度就是：DIST(u)+c(u,w) 要加上已计算的

28 (1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧<vi,vj>
算法设计与分析 > 贪心算法 算法描述： (1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧<vi,vj> 上的权值. 若 <vi, vj>V,则置c[i][j]为 设S为已知最短路径的终点的集合,它的初始状态为空集. 从源点v到图上其余各点vi的当前最短路径长度的初值为： dist[i]=c[v][i] ，viV (2) 选择vj, 使得dist[j]=Min{dist[i] | viV-S} vj就是长度最短的最短路径的终点。令S=SU{j}//更新S (3) 修改从v到集合V-S上任一顶点vk的当前最短路径长度: 如果 dist[j]+c[j][k]< dist[k] 则修改 dist[K]= dist[j]+c[j][k] //更新dist和prev (4) 重复操作(2),(3)共n-1次. 常见问题3种:定点到定点,定点到任意点,任意点到任意点. 1地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短 i已知。初始时，S中仅含有源。设2J是G的某一个顶点，我们把从源到以且中间只经过 ；的路称为从源到u的特殊路径，并用数组dist来记录当前每个顶点所对应的最短特殊 ＼Dijkstra算法每次从y—S中取出具有最短特殊路长度的顶点c4，将“添加到S中， [组dist作必要的修改。一旦S包含了所有y中顶点，dist就记录了从源到所有其他顶 y最短路径长度。 stra算法可描述如下，其中输入的带权有向图是G=(y，正)，y二11，2…，，2}，顶点 ：是一个二维数组，cC 2，)[川表示边(2·，了)的权。当(2·，了)务正时，c㈠)[川是一个大数。 乏示当前从源到顶点I，的最短特殊路径长 即按路径长度顺序产生最短路径.

29 1) v1  v2: 10 2) v1  v3: 50 3) v1  v4: 30 4) v1  v5: 60
算法设计与分析 > 贪心算法 >单源最短路径 例 题 1) v1  v2: 10 2) v1  v3: 50 3) v1  v4: 30 4) v1  v5: 60 1到5，加入4之后由100变成90，1地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短 i已知。初始时，S中仅含有源。设2J是G的某一个顶点，我们把从源到以且中间只经过 ；的路称为从源到u的特殊路径，并用数组dist来记录当前每个顶点所对应的最短特殊 ＼Dijkstra算法每次从y—S中取出具有最短特殊路长度的顶点c4，将“添加到S中， [组dist作必要的修改。一旦S包含了所有y中顶点，dist就记录了从源到所有其他顶 y最短路径长度。 stra算法可描述如下，其中输入的带权有向图是G=(y，正)，y二11，2…，，2}，顶点 ：是一个二维数组，cC 2，)[川表示边(2·，了)的权。当(2·，了)务正时，c㈠)[川是一个大数。 乏示当前从源到顶点I，的最短特殊路径长 即按路径长度顺序产生最短路径.

30 for (int i=1;i<=n; i++){ dist[i]=c[v][i]； s[i]=false；
算法设计与分析 > 贪心算法 单源最短路径问题的Dijkstra算法 voidDijkstra(int n, int v,Type dist[], int prev[], Type **c) { bool s[maxint]； 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)){ Type newdist=dist[u)+c[u][j]; if (newdist<dist[j]){ dist[]]=newdist； prev[j]=u; }}}} 迪科斯彻算法 在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉 象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制p 机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个 的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平 点对问题。 最接近点对问题的提法是：给定平面上"个点，找其中的一对点，使得在，2 对中，该点对的距离最小。 严格地说，最接近点对可能多于l对。为了简单起见，这里只限于找其中的— 很容易理解，似乎也不难解决。我们只要将每一点与其他，2—1个点的距离算出， 距离的两个点即可。然而，这样做效率太低，需要O("’)的计算时间。稍后在第九 看到，该问题的计算时间下界为n1ogn。这个下界引导我们去找问题的一个‘ 很自然地我们会想到用分治法来解这个问题。也就是说，将所给的平面上，2个点 2个子集s1和S2：，每个子集中约有n/2个点，然后在每个子集中递归地求其最接进 里，一个关键的问题是如何实现分治法中的合并步骤，即由s1和S2的最接近点对 集合S中的最接近点对。如果组成5的最接近点对的2个点都在J1中或都在S2 易解决。但是，如果这2个点分别在s1和S2，中，则仍需做n2／4次计算和比较才 分析:用带权邻接矩阵表示有n个顶点和e条边的带权有向图,主循环体需要O(n)时间,循环需要执行n-1次,所以完成循环需要O(n2).

31 算法实例 求下图中v1到其余各结点的最短路径 v2 70 20 25 50 50 50 v6 v7 v1 v3 25 30 10 40 70
算法设计与分析 > 贪心算法 算法实例 求下图中v1到其余各结点的最短路径 v2 70 20 25 50 50 50 v6 v7 v1 v3 25 30 10 40 70 v4 55 v5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

32 算法实例 SHORTEST-PATHS执行踪迹 ∞ 迭代 选取 结点 S DIST (1) (2) (3) (4) (5) (6) (7)
算法设计与分析 > 贪心算法 算法实例 SHORTEST-PATHS执行踪迹 迭代 选取 结点 S DIST (1) (2) (3) (4) (5) (6) (7) 置初值 -- 1 20 50 30 ∞ 2 1,2 45 90 3 1,2,4 85 4 1,2,4,3 70 5 1,2,4,3,5 80 140 6 1,2,4,3,5,6 130 课堂？

33 所谓“贪心算法”是指： 在对问题求解时，总是作出在当前看来是最好 的选择。也就是说，不从整体上加以考虑，它 所作出的仅仅是在某种意义上的局部最优解 （是否是全局最优，需要证明）。 谈恋爱，所有的选择都是当时最好的选择 2019/5/18

34 特别说明： 若要用贪心算法求解某问题的整体最优解，必须 首先证明贪心思想在该问题的应用结果就是最优 解！！ 2019/5/18
可以通过实验证明，1、贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2、最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征 3、贪心算法与动态规划算法的差异 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2019/5/18

35 三、HDOJ_1050 Moving Tables 2019/5/18
沿着走廊，北面和南面各有200个房间。 最近公司制定了改革体系的计划。 改革包括在房间之间移动大量桌子。 由于走廊狭窄，所有桌子都很大，只有一张桌子可以穿过走廊。 需要制定一些计划来提高移动效率。 经理想出了以下计划：将桌子从一个房间移到另一个房间可以在10分钟内完成。 当将桌子从房间i移动到房间j时，使用房间i前面和房间j前面之间的走廊部分。 因此，在每10分钟内，两个不共享同一部分走廊的房间将会同时移动。 为了清楚说明经理说明了同时移动的可能情况和不可能情况。 对于每个房间，最多一张桌子将被移入或移出。 现在，经理寻找一种方法来最小化移动所有表的时间。 你的工作是写一个程序来解决经理的问题。 2019/5/18

36 三、HDOJ_1050 Moving Tables Sample Output Sample Input 10 20 30
Sample Input Input The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above. Output The output should contain the minimum time in minutes to complete the moving, one per line. 输入输入包含T测试用例。 测试用例的数量）（T在输入的第一行给出，每个测试用例都以包含整数N的行开始，1 <= N <= 200，表示要移动的表的数量。 以下N行包含两个正整数s和t，表示一个表从房间号s移动到房间号t（每个房间号在N行中最多出现一次）从第N + 3行开始， 剩下的测试用例与上述相同。 产量输出应包含完成移动的最短时间（以分钟为单位），每行一个。 2019/5/18

37 算法分析： 1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？ 3、如果每趟处理都包含最大重叠，处理后的效果 是什么？
4、得出什么结论？ 最多10，overlap,必须等待，所以导致时间累加，贪心算法，先处理较小问题得到较小问题的最优解 2019/5/18

38 附:参考源码(HDOJ-1050) #include <iostream> if(s>d)
using namespace std; int main() { int t,i,j,N,P[200]; int s,d,temp,k,min; cin>>t; for(i=0;i<t;i++) { for(j=0;j<200;j++) P[j]=0; cin>>N; for(j=0;j<N;j++) cin>>s>>d; s=(s-1)/2; d=(d-1)/2; if(s>d) { temp=s; s=d; d=temp; } for(k=s;k<=d;k++) P[k]++; } min=-1; for(j=0;j<200;j++) if(P[j]>min) min=P[j]; cout<<min*10<<endl; return 0; 折半查找看有无overlap, p[k]相当于酸overlap次数 2019/5/18

39 贪心算法的基本步骤 1、从问题的某个初始解出发。
2、采用循环语句，当可以向求解目标前进一 步时，就根据局部最优策略，得到一个部 分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终 解。 2019/5/18