当前位置：文档之家 › 贪心算法的图文讲解

贪心算法的图文讲解

  • 格式：ppt
  • 大小：337.00 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

贪心算法精品PPT课件

贪心算法精品PPT课件
– 从全局看来，运用贪心策略解决的问题在 程序的运行过程中无回溯过程
教学进度
背包问题
计算机科学与工程系
• 给定n种物品和一个背包。物品i的重量是 Wi，其价值为Vi，背包的容量为C。在选 择物品i装入背包时，可以选择物品i的一部 分，而不一定要全部装入背包，1≤i≤n。 应如何选择装入背包的物品，使得装入背包 中物品的总价值最大?
教学进度
计算机科学与工程系
• 贪心算法并不总能求得问题的整体最优 解。但对于活动安排问题，贪心算法 GreedySelector却总能求得的整体最 优解，即它最终所确定的相容活动集合 A的规模最大。
教学进度
贪心算法的基本要素
• 最优子结构性质 • 贪心选择性质
计算机科学与工程系
教学进度
最优子结构性质
教学进度
计算机科学与工程系
• 怎样对这n个活动进行安排才能 令最多的活动可以使用资源？
教学进度
计算机科学与工程系
• 活动安排问题也就是要在所给 的活动集合中选出最大的相容 活动子集合
教学进度
计算机科学与工程系
教学进度
计算机科学与工程系
• 思路：按照结束时间递增序列将活动排 序，使得f1<=f2<=…<=fn
• void GreedySelector(int n, Type s[], Type f[], bool A[])
•{
•
A[1]=true;
•
int j=1;
•
for (int i=2;i<=n;i++) {
各活动的起始时间和结 束时间存储于数组s和f 中且按结束时间的非减 序排列
•
if (s[i]>=f[j]) { A[i]=true; j=i; }

[数学]152 贪心算法ppt课件

[数学]152 贪心算法ppt课件
S { 0，1，2，3，4，5}
35 53
Prim算法实现 int s[N]表示集合S，1表示曾经参与，否那么0
，初始S[0] = 1; lowcost[N]记录每一个顶点到集合s的最短边长
度,初始lowcost[0, ..., N-1] = c[0][0, ..., N-1] lowcost[N] ={0,4,INT_MAX, 5, INT_MAX,
就根据部分最优战略，得到一个部分解，减少 问题的范围或规模 选择最早终了的事件； 将一切的部分解综合列；
13 53
二：区间覆盖问题
问题的描画
用整数i来表示x轴上坐标为[i - 1, i]的区间(长度 为1)。给出M(1 <= M <= 200)个不同的整数， 表示M个这样的区间。
2 53
背包问题： 给定n种物品和一个背包，设Wi为物体i的分量
，Vi为期价值，C为背包的承分量。要求在背 包的承分量的限制下，进能够使背包中物品 的价值最大。 贪婪战略一：每次选择价值最大的物品。 贪婪战略二：每次选择分量最小的物品。 贪婪战略三：每次选择Vi/Wi最大的物品
3 53
什么是贪婪法？ “鼠目寸光〞的方法？每次选择面值最大的硬币
10 53
#include <iostream> using namespace std; const int N = 12; void OutputResult(int select[], int N) //输出结果函数 {
for(int i = 0; i < N; i++) {
if(select[i] == 1) //当标志为1时该事件被选中 cout << i << endl; } }

贪心算法PPT学习课件

贪心算法PPT学习课件

5
例8.2 一个买糖的孩子用1元钱买了不到1元钱的糖,售货 员找硬币时希望用最少个数的硬币。 售货员每增加一个硬币,使用的贪心规则是: 每次希望增加尽可能多的币值,又不能超出总数。 例如要找66c(分)。
● 假设硬币面值分别为：25c, 10c, 5c, 1c。
● 假设硬币面值分别为：20c, 16c, 10c, 1c。
3. MAKESET({v})
4. End for
5. T={}
6. While |T|<n-1
7. 令(x,y)为E中的下一条边
8. If FIND(x)≠FIND(y) then
heyichao@
26
9.
将(x,y)加入T
10.
UNION(x,y)
11. End if
12. End while
● 函数H-1(w)返回w在H中的位置 (注意堆由一个 数组H(1…n)来实现)。
heyichao@
18
● 运行时间主要取决于堆运算，这里共有n-1 个DELETEMIN运算，n-1个INSERT运算，最 多m-n+1个SIFTUP运算，每个堆运算用O(logn) 时间，得到总共需要O(mlogn)时间。
1. 对G的边以非降序权重排列。
2. 对于排序表中的每条边，如果现在把它放入T 不会形成回路的话，则把它加入到生成树T中；否 则将它丢弃。
见例8.3
heyichao@
24
Kruskal算法的实现
为有效地实现此算法，我们需要某种机制来检 测加入边后是否构成回路。为此需要确定一种数 据结构，让它在算法的每个时刻来表示森林，并 且在向T中添加边时动态检测是否有回路生成。
7
● 假设V={1,2,…,n}并且s=1。这个问题可以用一 种称为Dijkstra算法的贪心技术来解决。初始时， 将顶点分为两个集合X={1}和Y={2,3,…,n}。X包 含的顶点集合：从源点到这些顶点的距离已经确 定。

简单的贪心算法pptPPT课件

简单的贪心算法pptPPT课件

问题的整体最优解 中包含着它子问题 的最优解
【常见应用】背包问题,最小生成树,最短路径,作业调度等等 【算法优点】求解速度快,时间复杂性有较低的阶. 【算法缺点】需证明是最优解.
02.08.2021
编辑版pppt
9
‫ﻻ‬常见应用
1、活动安排问题
【问题陈述】设有n个活动E={1,2,…,n}要使用同一资源,同一时间内 只允许一个活动使用该资源. 设活动i的起止时间区间[si, fi) ,如果选
02.08.2021
编辑版pppt
10
‫ﻻ‬常见应用
活动安排问题贪心算法： 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; } }
02.08.2021
编辑版pppt
11
‫ﻻ‬常见应用
2、多机调度问题
多机调度问题要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。
约定，每个作业均可在任何一台机器上加工处理，但未完 工前不允许中断处理。作业不能拆分成更小的子作业。
体上考虑并不一定是最优解；
（2）贪心算法只能用来求某些最大或最小解的 问题；
（3）贪心算法只能确定某些问题的可行性范围
。
因此，贪心算法具有局限性，并不是总能得到最优
解。 02.08.2021
编辑版pppt
16
谢谢观 看！！！
02.08.2021

贪心算法090420

贪心算法090420
（证明：略）
2019/11/2
10
思考：
请谈谈自己的解题思路
2019/11/2
11
思考题
2037 今年暑假不AC
2019/11/2
12
二、区间覆盖问题
用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并 给出M(1=<M=<200)个不同的整数，表示M个这样的区间。 现在让你画几条线段覆盖住所有的区间，条件是：每条 线段可以任意长，但是要求所画线段之和最小，并且线 段的数目不超过N(1=<N=<50)。 例如：M=5个整数1、3、4、8和11表示区间，要求所用线 段不超过N=3条 0 1 2 3 4 5 6 7 8 9 10 11
if(P[j]>min) min=P[j];
cout<<min*10<<endl; } return 0; }
2019/11/2
17
贪心算法的基本步骤
1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一
步时，就根据局部最优策略，得到一个部 分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终 解。
Sample Input
Sample Output
3 4 10 20 30 40
10 20 30
50 60
70 80
2
13
2 200
3
10 100
20 80
30 50
2019/11/2
15
算法分析：
1、如果没有交叉，总时间应该是多少？ 2、影响搬运时间的因素是什么？ 3、如果每趟处理都包含最大重叠，处理
Thank You ~
2019/11/2

贪心算法PPT课件

贪心算法PPT课件
且有||B’-{k}||>||B-{1}||，这与假设2°矛盾。 ▌
安排方案
f1
B
安排方案
fk
B’
…… 共j个活动
可能 相同 不存在
……
可能
如果 B’包 含这 个活, 则B 一定 包含
9
(2) 时间复杂度分析： 因为排序过程可以在O(nlogn)时间内完成，而求最优活动子 集的过程只需O(n)次比较，因此这个算法的时间复杂度为 O(nlogn)。 (3) 贪心策略设计算法的一般特点
·选Si最小的，这样可以增大场地的利用率； ·选fi最小的，使得下一个活动可以更早开始。
由于活动的占用时间长度没有限制，因此后一选择更合理。
6
为了在每一次选择时取当前可以安排的活动中最早结束的活动，应首先把 n项活动按结束时间的先后进行升序排序。即，使f1≤f2≤…≤fn，然后在Si值 不小于当前时刻的活动中取fi值最小者。 算法：
·算法的设计比较简单； ·算法一般比较快速； ·算法的正确性一般不明显，需要论证；如果正确性不能保 证，那么它往往可以得到近似最优解。
10
5.2 背包(Knapsack)问题
1. 问题描述
已知：n个(应为n种)物体{1,2,…,n}与一个背包。物体i的重量 （或体积）为Wi>0，价值为Pi>0(i=1,2,…,n)，背包容量为 M>0。
计算机算法 ——设计与分析导论
刘璟
1
Chapter 5. 贪心（Greedy）技术
❖ 5.1 贪心策略的思想 ❖ 5.2 背包(Knapsack)问题 ❖ 5.3 Huffman编码 ❖ 5.4 多机调度问题的近似解法 ❖ 5.5 单源最短路径的Dijkstra算法

第五讲 贪心算法PPT课件

第五讲 贪心算法PPT课件

• Begin
•
S:=S+P[I]; M:=M-W[I];
• End
• Else {否则取一部分}
• Begin
•
S:=S+M*(P[I]/W[I]); Break;
• End;
• End;
11
• Procedure Out; {输出} • Begin • Assign(Output,Fout); Rewrite(Output); • Writeln(S:0:0); • Close(Output); • End; • Begin {主程序} • Init; • Work; • Out; • End.
23
• 分析：需要考虑如下问题： • (1)出发前汽车的油箱是空的，故汽车必须在起
点（1号站）处加油。加多少油？ • (2)汽车行程到第几站开始加油，加多少油？ • 可以看出，原问题需要解决的是在哪些油站加油
• (2) 原问题的最优解包含子问题的最优解，即问题具有最优 子结构的性质。在背包问题中，第一次选择单位质量最大的货 物，它是第一个子问题的最优解，第二次选择剩下的货物中单 位重量价值最大的货物，同样是第二个子问题的最优解，依次 类推。
• 其次，如何选择一个贪心标准？正确的贪心标准可以得到问 题的最优解，在确定采用贪心策略解决问题时，不能随意的判 断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准 所迷惑。在得出贪心标准之后应给予严格的数学证明。
二
请在这里输入您的主要 叙述内容
三 请在这里输入您的主要叙述内容
2
一、引入：
• 若在求解一个问题时，能根据每次所得 到的局部最优解，推导出全局最优或最优 目标。那么，我们可以根据这个策略，每 次得到局部最优解答，逐步而推导出问题， 这种策略称为贪心法。

算法-第4章贪心法-PPT课件

算法-第4章贪心法-PPT课件
f i A
i , j A , i j , f ( i ) t f ( j ) or f ( j ) t f ( i ) i j
12
实例
A={1, 2, 3, 4, 5}, T=<5, 8, 4, 10, 3>, D=<10, 12, 15, 11, 20> 调度1： f1(1)=0, f1(2)=5, f1(3)=13, f1(4)=17, f1(5)=27 各任务延迟：0, 1, 2, 16, 10; 最大延迟：16 5 1 2 13 3 17 4 27 5 30
18
i j
f2(j)=s f2(i)=s+tj
delay(f’,i)=s＋tj+ti－ di <delya(f,j)r delay(f, j)＝s+ti+tj－dj
4.3 得不到最优解的处理方法
讨论对于哪些输入贪心法能得到最优解：输入条件 讨论贪心法的解最坏情况下与最优解的误差（见第8章）
例4.4 找零钱问题 设有 n 种零钱， 重量分别为w1, w2, ... , wn, 价值分别为 v1=1, v2, ... , vn. 需要付的总钱数是 Y .不妨设币值和钱数都为 正整数. 问：如何付钱使得所付钱的总重最轻?
设计思想：按完成时间从早到晚安排任务，没有空闲
15
交换论证：正确性证明
算法的解的性质： (1) 没有空闲时间, 没有逆序. (2) 逆序 (i, j): f(i) < f(j) 且 di > dj 引理4.1 所有没有逆序、没有空闲时间的调度具有相同的 最大延迟. 证: 设 f 没有逆序，在 f 中具有相同完成时间的客户i1, i2, … , ik 必被连续安排. 在这k个客户中最大延迟是最后一个客 户，被延迟的时间是 k
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

总结
• 在对问题求解时，会选择当前看起来最有希望成功的边（任务） 。一旦做出决定，它就不会再重新考虑，也不会关心后面会引发 什么情况。也就是说，不从整体最优上加以考虑，它所做出的是 在某种意义上的局部最优解。 • 贪心算法是一种能够得到某种度量意义下的最优解的分级处理方 法，通过一系列的选择来得到一个问题的解，而它所做的每一次 选择都是当前状态下某种意义的最好选择，即贪心选择。即希望 通过问题的局部最优解来求出整个问题的最优解。这种策略是一 种很简洁的方法，对许多问题它能产生整体最优解，但不能保证 总是有效，因为它不是对所有问题都能得到整体最优解，只能说 其解必然是最优解的很好近似值
对于这个问题我们有以下几种情况：设加油次数为k，每个加油 站间距离为a[i]；i=0，1，2，3……n （1）始点到终点的距离小于N，则加油次数k=0； （2）始点到终点的距离大于N时： A 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n ； B 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点； C 加油站间的距离相等，即ａ[i]=a[j]=L<N，则加油次数 k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)； D 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过贪心 算法求解。
•
• • 贪心的基本思想
• 用局部解构造全局解，即从问题的某一个初始解逐步逼 近给定的目标，以尽可能快地求得更好的解。当某个算 法中的某一步不能再继续前进时，算法停止。贪心算法 思想的本质就是分处理 出一个最好的方案。 • 利用贪心策略解题，需要解决两个问题： • （1）该题是否适合于用贪心策略求解； • （2）如何选择贪心标准，以得到问题的最优/较优解。
正确性证明
该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、 Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那 • 么在Ａ加油一定不能到达终点，因为 m+N<n+N，即在B点加油可行驶 的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在 B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就 会选择距离加满油得点远一些的加油站去加油，因此，加油次数最 少满足贪心选择性质由于（b[1]，b[2]，……b[n]）是这段路程加 油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个 加油站加油时，b[1]=1，则（b[2]，b[3]，……b[n]）是从a[2]到 a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2]， a[3]，……a[n]）的最优解，即每次汽车中剩下的油不能在行驶到 下一个加油站时我们才在这个加油站加一次油，每个过程从加油开 始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同 的条件，每个过程都是相同且独立，也就是说加油次数最少具有最 优子结构性质。
最优子结构性质
• 当一个问题的最优解包含其子问题的最优解时，称此问题具有 最优子结构性质。运用贪心策略在每一次转化时都取得了最优 解。问题的最优子结构性质是该问题可用贪心算法或动态规划 算法求解的关键特征。贪心算法的每一次操作都对结果产生直 接影响，而动态规划则不是。贪心算法对每个子问题的解决方 案都做出选择，不能回退；动态规划则会根据以前的选择结果 对当前进行选择，有回退功能。动态规划主要运用于二维或三 维问题，而贪心一般是一维问题。
• 贪心算法的特点
• 贪心算法最大的特点就是快，但同时存在两大难点： • （1）如何贪心 • 具有应当采用贪心算法的问题，当“贪心序列”中的每项互 异且当问题没有重叠性时，看起来总能通过贪心算法取得（ 近似）最优解的。当一个问题具有多个最优解时，贪心算法 并不能求出所有最优解。一般单纯的贪心算法是顺序处理问 题的，而且每个结果是可以在处理完一个数据后即时输出的 。 • （2）贪心的正确性 • 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为 并不是每次局部最优解都会与整体最优解之间有联系，往往 靠贪心算法生成的解不是最优解。
• 贪心算法策略
• 由于汽车是由始向终点方向开的，我们最大的麻烦就是不知 道在哪个加油站加油可以使我们既可以到达终点又可以使我 们加油次数最少。（提出问题） • 提出问题是解决的开始。为了着手解决遇到的困难，取得最 优方案。我们可以假设不到万不得已我们不加油，即除非我 们油箱里的油不足以开到下一个加油站，我们才加一次油。 在局部找到一个最优的解。每加一次油我们可以看作是一个 新的起点，用相同的递归方法进行下去。最终将各个阶段的 最优解合并为原问题的解得到我们原问题的求解。
•
在动态规划算法中，每步所做的选择往往依赖于相关子问 题的解。因而只有在解出相关子问题后，才能做出选择。 而在贪心算法中，仅在当前状态下做出最好选择，即局部 最优选择。然后再去解做出这个选择后产生的相应的子问 题。贪心算法所做的贪心选择可以依赖于以往所做过的选 择，但决不依赖于将来所做的选择，也不依赖于子问题的 解。正是由于这种差别，动态规划算法通常以自底向上的 方式解各子问题，而贪心算法则通常以自顶向下的方式进 行，以迭代的方式做出相继的贪心选择，每做一次贪心选 择就将所求问题简化为规模更小的子问题。
智能信息处理 -----贪心算法
贪心算法的定义
贪心算法的基本思想 贪心算法的实现思路 贪心算法的基本要素
贪心算法的特点
贪心算法存在的问题
• 贪心算法
• （又称贪婪算法）可以简单描述为：对一组数据进行排序， 找出最小值，进行处理，再找出最小值，再处理，也就是说 贪心算法是一种依据某种贪心标准，从问题的初始状态出发 ，在每一步选择中都直接去求每一步的最优解，最终通过若 干次的贪心选择得出整个问题的最优解的算法 。 贪心算法是一种能够得到某种度量意义下的最优解的分级处 理方法，通过一系列的选择来得到一个问题的解，而它所做 的每一次选择都是当前状态下某种意义的最好或最优的选择 ，即贪心选择，从而得到结果是最好或最优的算法。
贪心算法的实现思路
应用同一规则F，将原问题变为一个相似的、但规模更小的 子问题； 从问题的某一初始解出发： while 能朝给定总目标前进一步 Do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。
贪心算法的基本要素
• 贪心选择性质
• 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列 局部最优的选择，即贪心选择来达到。对于一个具体问题，要 确定它是否具有贪心选择性质，必须证明每一步所做的贪心选 择最终导致问题的整体最优解。首先考察问题的一个整体最优 解，并证明可修改这个最优解，使其以贪心选择开始。做了贪 心选择后，原问题简化为规模更小的类似子问题。然后，用数 学归纳法证明，通过每一步做贪心选择，最终可得到问题的整 体最优解。其中，证明贪心选择后的问题简化为规模更小的类 似子问题的关键在于利用该问题的最优子结构性质。（先做选 择，再解问题的自顶向下的方式）
贪心算法存在的问题
不能保证求得的最后解是最佳的。由于贪心策略总是采用从 局部看来是最优的选择，因此并不从整体上加以考虑； 贪心算法只能用来求某些最大或最小解的问题；
贪心算法只能确定某些问题的可行性范围。
汽车加油问题
• 问题的提出 • 一辆汽车加满油后，可行使N千米。旅途中有若干个加油站 。若要使沿途加油次数最少，设计一个有效算法，对于给定 的N和k个加油站位置，指出应在哪些加油站停靠加油才能使 加油次数最少。 • 编码分析 • 把两加油站的距离放在数组中，a[1..k]表示从起始位置开始 跑，经过k个加油站，a[i]表示第i-1个加油站到第i个加油站的 距离。汽车在运行的过程中如果能跑到下一个站则不加油， 否则要加油。