算法设计与分析W8-贪心算法

VIP免费

2025-01-13 0 0 1.87MB 95 页 5.9玖币

侵权投诉

贪心算法

算法比较

nDivide-and-conquer

（分治策略）

Break up a problem into sub-problems, solve each sub-

problem independently, and combine solution to sub-

problems to form solution to original problem.

nDynamic programming

（动态规划）

Break up a problem into a series of overlapping sub-

problems, and build up solutions to larger and larger

sub-problems.

nGreedy

（贪心）

Build up a solution incrementally, myopically

optimizing some local criterion.

贪心策略

nA “greedy algorithm” is a “non-backtracking

algorithm in which irrevocable decisions of global

significance are made on the basis of local

information”.

----G. B. McMahon

贪心策略

所做的每一步选择都必须满足：

可行的：必须满足问题的约束

局部最优：是当前步骤中所有可行性选择中最佳的局

部选择

不可取消：选择一旦做出，在算法的后面步骤中就无

法改变了

nA “greedy algorithm” is a “non-backtracking

algorithm in which irrevocable decisions of global

significance are made on the basis of local

information”.

----G. B. McMahon

贪心策略

贪心算法的特点：

容易设计

容易分析运行时间

难于证明正确性

精确算法

近似算法

nA “greedy algorithm” is a “non-backtracking

algorithm in which irrevocable decisions of global

significance are made on the basis of local

information”.

----G.B.McMahon

贪心算法举例

部分背包问题

赫夫曼编码问题（

Huffman

算法）

最短路径问题（

Dijkstra

算法）

最小生成树问题

pKruskal

算法

pPrim

算法

区间调度问题（活动选择问题）

区间划分问题

最小延迟调度问题

主要内容

贪心算法举例

区间调度问题（活动选择问题）

•

单资源多请求

•

每个请求有开始时间和完成时间

•

满足最大数目的请求

区间划分问题

•

多资源多请求

•

用尽可能少的资源满足所有请求

最小延迟调度问题

•

单资源多请求

•

每个请求有截止时间和处理时间，开始时间不固定

•

最小化最大延迟

贪心算法的理论基础

——

拟阵

贪心算法举例

区间调度问题（活动选择问题）

单资源多请求

每个请求有开始时间和完成时间

满足最大数目的请求

区间划分问题

多资源多请求

用尽可能少的资源满足所有请求

最小延迟调度问题

单资源多请求

每个请求有截止时间和处理时间，开始时间不固定

最小化最大延迟

贪心算法举例

区间调度问题（活动选择问题）

单资源多请求

每个请求有开始时间和完成时间

满足最大数目的请求

区间划分问题

多资源多请求

用尽可能少的资源满足所有请求

最小延迟调度问题

单资源多请求

每个请求有截止时间和处理时间，开始时间不固定

最小化最大延迟

区间调度（

Interval scheduling

）问题

输入

pS ={1, 2, ... , n}

为

项工作的集合，

si, fi

分别为

第

项工作的开始和结束时间

输出

最大的两两相容的工作集

其中，工作

与

相容

⇔

si≥ fj

或

sj≥ fi

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

贪心算法算法比较nDivide-and-conquer（分治策略）Breakupaproblemintosub-problems,solveeachsub-problemindependently,andcombinesolutiontosub-problemstoformsolutiontooriginalproblem.nDynamicprogramming（动态规划）Breakupaproblemintoaseriesofoverlappingsub-problems,andbuildupsolutionstolargerandlargersub-problems.nGreedy（贪心）...

展开>> 收起<<

算法设计与分析W8-贪心算法.pdf

共95页,预览19页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W8-贪心算法

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: