自适应好还是响应式网站好,win10优化大师,湖州网站建设公司哪家好,合肥营销型网站建设1.贪心算法基础
1.贪心算法的基本思想
贪心算法是从问题的某一个初始解出发#xff0c;向给定的目标推进。但它与普通递推求解过程不同的是#xff0c;其推动的每一步不是依据某一固定的递推式#xff0c;而是做一个当时看似最佳的贪心选择#xff0c;不断地将问题实例归…1.贪心算法基础
1.贪心算法的基本思想
贪心算法是从问题的某一个初始解出发向给定的目标推进。但它与普通递推求解过程不同的是其推动的每一步不是依据某一固定的递推式而是做一个当时看似最佳的贪心选择不断地将问题实例归纳为更小的相似的子问题并期望通过所做的局部最优选择产生出一个全局最优解。
贪心算法Greedy Alogorithm又叫登山算法它的根本思想是逐步到达山顶即逐步获得最优解是解决最优化问题时的一种简单但是适用范围有限的策略。
贪心算法没有固定的框架算法设计的关键是贪婪策略的选择。贪心策略要无后向性也就是说某状态以后的过程不会影响以前的状态至于当前状态有关。
贪心算法是对某些求解最优解问题的最简单、最迅速的技术。某些问题的最优解可以通过一系列的最优的选择即贪心选择来达到。
但局部最优并不总能获得整体最优解但通常能获得近似最优解。 在每一步贪心选择中只考虑当前对自己最有利的选择而不去考虑在后面看来这种选择是否合理。
2.贪心算法的基本要素
一个贪心算法求解的问题必须具备以下两要素
1. 贪心选择性质
所谓贪心选择性质是指应用同一规则将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择但不依赖于未做出的选择。
1贪心算法选择每一步最佳的
2不依赖于未做出的选择
3自顶向下的迭代
4程序在运行过程中无回溯过程
首先证明问题存在一个整理最优解必定包含了第一个贪心选择。然后证明在做了贪心选择之后原问题简化为规模较小的类似的子问题即可继续使用贪心选择。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质。 由于运用贪心策略解题在每一次都取得了最优解问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。 1.贪心算法又称贪婪算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑他所做出的是在某种意义上的局部最优解。
2.贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到。这是贪心算法可行的第一个基本要素。
3.当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响。贪心算法对每个子问题的解决方案都做出选择不能回退。
4.贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行根据某个优化测度每一步都要确保能获得局部最优解。每一步只考虑一个数据他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时就不把该数据添加到部分解中直到把所有数据枚举完或者不能再添加算法停止。
5.实际上贪心算法适用的情贪心算法(贪婪算法)况很少。一般对一个问题分析是否适用于贪心算法可以先选择该问题下的几个实际数据进行分析就可以做出判断。
该算法存在的问题
1.不能保证求得的最后解是最佳的
2.不能用来求最大值或最小值的问题
3.只能求满足某些约束条件的可行解的范围
3.贪心算法适合的问题
贪心算法通常用来解决具有最大值或最小值的优化问题。它是从某一个初始状态出发根据当前局部而非全局的最优决策以满足约束方程为条件以使得目标函数的值增加最快或最慢为准则选择一个最快地达到要求的输入元素以便尽快地构成问题的可行解。 4.贪心算法的基本步骤
贪心算法的原理是通过局部最优来达到全局最优采用的是逐步构造最优解的方法。在每个阶段都做出一个看上去最优的决策一旦做出就不再更改
要选出最优解可不是一件容易的事要证明局部最优为全局最优要进行数学证明否则就不能说明为全局最优。
很多问题表面上看来用贪心算法可以找到最优解实际上却把最优解给漏掉了。这就像现实生活中的“贪小便宜吃大亏”。所以我们在解决问题的时候一定要谨慎使用贪心算法一定要注意这个问题适不适合采用贪心算法。
贪心算法很多时候并不能达到全局最优为什么我们还要使用它呢
因为在很多大规模问题中寻找最优解是一件相当费时耗力的事情有时候付出大量人力物力财力后回报并不与投入成正比。在这个时候选择相对最优的贪心算法就比较经济可行了。有的问题对最优的要求不是很高在充分衡量付出和回报后选择贪心算法未尝不是一种不错的选择呢。
步骤
(1) 选定合适的贪心选择的标准
(2) 证明在此标准下该问题具有贪心选择性质
(3) 证明该问题具有最优子结构性质
(4) 根据贪心选择的标准写出贪心选择的算法求得最优解。
说明1当一个问题具有多个最优解时贪婪算法并不能求出所有的最优解。
2整体的最优解时通过一系列的局部最优选择即贪心选择来达到的。通常采用的方法是假设问题的一个整体最优解并证明可以修改这个最优解使其以贪婪算法开始。
贪心算法使用基本步骤
1.从问题的某个初始解出发
2.采用循环语句当可以向求解目标前进一步时就根据局部最优策略得到一个不分解缩小问题的范围或规模。
3.将所有的部分解综合起来得到问题的最终解。 货郎担旅行商问题
有n个城市用12…n表示城i,j之间的距离为dij有一个货郎从城1出发到其他城市一次且仅一次最后回到城市1怎样选择行走路线使总路程最短
假定有5个城市费用矩阵如表1-1所示。如果货郎从第一个城市出发采用贪婪法求解解法如下图 5.贪心算法实例——背包问题
在 从零开始学动态规划中我们已经谈过三种最基本的背包问题0-1背包部分背包完全背包。很容易证明背包问题不能使用贪心算法。然而我们考虑这样一种背包问题在选择物品i装入背包时可以选择物品的一部分而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标选择单位重量价值最高的物品将尽可能多的该物品装入背包依此策略一直地进行下去直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。 2.汽车加油问题
问题描述 一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站如图4-1所示。指出若要使沿途的加油次数最少设计一个有效的算法指出应在那些加油站停靠加油前提行驶前车里加满油。 由于汽车是由始向终点方向开的我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。我们可以假设不到万不得已我们不加油即除非我们油箱里的油不足以开到下一个加油站我们才加一次油。在局部找到一个最优的解。每加一次油我们可以看作是一个新的起点用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。
贪心策略汽车行驶过程中应走到自己能走到并且离自己最远的那个加油站在那个加油站加油后再按照同样的方法贪心选择下一个加油站。
例在汽车加油问题中设各个加油站之间的距离为假设没有环路:1,2,3,4,5,1,6,6.汽车加满油以后行驶的最大距离为7则根据贪心算法求得最少加油次数为4需要在3,4,6,7加油站加油如下图所示 1贪心选择性质
设在加满油后可行驶的N千米这段路程上任取两个加油站、且距离始点比距离始点近则若在加油不能到达终点那么在加油一定不能到达终点如下图 由图可知因为mNnN即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米所以只要终点不在A、B之间且在B的右边的话根据贪心选择为使加油次数最少就会选择距离加满油得点远一些的加油站去加油因此加油次数最少满足贪心选择性质。
2最优子结构性质
当一个大问题的最优解包含着它的子问题的最优解时称该问题具有最优子结构性质。
(b[1],b[2],……b[n]) 整体最优解
b[1]1,(b[2],b[3],……b[n]) 局部最优解
每一次加油后与起点具有相同的条件每个过程都是相同且独立。
算法步骤先监测各加油站之间的距离若发现其中有一个距离大于汽车加满油能行驶的距离则输出no solution否则对加油站间的距离进行逐个扫描尽量选择往远处行驶不能行驶就让num1.最终统计出来的num便是最少的加油站数
int Greedy(int a[],int n,int k) { int *bnew int[k1]; //加油站加油最优解b1~bkint num 0; int s0; //加满油后行驶的公里数for(int i 0;i k;i) { if(a[i] n) { coutno solution\n; return; } } for(int i 0,s 0;i k;i) { s a[i]; if(s n) { num; b[i]1; s a[i]; } } return num;
}3.最优服务次序问题
最优服务次序问题: 设有n个顾客同时等待同一项服务顾客i 需要的服务时间为ti,1 ≤ i ≤ n应如何安排这n 个顾客的服务次序才能使平均等待时间达到最小。平均等待时间是n 个顾客等待服务时间的总和除以n。
假设原问题为T而我们已经知道了某个最优服务系列即最优解为A{t(1),t(2),⋯ t(n)}(其中t(i)为第i个用户需要的服务时间)则每个用户等待时间为:
T(1)t(1); T(2)t(1)t(2); ⋯⋯
T(n)t(1)t(2)t(3)…t(n);
那么总等待时间即最优值为:
TAn*t(1)(n-1)*t(2)…(n1-i)*t(i)…2*t(n-1)t(n)
由于平均等待时间是n个顾客等待时间的总和除以n故本题实际上就是求使顾客等待时间的总和最小的服务次序。
贪心策略对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务即做完第一次选择后原问题T 变成了对n-1 个顾客服务的新问题T’。新问题和原问题相同只是问题规模由n减小为n-1。基于此种选择策略对新问题T’选择n-1顾客中选择服务时间最短的先进行服务如此进行下去直至所有服务都完成为止。 1贪心选择性质
先来证明该问题具有贪心选择性质即最优服务A 中t(1)满足条件: t(1)t(i)(2 ≤ i ≤ n)。证明用反证法:
假设t(1)不是最小的不妨设t(1)t(i)(i1)。设另一服务序列B{t(i),t(2),⋯, t(1),...t(n)} 那么TA-TBn*[t(1)-t(i)](n1-i)*[t(i)- t(1)](1-i)*[t(i)-t(1)]0
即TATB这与A 是最优服务相矛盾即问题得证。故最优服务次序问题满足贪心选择性质。
2 问题的最优子结构性质
在进行了贪心选择后原问题T就变成了如何安排剩余的n-1 个顾客的服务次序的问题T’是原问题的子问题。若A 是原问题T 的最优解则A’{t(2),⋯ t(i)...t(n)}是服务次序问题子问题T’的最优解。
证明: 假设A’不是子问题T’的最优解其子问题的最优解为B’,则有TB’TA’而根据TA 的定义知TA’t(1)TA。因此TB’t(1)TA’t(1)TA即存在一个比最优值TA更短的总等待时间而这与TA为问题T的最优值相矛盾。因此A’是子问题T’的最优值。从以上贪心选择及最优子结构性质的证明可知对最优服务次序问题用贪心算法可求得最优解。
根据以上证明最优服务次序问题可以用最短服务时间优先的贪心选择可以达到最优解。故只需对所有服务先按服务时间从小到大进行排序然后按照排序结果依次进行服务即可。平均等待时间即为TA/n.
/*功能计算平均等待时间输入各顾客等待时间a[n],n是顾客人数 输出平均等待时间average
*/
double GreedyWait(int a[],int n)
{double average0.0;Sort(a);//按服务时间从小到大排序for(int i0;in;i){average (n-i)*a[i];}average /n;return average;}
例有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下将尽可能多的集装箱装上轮船。
1、算法描述
最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略可产生最优装载问题的最优解。具体算法描述如下页。
templateclass Type
void Loading(int x[], Type w[], Type c, int n)
{int *t new int [n1];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]];}
}多机调度问题要求给出一种作业调度方案使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
约定每个作业均可在任何一台机器上加工处理但未完工前不允许中断处理。作业不能拆分成更小的子作业。
这个问题是NP完全问题到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。 4.区间相交问题
给定x 轴上n 个闭区间。去掉尽可能少的闭区间使剩下的闭区间都不相交。输出计算出的去掉的最少闭区间数。
最小删去区间数目区间总数目-最大相容区间数目。
区间选择问题即若干个区间要求互斥使用某一公共区间段目标是选择最大的相容区间集合。 假定集合S{x1, x2, …, xn}中含有n个希望使用某一区间段每个区间xi有开始时间li和完成时间ri其中0≤leftirighti∞。如果某个区间xi被选中使用区间段则该区间在半开区间(leftirighti这段时间占据区间段。如果区间xi和xj在区间(leftirighti 和(leftjrightj上不重叠则称它们是相容的即如果lefti≥ rightj或者leftj≥ righti 区间xi和xj是相容的。 区间选择问题是选择最大的相容区间集合。
最大相容区间问题可以用贪心算法解决可以将集合S的n个区间段以右端点的非减序排列每次总是选择具有最小右端点相容区间加入集合A中。直观上按这种方法选择相容区间为未安排区间留下尽可能多的区间段。也就是说该算法贪心选择的意义是使剩余的可安排区间段极大化以便安排尽可能多的相容区间。
1具有贪心选择性质
1设A是区间选择问题一个最优解A中区间按右端点非减序排列
2设K是A中第一区间若k1则A就是一个以贪心选择开始的最优解若k1再设BA-{k}U{1}.由于right1
rightk且A中区间是相容的故B中区间也是相容的。 又由于B中区间个数与A中区间个数相同且A是最优的故B也是最优的。也就是B是以贪心选择区间1开始的最优区间选择。
结论总存在一个以贪心选择开始的最优区间选择方案。 5.单源最短路径
给定一个带权有向图GVE其中每条边的权是非负实数,另外还给定V中的一个顶点作为源点。现在要计算源点到其他各顶点的最短路径长度。这里路径长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
例如现有一张县城的城镇地图图中的顶点为城镇边代表两个城镇间的连通关系边上的权为公路造价县城所在的城镇为v0。由于该县的经济比较落后因此公路建设只能从县城开始规划。规划的要求是所有可达县城的城镇必须建设一条通往县城的汽车线路该线路工程的总造价必须最少。
由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。Dijkstra算法描述如下其中输入的带权有向图是G (V , E),V {v0,v1,v2,…,vn}顶点v0是源E为图中边的集合cost[i,j]为顶点i和j之间边的权值当i,jE时cost[i,j]的值为无穷大distance [i]表示当前从源点到顶点i的最短路径长度。
算法步骤
(1)初始时,S中仅含有源。设u是V的某一个顶点把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径并用数组distance记录当前每个顶点所对应的最短特殊路径长度。
(2)每次从集合V-S中选取到源点v0路径长度最短的顶点w加入集合S集合S中每加入一个新顶点w都要修改顶点v0到集合T中剩余顶点的最短路径长度值集合T中各顶点新的最短路径长度值为原来最短路径长度值与顶点w的最短路径长度加上w到该顶点的路径长度值中的较小值。
(3)直到S包含了所有V中顶点此时distance就记录了从源到所有其他顶点之间的最短路径长度。
贪心策略设置两个顶点集合V和S集合S中存放己经找到最短路径的顶点集合V中存放当前还未找到最短路径的顶点。设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 贪心算法适用于最优化问题。它是通过做一系列的选择给出某一问题的最优解。对算法中的每一个决策点做出当时看起来最佳的选择。
贪心算法的基本步骤
1.选择合适的贪心选择的标准
2.证明在此标准下该问题具有贪心选择性质
3.证明该问题具有最优子结构性质
4.根据贪心选择的标准写出贪心选择的算法求得最优解。
贪心算法通常包括排序过程这是因为贪心选择的对象通常是一个数值递增或递减的有序关系,自顶向下计算。
