如何建设诗词网站,公司网页免费制作,wordpress企业主题教程,中国商标网查询入口目录 一、贪心算法的定义二、贪心算法的基本步骤三、贪心算法的性质#xff08;一#xff09;最优子结构性质#xff08;二#xff09;贪心选择性质 四、贪心算法的应用#xff08;一#xff09;哈夫曼树——哈夫曼编码#xff08;二#xff09;图的应用——求最小生成… 目录 一、贪心算法的定义二、贪心算法的基本步骤三、贪心算法的性质一最优子结构性质二贪心选择性质 四、贪心算法的应用一哈夫曼树——哈夫曼编码二图的应用——求最小生成树1、普里姆算法Prim2、克鲁斯卡尔算法Kruskal3、两种算法的比较 三图的应用——求单源最短路径迪杰斯特拉算法Dijkstra 一、贪心算法的定义
贪心算法是指不考虑整体上的综合最优决策而在局部上以最优决策来解决问题即每次选择的都是最优的解决方案不考虑该决策对整体的影响。这种方法在处理一些情况下可以得到最优解的很好近似方案例如哈夫曼编码、求最小生成树中的普里姆算法Prim、克鲁斯卡尔算法Kruskal、求单源最短路径中的迪杰斯特拉算法Dijkstra等算法。
二、贪心算法的基本步骤
首先对整体最优解采用贪心算法进行分解将其化为若干个小规模的子问题这些子问题是相互独立的然后通过数学归纳法证明在每一步的选择中可以依据贪心策略在当前子问题中选择出最优解局部解决不考虑整体情况只考虑当前最后将所有子问题的最优解进行整体合并得到整体的最优解从而解决问题简单可归纳为三个步骤。
三、贪心算法的性质 贪心算法具有以下两大性质若针对某一问题若具有以下重要性质则可以通过使用贪心算法可以得到最优解。 一最优子结构性质
针对一个问题将问题分为若干个子问题从而该问题的最优解分割成若干个子问题的最优解来解决然后通过递推从而得到该问题的最优解即最优子结构性质。所以具有这种性质的问题才能保证通过贪心算法得到的解是最优解。【可分割局部】
二贪心选择性质
在求解问题时每一步都采取在当前情况下最优的选择即每次选择都是在局部中选择最优解从而最终得到的解是整体最优解最近似即贪心选择性质。【局部最优】
四、贪心算法的应用
在《数据结构》中贪心算法的常见应用场景有以下例如哈夫曼树中的哈夫曼编码图的应用中求最小生成树以及求单源最短路径的相关算法。 #mermaid-svg-uPjnTPDfIBvITeLp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-uPjnTPDfIBvITeLp .error-icon{fill:#552222;}#mermaid-svg-uPjnTPDfIBvITeLp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-uPjnTPDfIBvITeLp .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-uPjnTPDfIBvITeLp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-uPjnTPDfIBvITeLp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-uPjnTPDfIBvITeLp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-uPjnTPDfIBvITeLp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-uPjnTPDfIBvITeLp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-uPjnTPDfIBvITeLp .marker.cross{stroke:#333333;}#mermaid-svg-uPjnTPDfIBvITeLp svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-uPjnTPDfIBvITeLp .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-uPjnTPDfIBvITeLp .cluster-label text{fill:#333;}#mermaid-svg-uPjnTPDfIBvITeLp .cluster-label span{color:#333;}#mermaid-svg-uPjnTPDfIBvITeLp .label text,#mermaid-svg-uPjnTPDfIBvITeLp span{fill:#333;color:#333;}#mermaid-svg-uPjnTPDfIBvITeLp .node rect,#mermaid-svg-uPjnTPDfIBvITeLp .node circle,#mermaid-svg-uPjnTPDfIBvITeLp .node ellipse,#mermaid-svg-uPjnTPDfIBvITeLp .node polygon,#mermaid-svg-uPjnTPDfIBvITeLp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-uPjnTPDfIBvITeLp .node .label{text-align:center;}#mermaid-svg-uPjnTPDfIBvITeLp .node.clickable{cursor:pointer;}#mermaid-svg-uPjnTPDfIBvITeLp .arrowheadPath{fill:#333333;}#mermaid-svg-uPjnTPDfIBvITeLp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-uPjnTPDfIBvITeLp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-uPjnTPDfIBvITeLp .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-uPjnTPDfIBvITeLp .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-uPjnTPDfIBvITeLp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-uPjnTPDfIBvITeLp .cluster text{fill:#333;}#mermaid-svg-uPjnTPDfIBvITeLp .cluster span{color:#333;}#mermaid-svg-uPjnTPDfIBvITeLp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-uPjnTPDfIBvITeLp :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 贪心算法的应用 哈夫曼编码 求最小生成树 普里姆算法 克鲁斯卡尔算法 求单源最短路径 迪杰斯特拉算法 一哈夫曼树——哈夫曼编码
注求哈夫曼编码时最小频率和最小权值等同这里以最小权值为例介绍。 简单的来说哈夫曼编码是可变字长编码(VLC)的一种常用于数据的压缩压缩率在20%~90%。哈夫曼树以及哈夫曼编码的基本概念可以回顾一下之前的文章数据结构学习笔记——哈夫曼树 例如画出以3468121315182540为结点权值所构造的哈夫曼树并对各结点编码。 解选取权值最小的两个结点3和4相加347新的根结点为7将其插入到树的集合中 此时集合中为[678121315182540]继续选取最小的两个结点权值 此时集合中为[812131315182540]继续选取最小的两个结点权值 此时集合中为[13131518202540]继续选取最小的两个结点权值 此时集合中为[151820252640]继续选取最小的两个结点权值 此时集合中为[2025263340]继续选取最小的两个结点权值 此时集合中为[26334045]继续选取最小的两个结点权值 此时集合中为[404559]继续选取最小的两个结点权值 此时集合中为[5985]继续选取最小的两个结点权值 即为最终的哈夫曼树设左分支为0右分支为1如下 则各叶子结点的哈夫曼编码如下 300010 400011 60000 81100 121101 13001 15010 18011 25111 4010
从以上过程中不难看出每次的选择都是选取两棵根结点权值最小的树作为左、右子树新的二叉树的根结点权值为其权值之和然后将原先两个结点从森林中删除新的结点添加进去……按照由下至上依次构造哈夫曼树最上层的权值最大。 1、哈夫曼编码的最优子结构性质
针对哈夫曼树对字符进行编码将要编码的字符作为叶子节点两两组合从下往上通过执行n-1次的合并产生新的根结点依次进行下去得到最终的哈夫曼编码。由于每次选择的都是两个最小权值结点从而构成了一个局部最优解。【局部最优】 n个结点的哈夫曼树可形成共2n-1个结点且叶子结点的个数也为n分支结点的个数总结点数-叶子结点数2n-1-nn-1即有n-1次合并。 2、哈夫曼编码的贪心选择性质
每次选择当前两个或权值最小的结点构造一颗子树的根结点其权值为权值之和并把产生的子树的根结点再插入到队列中最后按结点的权值大小为最小优先队列。由于每次选择的情况都是最小权值结点所以这两个结点之和一定是最优解。【选择最优】
二图的应用——求最小生成树
简单的来说含有n个顶点的最小生成树有以下特点 ①最小生成树不唯一 ②最小生成树是一个无环图不形成回路 ③最小生成树中包含图的所有顶点 ④最小生成树在所有生成树中该树的各边权值之和最小 ⑤最小生成树生成树的边的个数为n-1 在生成最小生成树时可以选择不同的边所以最小生成树不唯一存在权值相同的边但若当图G的各边权值不同则此时最小生成树是唯一的所以最小生成树的边的权值之和总是唯一的。 最小生成树的概念可以回顾一下之前的文章数据结构学习笔记——图的应用1最小生成树、最短路径
1、普里姆算法Prim
普里姆算法的步骤如下 ①从顶点集V中任意选取一个顶点然后将与该顶点邻接的边中选取一条权值最小的边将其并入从而得到一棵树 ②继续选取邻接的边中最短的边权值最小连接边并入树中若有相同权值则任选一条即可 ③直到图中的所有顶点都被并入得到最小生成树。
普里姆算法适用于求边稠密的网的最小生成树由于每次都是选择一个点与其他剩下点的之间的最短边最小权值所以其时间复杂度与图的边数无关核心语句是在集顶点集V中寻找最近的顶点所以n个顶点、e条边的无向连通带权图其时间复杂度为O(n2)。 例如下面是一个无向带权连通图采用普里姆算法生成最小生成树 任意选取一个顶点为起点开始这里选取V1为例。 此时邻接的边的权值分别为[2、3、6]取最小权值2所以V1与邻接的顶点V4相连 此时邻接的边的权值分别为1、4、5、5以及加上前面的3、6即[1、3、4、5、5、6]取最小权值1所以V4与邻接的顶点V6相连 此时邻接的边的权值分别为3、4以及加上前面的3、6、4、5、5即[3、4、4、5、5、6]取最小权值3V6与邻接的顶点V5相连 取此时最小权值取的是当前图中剩余各边对应权值中最小的权值即3V1与V3相连 取此时最小权值即4V4与V2相连至此所有顶点都被访问到得到最小生成树该最小生成树的代价为3142313 1普里姆算法的最优子结构性质
从上可看出普里姆算法的核心是每次选择当前顶点连通与剩下顶点未连通之间的最小权值的边依次进行每次选最小最后得到一棵最小生成树。由于每次选择两个最小权值边从而构成了一个局部最优解。【局部最优】
2普里姆算法的贪心选择性质
由于在每次选择中都是选择的权值最小的边所以保证了每一步的选择情况都是当前最优的从而最终得到的是一棵最小生成树。【选择最优】
2、克鲁斯卡尔算法Kruskal
克鲁斯卡尔算法的步骤如下 ①先将图的所有边对应的权值按照从小到大的顺序排序 ②选择其中权值最小的边加入并连接并入树中若选取的某边与先前的树构成回路环则舍去 ③一直进行下去权值以小到大直到所有顶点被访问到得到最小生成树。
克鲁斯卡尔算法适用于求边稀疏的网的最小生成树核心语句是将e条边从小到大依次排序所以n个顶点、e条边的无向连通带权图其时间复杂度为O(eloge)。 例如下面是一个无向带权连通图采用克鲁斯卡尔算法生成最小生成树 将图中所有边对应的权值按从小到大排序如下1234568。 可知权值1最小首先连接V4和V6 3、选择权值2连接V6与V5 3、选择权值3选取V4与V1连接 4、选择权值4连接V1与V3 5、选取权值5连接V4与V2最终得到最小生成树如下该最小生成树的代价为4315215 1克鲁斯卡尔算法的最优子结构性质
克鲁斯卡尔算法中由于权值已经顺序排列所以依次进行每次加入的都是当前最小的边构成的都是当前的一个连通分量的最小生成树该顶点到其他顶点的最小生成树最后得到整个图的最小生成树。由于事先已排序好每次选择的是当前最小权值边从而构成了一个局部最优解。【局部最优】
2克鲁斯卡尔算法的贪心选择性质
由于在每次选择中都是选择的权值最小的边且保证不会成回路环若不满足该条件则说明当前情况不是最优所以保证了在每一步的选择情况都是当前最优的从而最终得到的是一棵最小生成树。【选择最优】
3、两种算法的比较
名称比较普里姆算法一次次克鲁斯卡尔算法整体
普里姆算法是每次选取一个最短边即针对顶点只能得到该顶点到其他顶点的最小生成树当需要求图的最小生成树时需要一次次的普里姆算法才能得到最小生成树而克鲁斯卡尔算法由于一开始就将边的权值按从小到大依次排序是从整体上出发所以可以直接得到最小生成树另外由于需要对所有的边进行排序其占用的空间也比普里姆算法多空间复杂度为O(n)。
三图的应用——求单源最短路径
迪杰斯特拉算法Dijkstra
迪杰斯特拉算法计算的是在一个有向带权图中指定一个源点到其他所有顶点的最短路径长度即最短路径而单源最短路径一般通过迪杰斯特拉算法解决。 在带权图中一个顶点到另一个顶点所经过边的权值之和称为该路径的带权路径长度由于可能路径不止一条所以将带权路径长度最短的那条路径称为最短路径。 迪杰斯特拉算法的步骤如下 ①通过一个数组存储源点到每个顶点的距离 ②依次选取源点当前未访问到的所有顶点中距离最短的顶点然后更新该顶点相邻的顶点与源点的距离 ③重复过程直到所有顶点都被访问到。
克鲁斯卡尔算法中的核心语句是寻找距离源点最近的顶点所以n个顶点的有向带权图其时间复杂度为O(n2)另外由于需要数组存放带权邻接矩阵所以空间复杂度为O(n)。
1迪杰斯特拉算法的最优子结构性质
在每次更新该顶点相邻的顶点与源点的距离时当前所有的顶点与源点的最短路径是最优的从而构成了一个局部最优解。【局部最优】
2迪杰斯特拉算法的贪心选择性质
由于每次选择的都是源点当前未访问到的所有顶点中距离最短的顶点保证选择的都是当前距离最短从而得到的是最短路径。【选择最优】
