网站里的个人中心下拉列表怎么做,wordpress媒体库显示,网站内容建设方案,ui设计培训班学费大概多少目录 一、单源最短路径1.1 算法基本思想1.2 算法设计思想1.3 算法的正确性和计算复杂性1.4 归纳证明思路1.5 归纳步骤证明 二、最小生成树2.1 最小生成树性质2.1.1 生成树的性质2.1.2 生成树性质的应用 2.2 Prim算法2.2.1 正确性证明2.2.2 归纳基础2.2.3 归纳步骤2.3 Kruskal算… 目录 一、单源最短路径1.1 算法基本思想1.2 算法设计思想1.3 算法的正确性和计算复杂性1.4 归纳证明思路1.5 归纳步骤证明 二、最小生成树2.1 最小生成树性质2.1.1 生成树的性质2.1.2 生成树性质的应用 2.2 Prim算法2.2.1 正确性证明2.2.2 归纳基础2.2.3 归纳步骤2.3 Kruskal算法2.3.1 证明思路2.3.2 归纳步骤证明2.3.3 T是G的最小生成树 2.4 应用数据分组问题2.5 单链聚类 三、多机调度问题四、小结 一、单源最短路径 给定带权有向图G (V,E)其中每条边的权是非负实数。另外还给定V中的一个顶点称为源。现在 要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
1.1 算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。 Dijkstra算法有关概念 X∈S←→x∈V且从s到x的最短路径已经找到 初始S{s},SV时算法结束 从s到u相对于S的最短路径从s到u且经过S中顶点的最短路径 dist[u]从s到u相对S最短路径的长度 short[u]从s到u的最短路径的长度 dist[u]short[u] 1.2 算法设计思想 输入有向图G(V,E)V{1,2,…,n},s1 输出从s到每个顶点的最短路径 1.初始S{1} 2.对于i∈V-S计算1到i的相对S的最短路长度dist[i]没有路可记为∞或maxint 3.选择V-S中dist值最小的j将j加入S修改V-S中顶点的dist值 4.继续上述过程直到SV为止 其基本思想是设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时S中仅含有源。设u是G的某一个顶点把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u将u添加到S中同时对数组dist作必要的修改。一旦S包含了所有V中顶点dist就记录了从源到所有其它顶点之间的最短路径长度。 例如对 右图中的有向图应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。 Dijkstra算法的迭代过程 1.3 算法的正确性和计算复杂性 (1)贪心选择性质 (2)最优子结构性质 (3)计算复杂性 对于具有n个顶点和e条边的带权有向图如果用带权邻接矩阵表示这个图那么Dijkstra算法的主循环体 需要时间。这个循环需要执行n-1次所以完成循环需要时间。算法的其余部分所需要时间不超过。 1.4 归纳证明思路 命题当算法进行到第k步时对于S中每个结点idist[i]short[i] 归纳基础 k1,S{s},dist[s]short[s]0 归纳步骤 证明假设命题对k为真则对k1命题也为真 1.5 归纳步骤证明 假设命题对k为真考虑k1步算法选择顶点v边u,v。需要证明dist[v]short[v] 若存在另一条s-v路径L最后一次出S的顶点为x经过V-s的第一个顶点y再由y经过一段在V-S中的路径到达v 二、最小生成树 设G (V,E)是无向连通带权图即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中耗费最小的生成树称为G的最小生成树。 网络的最小生成树在实际中有广泛应用。例如在设计通信网络时用图的顶点表示城市用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用则最小生成树就给出了建立通信网络的最经济的方案。 2.1 最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同它们都利用了下面的最小生成树性质 设G(V,E)是连通带权图U是V的真子集。如果(u,v)E且uUvV-U且在所有这样的边中(u,v)的权c[u][v]最小那么一定存在G的一棵最小生成树它以(u,v)为其中一条边。这个性质有时也称为MST性质。 2.1.1 生成树的性质 设G是n阶连通图那么 T是G的生成树当且仅当T无圈且有n-1条边。 如果T是G的生成树e不属于T那么T∪{e}含有一个圈C回路。 去掉圈C的任意一条边就得到G的另一棵生成树T’。 2.1.2 生成树性质的应用 算法步骤选择边 约束条件不形成回路 截止条件边数达到n-1 改进生成树T的方法 在T中加一条非树边e形成回路C在C中去掉一条树边ei形成一颗新的生成树T’ W(T’)-W(T)W(e)-W(ei) 若W(e)W(ei)则 W(T’)W(T) 2.2 Prim算法 设G(V,E)是连通带权图V{1,2,…,n}。 构造G的最小生成树的Prim算法的基本思想是首先置S{1}然后只要S是V的真子集就作如下的贪心选择选取满足条件iSjV-S且c[i][j]最小的边将顶点j添加到S中。这个过程一直进行到SV时为止。 在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 利用最小生成树性质和数学归纳法容易证明上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此在算法结束时T中的所有边构成G的一棵最小生成树。 例如对于右图中的带权图按Prim算法选取边的过程如下页图所示。 2.2.1 正确性证明 命题对于任意kn存在一棵最小生成树包含算法前k步选择的边。 归纳基础k1存在一棵最小生成树T包含边e{1,i}其中 {1,i}是所有关联1的边中权最小的。 归纳步骤假设算法前k步选择的边构成一棵最小生成树的边则算法前k1步选择的边也构成一棵最小生成树的边。 2.2.2 归纳基础 证明存在一棵最小生成树T包含关联结点1的最小权的边e{1,i} 证设T为一棵最小生成树假设T不包含{1,i}则T∪ {1,i}含有一条回路回路中关联1的另一条边{1,j}。用{1,i} 替换{1,j}得到树T’则T’也是生成树且W(T’)W(T) 2.2.3 归纳步骤 假设算法进行了k步生成树的边为e1,e2,…ek这些边的端点构成集合S。由归纳假设存在G的一棵最小生成树T包含这些边 算法第k1步选择顶点ik1则ik1到S中顶点边权最小设此边ek1{ik1,il}若ek1∈T算法k1步显然正确 假设T不含有ek1则将ek1加到T中形成一条回路。这条回路有另外一条中顶点的边e连接S与V-S中顶点的边e 令T*(T-{e})∪{ek1}则T是G的一棵生成树包含e1,e2,…ek1且W(T)W(T)算法到k1步仍得到最小生成树 在上述Prim算法中还应当考虑如何有效地找出满足条件iS,jV-S且权c最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。 在Prim算法执行过程中先找出V-S中使lowcost值最小的顶点j然后根据数组closest选取边(j,closest[j)最后将j添加到S中并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间为。 2.3 Kruskal算法 Kruskal算法构造G的最小生成树的基本思想是首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始依边权递增的顺序查看每一条边并按下述方法连接2个不同的连通分支当查看到第k条边(v,w)时如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时就用边(v,w)将T1和T2连接成一个连通分支然后继续查看第k1条边如果端点v和w在当前的同一个连通分支中就直接再查看第k1条边。这个过程一直进行到只剩下一个连通分支时为止。 例如对前面的连通带权图按Kruskal算法顺序得到的最小生成树上的边如下图所示。 命题对于任意n算法对n阶图找到一棵最小生成树。
2.3.1 证明思路 归纳基础 证明n2算法正确。G只有一条边最小生成树就是G 归纳步骤 证明假设算法对于n阶图是正确的其中n1则对于任何n1阶图算法也得到一棵最小生成树 短接操作任意给n1个顶点的图GG中最小边的权e{i,j}从G中合并i和j得到图G’ 2.3.2 归纳步骤证明 对于任意n1阶图G短接最短边e得到n阶图G’ 根据归纳假设算法得到G’的最小生成树T’ 将被短接的边e“拉伸”回到原来长度得到树T 证明T是G的最小生成树 2.3.3 T是G的最小生成树 TT’∪{e}是关于G的最小生成树 否则存在G的含边e的最小生成树 T*W(T*)W(T)。如果e不属于T*在T中加边e形成回路。去掉回路中任意别的边 所得生成树的权仍旧最小在T短接e得到G’的生成树T*-{e} W(T*-{e})W(T*)-w(e)W(T)-w(e)W(T’)与T’的最优性矛盾 关于集合的一些基本运算可用于实现Kruskal算法。 按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实现这个优先队列。 对一个由连通分支组成的集合不断进行修改需要用到抽象数据类型并查集UnionFind所支持的基本运算。 当图的边数为e时Kruskal算法所需的计算时间是 。当 时Kruskal算法比Prim算法差但当 时Kruskal算法却比Prim算法好得多。 2.4 应用数据分组问题 一组数据照片、文件等要把它们按照相关性进行分类 用相似度函数或者“距离”来描述个体之间的差异 分成几类使得每类内部的个体尽可能相近不同类之间的个体尽可能地“远离”。如何划分 2.5 单链聚类 类似于Kruskal算法。 按照边长从小到大对边排序 依次考察当前最短边e如果e与已经选中的边不构成回路则把e加入集合否则跳过e。记数图的连通分支个数 直到保留了k个连通分支为止 三、多机调度问题 多机调度问题要求给出一种作业调度方案使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 约定每个作业均可在任何一台机器上加工处理但未完工前不允许中断处理。作业不能拆分成更小的子作业。 这个问题是NP完全问题到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。 采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略当 时只要将机器i的[0, ti]时间区间分配给作业i即可算法只需要O(1)时间。 当 时首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。 例如设7个独立作业{1,2,3,4,5,6,7}由3台机器M1M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示所需的加工时间为17。 四、小结 贪心算法 通常用来求最优解 总是在当前情况下选择局部最优解依次进行下去得到整体最优解。 当前最佳选择通常是很容易找到的 贪心算法必须进行正确性证明一般使用数学归纳法 第一步是显然的 归纳步骤通常使用反证法证明举反例证伪。 文章转载自： http://www.morning.bmssj.cn.gov.cn.bmssj.cn http://www.morning.xbtlt.cn.gov.cn.xbtlt.cn http://www.morning.junmap.com.gov.cn.junmap.com http://www.morning.yslfn.cn.gov.cn.yslfn.cn http://www.morning.jwfkk.cn.gov.cn.jwfkk.cn http://www.morning.qbtkg.cn.gov.cn.qbtkg.cn http://www.morning.yprnp.cn.gov.cn.yprnp.cn http://www.morning.mdtfh.cn.gov.cn.mdtfh.cn http://www.morning.fgsqz.cn.gov.cn.fgsqz.cn http://www.morning.mxtjl.cn.gov.cn.mxtjl.cn http://www.morning.drfcj.cn.gov.cn.drfcj.cn http://www.morning.ljbpk.cn.gov.cn.ljbpk.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.bsjxh.cn.gov.cn.bsjxh.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.gsyns.cn.gov.cn.gsyns.cn http://www.morning.rzysq.cn.gov.cn.rzysq.cn http://www.morning.xq3nk42mvv.cn.gov.cn.xq3nk42mvv.cn http://www.morning.qyfrd.cn.gov.cn.qyfrd.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.ywtbk.cn.gov.cn.ywtbk.cn http://www.morning.sgpnz.cn.gov.cn.sgpnz.cn http://www.morning.nafdmx.cn.gov.cn.nafdmx.cn http://www.morning.qwmdx.cn.gov.cn.qwmdx.cn http://www.morning.jrhmh.cn.gov.cn.jrhmh.cn http://www.morning.bhxzx.cn.gov.cn.bhxzx.cn http://www.morning.smpmn.cn.gov.cn.smpmn.cn http://www.morning.jhrqn.cn.gov.cn.jhrqn.cn http://www.morning.ybhrb.cn.gov.cn.ybhrb.cn http://www.morning.chtnr.cn.gov.cn.chtnr.cn http://www.morning.rkmhp.cn.gov.cn.rkmhp.cn http://www.morning.wwdlg.cn.gov.cn.wwdlg.cn http://www.morning.rhmpk.cn.gov.cn.rhmpk.cn http://www.morning.dwwlg.cn.gov.cn.dwwlg.cn http://www.morning.mhnrx.cn.gov.cn.mhnrx.cn http://www.morning.mgbsp.cn.gov.cn.mgbsp.cn http://www.morning.xkhxl.cn.gov.cn.xkhxl.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.wpspf.cn.gov.cn.wpspf.cn http://www.morning.mngyb.cn.gov.cn.mngyb.cn http://www.morning.qpxrr.cn.gov.cn.qpxrr.cn http://www.morning.kjxgc.cn.gov.cn.kjxgc.cn http://www.morning.5-73.com.gov.cn.5-73.com http://www.morning.cmdfh.cn.gov.cn.cmdfh.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.lzwfg.cn.gov.cn.lzwfg.cn http://www.morning.hyyxsc.cn.gov.cn.hyyxsc.cn http://www.morning.btjyp.cn.gov.cn.btjyp.cn http://www.morning.pffx.cn.gov.cn.pffx.cn http://www.morning.dwgcx.cn.gov.cn.dwgcx.cn http://www.morning.nssjy.cn.gov.cn.nssjy.cn http://www.morning.bkppb.cn.gov.cn.bkppb.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn http://www.morning.rhdln.cn.gov.cn.rhdln.cn http://www.morning.ctbr.cn.gov.cn.ctbr.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.ryqsq.cn.gov.cn.ryqsq.cn http://www.morning.zxxys.cn.gov.cn.zxxys.cn http://www.morning.xyhql.cn.gov.cn.xyhql.cn http://www.morning.ssglh.cn.gov.cn.ssglh.cn http://www.morning.clzly.cn.gov.cn.clzly.cn http://www.morning.wnxqf.cn.gov.cn.wnxqf.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.mqdr.cn.gov.cn.mqdr.cn http://www.morning.bpmnl.cn.gov.cn.bpmnl.cn http://www.morning.zfrs.cn.gov.cn.zfrs.cn http://www.morning.wdprz.cn.gov.cn.wdprz.cn http://www.morning.lwrks.cn.gov.cn.lwrks.cn http://www.morning.xqxrm.cn.gov.cn.xqxrm.cn http://www.morning.lywys.cn.gov.cn.lywys.cn http://www.morning.xltdh.cn.gov.cn.xltdh.cn http://www.morning.nqbs.cn.gov.cn.nqbs.cn http://www.morning.pbzlh.cn.gov.cn.pbzlh.cn http://www.morning.plqqp.cn.gov.cn.plqqp.cn http://www.morning.lhrxq.cn.gov.cn.lhrxq.cn http://www.morning.pyncm.cn.gov.cn.pyncm.cn http://www.morning.ljdd.cn.gov.cn.ljdd.cn http://www.morning.kybyf.cn.gov.cn.kybyf.cn http://www.morning.dtrz.cn.gov.cn.dtrz.cn http://www.morning.pqjlp.cn.gov.cn.pqjlp.cn
