北京网站建设那些中国铁路建设投资公司网站熊学军

当前位置： 首页 > news >正文

北京网站建设那些,中国铁路建设投资公司网站熊学军,中心建设投官方网站 软件下载,网站设计与管理贪心算法#xff08;Greedy Algorithm#xff09; 找零钱问题 假设有4种硬币#xff0c;面值分别为#xff1a;二角五分、一角、五分和一分#xff0c;现在要找给顾客六角三分钱#xff0c;如何找使得给出的硬币个数最少#xff1f; 首先选出1个面值不超过六角三分的最…贪心算法Greedy Algorithm 找零钱问题 假设有4种硬币面值分别为二角五分、一角、五分和一分现在要找给顾客六角三分钱如何找使得给出的硬币个数最少 首先选出1个面值不超过六角三分的最大硬币即两角五分 然后从六角三分中减去两角五分剩下三角八分 再选出1个面值不超过三角八分的最大硬币 即又一个两角五分。如此一直做下去…… 这里用到的方法就是贪心算法 在这个例子中找硬币算法得到的结果是整体最优解问题本身具有最优子结构性质可以用动态规划算法求解用贪心算法更简单、更直接、且解题效率更高分。 贪心算法的基本思想 贪心算法在每一步选择中都采取在当前状态下最优的选择目的是希望由此导出的结果是最优的。贪心算法在求解问题时并不着眼于整体最优它所做出的选择仅仅是当前看来最优的。最优子结构性质局部最优解能决定全局最优解。问题能够分成子问题来解决。子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的区别 动态规划 每一步的最优解是由上一步的局部最优解进行选择得到的。因此需要保存之前求解的所有子问题的最优解备查。 贪心算法 下一步的最优解是由上一步的最优解推导得到的。当前最优解包含上一步最优解之前的最优解不作保留。在贪心算法中做出的每步决策都无法改变不能回退。 二者关系 贪心算法本质上是一种更快的动态规划算法。贪心法正确的条件每一步的最优解一定包含上一步的最优解。如果可以证明在递归求解的每一步按贪心选择策略选出的局部最优解最终可导致全局最优解则二者是等价的。 **贪心算法对每个子问题的解决方案都做出选择不能回退。动态规划则会保存以前的运算结果并根据以前的结果对当前结果进行选择有回退功能。对某些问题动态规划算法并不是最简便的方法因为有时候确实没有必要知道所有子问题的解。 ** 贪心算法得到的结果不能保证全局最优 活动安排问题 设有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]递增顺序进行贪心选择可得到全局最优解 首先证明活动安排问题有一个最优解以贪心选择开始 设E{1,…,n}为给定活动集合按结束时间非减序排列显然活动1具有最早的完成时间。设集合A是该问题的一个最优解同时第一个活动是活动k。若k1则A就是一个以贪心选择开始的最优解。若k1则设(A-{k})∪{1}由于由于F[1]≤F[k]且A中活动相容故B中活动也相容由于B和A中包含的活动个数相同故B也是最优的。 得证总存在一个以贪心选择开始的最优活动安排方案。 用数学归纳法证明贪心算法的解是全局最优解 设E{1,2,…,n}为所给的活动集合在做了贪心选择即选择了活动1后原问题就简化为对E中所有与活动1相容的活动进行活动安排的子问题。若A是原问题的最优解则AA-{1}是活动安排问题E’{i∈E : si ≥ f1}的最优解。证明如果能找到E’的一个解集B’它包含比A’更多的活动则将活动1加入到B将产生A的一个解它包含比A更多的活动这与A的最优性矛盾因此在做出贪心选择活动1之后原问题N简化为子问题N’对E中所有与活动1相容的活动进行安排 每一步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。 算法设计 用数组A[1:n]来存储所选择的活动设活动总数为n若活动i在集合A中则A[i]1否则A[i]0.各活动的起始时间和结束时间存储于数组S[1:n]和F[1:n]中数组F[1:n]已按结束时间的非减序排列。依次从F[1:n]中选择活动i尝试加入集合A设变量k记录A中最近一次加入的活动由于F[1:n]有序所以F[k]总是当前集合A中所有活动的最大结束时间。依次检查活动i是否与当前已选择的所有活动相容若相容则将活动i加入集合A中若不相容则放弃活动i。继续检查F[1:n]中下一个活动与集合A中活动的相容性。直到所有活动均已检查完毕程序结束。 新增的活动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 i2; in; i){if(s[i] f[j]){count;j i;a[i] 1;}else{a[i] 0;}}return count; }贪心算法求解背包问题 首先计算每种物品单位重量价值Vi/Wi然后按照贪心选择策略将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入后背包内的物品总重量未超过C则选择单位重量价值次高的物品并尽可能多地装入背包依次策略一直进行下去直到背包装满为止。 算法复杂度分析计算时间主要用于对各种物品按单位重量价值排序因此算法的计算时间上界为O(nlogn) 对于0-1背包问题贪心选择为什么不能得到最优解 因为对该问题采用贪心选择策略无法确保最终将背包装满部分闲置的背包空间降低了每公斤背包空间的价值 最优装载问题 有一批集装箱要装船其中集装箱 i 的重量为wi 轮船最大载重量为c要求在不受体积限制的情况下将尽可能多的集装箱装船。 给定c0, wi0, 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)(n1));//根据w从小到大排序数组R记录调整后的序号sort(w,R,n);for(int i1; in; i){x[i] 0;}for(int i1; in; 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算法是求解单源最短路径问题的一种有效算法 将图中所有顶点分成两组SV-SS已确定最短路径的顶点的集合TV-S尚未确定最短路径的顶点集合初始时集合S中仅包含源点V0不断在集合T中做贪心选择扩充集合S直到S中包含了V中的所有顶点 算法设计思想 初始时S仅包含源v0定义“特殊路径”从源v0到G中某一顶点u且中间只经过S中顶点的路径称为从源到u的路径。用数组元素dist[u]记录源v0到u的最短特殊路径的长度。 Dijkstra算法每次从T中取出具有最短特殊路径长度的顶点u将u添加到S中同时对数组dist作必要的修改。一旦S包含了所有V中顶点dist就记录了从源到其它所有顶点之间的最短路径长度。 Dijkstra算法的数据结构设计 使用带权邻接矩阵表示有向图G辅助数组Snvex表示已找到从V0出发的最短路径的终点的集合。辅助数组dist[nvex]存放当前找到的从V0到每个Vi的最短路径长度。辅助数组prev[next]数组元素为从V0到路径各顶点的最短上该顶点的前一顶点的序号 算法伪代码 令S{V0}T{其余顶点}T中顶点Vi对应的距离值dist[i]为若存在V0,Vidist[i]为V0,Vi弧上的值若不存在V0,Vidist[i]为∞从T中选取一个dist矩阵值最小的顶点u加入S对T中每一个顶点Vj的距离值dist[j]进行修改若增加u作为中间顶点之后从V0到Vj的距离比不加u的路径要短则更新Vj距离值。重复上述步骤直到S中包含所有顶点SV为止 void Dijkstra(int n,int v,int dist[],int prev[],int **c){int s[n];for(int i1; in; 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 i1; in; i){int temp maxint;int u v;for(int j1; jn; j){if(!s[j] dist[j]temp){u j;temp dist[j];}}s[u] true;for(int j1; jn ;j){if(!sj){int newdist dist[u] c[u][j];if(newdist dist[j]){dist[j] newdist;prev[j] u;}}}} }算法复杂度分析对于具有n个顶点和e条边的带权有向图G需O(n2) 多机调度问题 设有n个独立的作业{1,2…n}这n个作业由m台相同的机器进行加工处理作业 i 所需要的执行时间为ti每个作业均可以在任何一个机器加工处理但作业未完成之前不容许中断处理作业也不能拆分为更小的子作业。 多机调度问题要求给出一种作业调度方案使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是NP完全问题目前为止还没有十分有效的解法用贪心选择策略有时可以设计出较好的近似算法。 具体来说采用最长处理时间优先的贪心选择策略 当n≤m时只要将机器i的[0,ti]时间区间分配给作业i即可。算法只需要O(1)时间nm时首先将n个作业依其所需的处理时间从大到小排序然后依次顺序将作业分配给空闲的处理机算法所需的计算时间为O(nlogn)