做网站包含的技术,最新网页游戏传奇,门户网站设计,学软件开发需要学什么贪心算法编号题目1货郎担问题#xff1a;货郎担问题#xff1a;假定有五个城市#xff0c;已知费用矩阵如下#xff0c;分别从五个城市出发#xff0c;然后选取一条费用最小的线路#xff0c;验证这种算法不能得到最优解。贪心选择#xff1a;每次选择之前没有走过的费用…贪心算法编号题目1货郎担问题货郎担问题假定有五个城市已知费用矩阵如下分别从五个城市出发然后选取一条费用最小的线路验证这种算法不能得到最优解。贪心选择每次选择之前没有走过的费用最少的路关键:1 每次选择费用最小的路径走到达后再次做出选择相当于一个规模小一点的TSP子问题。2 每次做出选择的时候并没有考虑以后的情况即并没有考虑最优子结构问题。时间复杂度:O(n^2)空间复杂度:O(n^2)算法2背包求如下背包问题的最优解n7,M15价值P{10,5,15,7,6,18,3}重量为w{2,3,5,7,1,4,1}最优子结构:每次选取物品ti,最优取法为Sn {t1,t2,…,tn},子问题的最优解是:Sn{t2,t3,…,tn}贪心选择当前总价值为Vm,选取重量为m,当前单位价值最大Pm的物品后,Vm1 Vm m*Pm。假设选取的是重量为m,单位价值为Pm’的物品可以达到最优解则Vm1Vm m*Pm’,且使得总价值最大V’m1 Vm,但由于Pm Pm’所以实际V’m1Vm,这与假设矛盾。时间复杂度:快排O(n^2),装包O(n),整体O(n^2)空间复杂度:O(n)算法:1. 计算单位重量价值p1,p2,…,pm2. 对单位重量价值排序3. 初始化背包剩余载重4. 如果能够完全放入总价值 当前物品重量*单位重量价值如果只能部分放入总价值 背包剩余载重*单位重量价值5. 如果背包剩余载重为空算法结束3 dijkstra求单源最短路径问题用迪杰斯特拉算法求下图的单源最短路径问题贪心策略从V-S中选择具有最短路径的顶点贪心选择假设存在从源点V到U长度小于D[U]的路径不妨设经过的点XV-S则D[x] d(v,x) d(v,x) d(x,u) d(v,u) D[u]与D[u]是V-S中只经过S中的顶点到u的最短路径相矛盾最优子结构最优子结构假设出现从V经老S中的其他顶点到达u,再从u到达j的新路则D[u] d(u,j) D[j]这是正确的。假设出现从V经u再到老S中其他顶点x再到j的最短路径则D[u] d(u,x) d(x,j) D[j],又因为D[x] D[u],所以D[x] d(x,j) D[u] d(u,x) d(x,j) D[j]与D[j]是加入u后新生成的最短路径相矛盾。所以如果加入u后新生成的一条从源点到j的新路径这条新路径是从v到j的最短路径。算法时间复杂度:优先级队列O(VlogV ElogV)空间复杂度邻接矩阵O(n^2)邻接表为O(2*mn),m为边数4prim求最小生成树用普里姆算法求下图的最小花费生成树画出生成过程。贪心策略要记录到S中的下一条边uv是一条不在S中且使得SU{u,v}的权值之和也是最小的边贪心选择最优解包含了权值最小的边e1,假设不是这样将e1加入则会形成环去掉环中任意比e1大的边,就构造了更优解与题目矛盾。假设e2,e3,…,ek也是按照同样方式选择出来的边同样按照该方法可以证明ek1也能构造出最优解最优子结构设Prim算法生成的最小生成树为T,图G的最小生成树是T*。假设边e加入到T之前G’是G的最小生成树的子树把e加入T中G’无回路且连通G’是G的最小生成树当eT*结论成立。假设e!T*,T*U{e}包含回路回路中存在边e’,令T**T*U{e}-{e’},则T**的权T*的权与T*是最小生成树矛盾所以TT*时间复杂度O(n^2)空间复杂度O(n^2) 5kruskal求无向带权图的最小生成树问题:贪心策略:选取属于不同联通分量且构成权值最小且不形成回路的两个顶点组成的边、贪心选择证法同第4题的贪心选择证明最优子结构算法 6dijstra求单源最短路径问题求图1中所示网络中各点距离A点的最短路径问题。贪心选择下一条最短路径总是由已产生的最短路径加上一条边形成最优子结构假设P(I,j){Vi,..,Vk,…,Vs,…,Vj}是从i到j的最短路径则P(I,j)P(I,k) P(k,s) P(s,j)假设P(k,..,s)不是最短路径则存在P’(k,…,s)使得P’(I,j)P(I,k) P’(k,s) P(s,j) P(I,j)与P(I,j)是从i到j的最短路径矛盾算法参见第3题7prim求最小生成树问题利用Prim算法求出图1的最小花费生成树,画出生成过程证明算法参见第4题 8ruskal求节点网络的最小生成树用克鲁斯卡尔算法求下图的最小花费生成树画出生成过程。证明算法参见第5题9磁带存放问题贪心策略读取序列按照长度从小到大排列贪心选择设最优解S{l1,l2,…,li,lj,….,ln}假设存在更优的解:S*{l1,l2,..,lj,li,…,ln}ts l1 [(n-1)/n] * l2 … [(n-i1)/n] * li [(n-j1)/n] * lj …(1/n) * lnts* l1 [(n-1)/n] * l2 … [(n-i1)/n] * lj [(n-j1)/n] * li …(1/n) * lnts* - ts [(j-i)/n] * lj [(i-j)/n] * li [(j-i)/n] * (lj - li) 0 ,即 ts* ts 与ts*是最优解矛盾最优子结构假设已经摆放了l1,那么剩余需要摆放的磁带为{l2,…,ln},这是原问题T的一个字问题T*,假设此时该子问题存在另一个最优解T** T*则T**U{l1} T*U{l1} T与T是最优解矛盾算法时间复杂度:O(n^2)空间复杂度:O(n)10顶点覆盖问题令G(V, E)是一个无向图G的顶点覆盖集S是G的一个子集使得S⊆V并且E中的每一条边至少和S中的一个顶点关联。考虑下面寻找G的顶点覆盖算法首先按顶点度的递减顺序排序V中的顶点接着执行下面步骤直到所有的边全被覆盖挑选度数最高的顶点且至少和余图中的一条边相关联把这个顶点加入到顶点覆盖集中并删去和这个顶点相关联的所有边。设计这个算法说明这个算法不总能得到最小顶点覆盖集。贪心选择每次选择把度数最高的顶点加入到覆盖集中删除与该顶点相关联的边更新度数。但该问题并不具有贪心选择性质反证法:算法时间复杂度O(n^2)空间复杂度O(n^2) 11最大团问题团完全子图贪心策略选择不相邻接的顶点中度数最小的顶点删除。不满足贪心选择与其他顶点不相邻接且度数最小的顶点可能有多个应用局部选择不一定能得出全局最优解。不满足最优子结构性质可能删除最优解中的点而导致全局最优解中不含有局部最优解算法1初始化令CG2 判断C是否为最大团若是算法结束否则转步骤33 从C中删除与其他顶点不相邻接且度数最小的点4 更新C,转步骤2时间复杂度:O(n^2) 12无向图着色问题令G(V,E)是一个无向图图的着色问题是给V中的每一个顶点赋予一种颜色使得每一对邻接顶点不会具有相同颜色。G的着色问题是确定为G着色所需要的最少颜色数。考虑下面的方法令颜色为123…首先用颜色1为尽可能多的顶点着色然后用颜色2为尽可能多的顶点着色如此等等设计这个算法说明这个方法不总能用最少的颜色数为图着色。证明不能用贪心 算法1设定顶点集合中顶点编号i,i02 i,若i|V|转3否则算法结束3 令颜色编号j0,颜色集合为CL4 j5若当前节点的所有邻居节点都没有使用颜色clj,则为当前顶点赋予颜色clj。转步骤2否则转4 13 区间相交问题给定x轴上n个闭区间。去掉尽可能少的闭区间使剩下的闭区间都不相交。最小删除区间数量区间数量-最大相容区间数量。贪心策略每次选取右端点最小的区间做相容性判断贪心选择设区间集为I{I1,I2,…,Ik},设最大相容区间集为R,R中第一个区间为Ik。假设k1,那么R’R-{Ik}U{I1},则R’也相容也是最大相容区间集。最优子结构选择I1后原问题变为输入区间集为I*I – {I1}的最大相容区间集为R’R-{I1}的子问题,假设I’存在最优解R**,即|R**| |R*| ,则|R**U{I1}| |R*U{I1}| |R|与R是最优解矛盾算法时间复杂度:O(nlogn)快排空间复杂度O(nlogn) 14问题:设x1,x2,…,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点至少需要多少个这样的固定长度闭区间设计解此问题的有效算法并证明算法的正确性。贪心策略闭区间从最左向右开始覆盖贪心选择设闭区间集合为L{l1,l2,…,lm},点序列集合为S{S1,S2,…,Sn}。选择S1覆盖k个节点剩下的问题转化为如何从L’L-{l1}中选取最少的区间去覆盖S’S-{S1,S2,…,Sk}最优子结构问题最优解为L{l1,l2,…,lm}子问题的最优解为Ln-k{l2,..,lm},则有Ln-kU{l1}L算法时间复杂度:O(nlogn)空间复杂度:O(n)15最短服务时间问题此问题与磁带存放问题其实是同一个问题证明算法参见第9题。 16石子合并问题在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆最多选k堆石子合并成新的一堆合并的费用为新的一堆石子数。试设计一个算法计算出将n堆石子合并成一堆的最大总费用和最小总费用。分析是本质Huffman问题。贪心选择设b,c为T的最深且相邻叶子结点x,y是权值最小的两个叶节点。交换b与x得T’,交换b与x,c与Y得T’’WPL(T) – WPL(T’)WT(b)*LT(b) WT(x)*LT(x) – WT’(b)*LT’(b) – WT’(x)*LT’(x) WT(b)*LT(b) WT(x)*LT(x) – WT(b)*LT(x) – WT(x)*LT(b) [WT(b)-WT(x)]*LT(b) [WT(x) – WT(b)]*LT(x) [WT(b)-WT(x)]*[LT(b) – LT(x)]因为WT(b)WT(x),LT(b) LT(x),则WPL(T) – WPL(T’) 0,即WPL(T’) WPL(T)同理可证WPL(T’’) WPL(T)又因为T是哈夫曼树所以WPL(T) WPL(T’’),综上所述WPL(T)WPL(T’’)最优子结构设T是NodeSet最大带权路径的二叉树设x,y为叶子并且互为兄弟z是x,y的父节点NodeSet’T-{x,y}U{z},T’是NodeSet’的Huffman树。算法时间复杂度O(nlogn)空间复杂度:O(n)总结
转自https://blog.csdn.net/qingyuanluofeng/article/details/47776263
