什么网站可以做免费广告,html网页设计作业代码,企业建网站得多少钱,招聘58同城找工作公元2020年5月5日#xff0c;距离算法考试仅剩4天。一、知识归纳1.设计思想只根据当前已有的信息就做出选择#xff0c;而且一旦做出了选择#xff0c;将来无论如何都不能更改不从整体最优考虑#xff0c;所做的选择只是在某种意义上的局部最优这种选择并不总能获得整体最优…公元2020年5月5日距离算法考试仅剩4天。一、知识归纳1.设计思想只根据当前已有的信息就做出选择而且一旦做出了选择将来无论如何都不能更改不从整体最优考虑所做的选择只是在某种意义上的局部最优这种选择并不总能获得整体最优解Optimal Solution但通常能获得近似最优解Near-Optimal Solution动态规划法通常以自底向上的方式求解各个子问题。贪心法则通常以自顶向下的方式做出一系列的贪心选择。2.示例【找钱问题】假设有面值为5元、2元、1元、5角、2角、1角的货币需要找给顾客4元6角现金使付出的货币的数量最少。【思路】首先选出1张面值不超过4元6角的最大面值的货币即2元再选出1张面值不超过2元6角的最大面值的货币即2元再选出1张面值不超过6角的最大面值的货币即5角再选出1张面值不超过1角的最大面值的货币即1角总共付出4张货币。在付款问题每一步的贪心选择中在不超过应付款金额的条件下只选择面值最大的货币而不去考虑在后面看来这种选择是否合理而且它还不会改变决定一旦选出了一张货币就永远选定。贪心选择策略是尽可能使付出的货币最快地满足支付要求其目的是使付出的货币张数最慢地增加3.基本要素(1) 最优量度标准正确的贪心策略贪心选择性质贪心法求解问题的核心问题根据该量度标准实行多步决策进行求解在该量度意义下每步的贪心选择是局部最优的得到全局最优解(2) 求解的问题有最优子结构性质(最优性原理)一个问题的最优解包含其子问题的最优解注贪心算法的基本要素是贪心选择性质和最优子结构性质。4.求解过程(1) 分解 将原问题分解为若干相互独立的阶段(2) 求解 对于每个阶段求局部最优解即根据贪心策略进行贪心选择在每个阶段选择一旦做出就不可更改。(3) 合并 将各个阶段的解合并为原问题的一个可行解。5.相关概念(1) 候选解集合C问题的可能解问题的最终解均取自于该候选集合(2) 解集合S随着贪心选择的进行不断扩展直到构成一个满足问题的完整解(3) 解判定函数solution检查解集合S是否构成问题的完整解(4) 选择函数select贪心策略这是贪心法的关键指出哪个候选对象最有希望构成问题的解通常和目标函数有关(5) 可行解判定函数feasible检查解集合中加入一个候选对象是否可行即解集合扩展后是否满足约束条件6.贪心法的一般过程Greedy二、组合问题中的贪心法背包问题(物品可切割)多机调度问题活动安排问题1.背包问题【问题表述】给定n种物品和一个容量为C的背包物品i的重量是wi其价值为vi设xi表示物品i装入背包的情况背包问题是如何选择装入背包的物品使得装入背包中物品的总价值最大?【建立模型】【贪心策略】贪心策略一价值最大优先因为这可以尽可能快地增加背包的总价值。但是虽然每一步选择获得了背包价值的极大增长但背包容量却可能消耗得太快使得装入背包的物品个数减少从而不能保证目标函数达到最大。贪心策略二重量最轻优先因为这可以装入尽可能多的物品从而增加背包的总价值。但是虽然每一步选择使背包的容量消耗的慢了但背包的价值却没能保证迅速增长从而不能保证目标函数达到最大。贪心策略三单位重量价值最大优先在背包价值增长和背包容量消耗两者之间寻找平衡。例如有3个物品其重量分别是{20, 30, 10}价值分别为{60, 120, 50}背包的容量为50应用三种贪心策略装入背包的物品和获得的价值如图所示。应用第三种贪心策略每次从物品集合中选择单位重量价值最大的物品如果其重量小于背包容量就可以把它装入并将背包容量减去该物品的重量然后我们就面临了一个最优子问题——它同样是背包问题只不过背包容量减少了物品集合减少了。因此背包问题具有最优子结构性质。【算法描述】设背包容量为C共有n个物品物品重量存放在数组w[n]中价值存放在数组v[n]中问题的解存放在数组x[n]中。 1改变数组w和v的排列顺序使其按单位重量价值v[i]/w[i]降序排列
2将数组x[1:n]初始化为0 //初始化解向量
3i1;
4循环直到(w[i]C)4.1 x[i]1; //将第i个物品放入背包4.2 CC-w[i];4.3 i;
5. x[i]C/w[i];
void Knapsack(int n,float M,float v[],float w[],float x[])
{Sort(n,v,w);int i;for (i1;in;i) x[i]0;float cM;for (i1;in;i) {if (w[i]c) break;x[i]1;c - w[i];}if (in) x[i]c/w[i];
}【算法时间复杂度分析】该算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此其时间复杂性为O(nlog2n)。注贪心算法不能解决0/1背包问题可通过动态规划法解决。三、图问题中的贪心法单源最短路径问题 - Dijkstra算法TSP问题 最小生成树问题 - Prim算法 - Kruskal算法图着色问题1.最小代价生成树问题【问题表述】设G(VE)是一个无向连通图生成树上各边的权值之和称为该生成树的代价在G的所有生成树中代价最小的生成树称为最小生成树Minimal Spanning Trees。 【贪心策略】①最近顶点策略任选一个顶点并以此建立起生成树每一步的贪心选择是简单地把不在生成树中的最近顶点添加到生成树中。②最短边策略设G (V,E)是一个无向连通网令T (V,TE)是G的最小生成树。从TE{}开始每一次贪心选择都是在边集E中选取最短边(u,v)如果边(u, v)加入集合TE中不产生回路则将边(u,v)加入边集TE中并将它在集合E中删去。最近顶点策略—Prim算法使生成树以一种自然的方式生长从任意顶点开始每一步为这棵树添加一个分枝直到生成树中包含全部顶点【算法描述】设图G中顶点的编号为0n-1Prim算法1. 初始化两个辅助数组lowcost和adjvex2. U{u0}; 输出顶点u0; //将顶点u0加入生成树中3. 重复执行下列操作n-1次3.1 在lowcost中选取最短边取adjvex中对应的顶点序号k;3.2 输出顶点k和对应的权值3.3 UU{k}3.4 调整数组lowcost和adjvex【算法时间复杂度分析】设连通网中有n个顶点则第一个进行初始化的循环语句需要执行n一1次第二个循环共执行n - 1次,内嵌两个循环 其一是在长度为n的数组中求最小值需要执行n- 1次 其二是调整辅助数组需要执行n- 1次。所以Prim算法的时间复杂度为 。四、考点总结 1.满足最优子结构性质一定满足贪心性质吗满足贪心选择性质一定满足最优子结构性质而满足最优子结构性质不一定满足贪心选择性质比如背包问题可以用贪心算法解决而0-1背包问题只能用动态规划。2.活动选择问题中☞最优的贪心策略是“最早结束活动优先” ☞怎么衡量两个活动A和B是相容的3.背包问题的贪心算法所需的计算时间为 nlogn4.贪心算法与动态规划算法的主要区别是 贪心选择性质动态规划法通常以自底向上的方式求解各个子问题。贪心法则通常以自顶向下的方式做出一系列的贪心选择。5.最大效益优先是 贪心法 的搜索方式6.贪心算法的基本要素是 贪心选择 性质和 最优子结构 性质 。最优子结构性质是贪心算法与动态规划算法的共同点。贪心选择性质 是贪心算法可行的第一个基本要素也是贪心算法与动态规划算法的主要区别。
