北京大学屈婉玲算法设计与分析最新课件0r4

第4章贪心法（Greedy Approach）4.1 贪心法的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 思想4.2贪心法的正确性证明4.2贪心法的正确性证明4.3对贪心法得不到最优解情况的处理44贪心法的典型应用4.4贪心法的典型应用4.4.1最优前缀码4.4.2最小生成树4.4.3单源最短路径4.4.3单源最短路径14.1贪心法的设计思想活动选择问题输入：S={12n}为n项活动的集合，sifi分别为活动i输入：S{1,2,…,n}为n项活动的集合，si,fi分别为活动i的开始和结束时间，活动i与j相容⇔si≥fj或sj≥fi.求：最大的两两相容的活动集A求：最大的两两相容的活动集A实例i12345678910si1325456882fi45679910111213策略1：排序使得s1≤s2≤…≤sn，从前向后挑选策略2排序使得fs≤fs≤≤fs从前向后挑选策略2：排序使得f1－s1≤f2－s2≤…≤fn－sn，从前向后挑选策略3：排序使得f1≤f2≤…≤fn，从前向后挑选2以上策略中的挑选都要注意满足相容性条件两个反例策略1：S={1,2,3}，s1=0,f1=20,s2=2,f2=5,s3=8,f3=15策略2：S={1,2,3}，s1=0,f1=8,s2=7,f2=9,s3=8,f3=152310258101520231310258101520贪心算法算法GreedySelect输入：活动集S，s，fi=12n，且f≤≤f输入：活动集S，si，fi,i=1,2,…,n，且f1≤…≤fn输出：A⊆S，选中的活动子集1n←length[S]//活动个数1.n←length[S]//活动个数2.A←{1}3j←1//已选入的最后一个活动的标号3.j←1//已选入的最后个活动的标号4.fori←2tondo5ifs≥f//判断相容性5.ifsi≥fj//判断相容性6.thenA←A∪{i}7j←i7.j←i8.returnA4最后完成时间t=max{fk:k∈A}算法运行实例输入：S={1,2,…,10}i12345678910s1305356882si1305356882fi45678910111213解:A={1,4,8},t=11时间复杂度排序活动选择问题如何该算法对所有的实例都能得到确的解时间复杂度：排序+活动选择=O(nlogn)+O(n)=O(nlogn)问题：如何证明该算法对所有的实例都能得到正确的解？5算法的正确性证明定理1算法Select执行到第k步,选择k项活动i1=1,i2,…,i那么存在最优解A包含i1iiik,那么存在最优解A包含i1=1,i2,…,ik根据定理：算法至多到第n步得到最优解证：S={1,2,…,n}是活动集，且f1≤…≤fn归纳基础：k=1,证明存在最优解包含活动1任取最优解A,A中的活动按截止时间递增排列.如果A的第,截一个活动为j，j≠1,令A’=(A−{j})∪{1},由于f1≤fj,A’也是最优解，且含有1.6算法正确性证明（续）归纳步骤：假设命题对k为真,证明对k+1也为真.算法执行到第k步选择了活动i1ii根据归纳假设算法执行到第k步,选择了活动i1=1,i2,…,ik,根据归纳假设存在最优解A包含i1=1,i2,…,ik,A中剩下的活动选自集合S’={i|i∈Ssi≥fk}且A中剩下的活动选自集合S{i|i∈S,si≥fk},且A={i1,i2,…,ik}∪BB是S’的最优解.（若不然,S’的最优解为B*,B*的活动比B多，那么B*∪{1,i2,…,ik}是S的最优解，且比A的活动多,与A的最优性矛盾.）根据归纳基础存在S’的最优解B’含有S’中的第个活动}){'(}{'}{iBiiiiBiii根据归纳基础，存在S’的最优解B’含有S’中的第一个活动，即ik+1,且|B’|=|B|,于是}){'(},,...,{'},...,,{112121++−∪=∪kkkkiBiiiiBiii也是原问题的最优解.7贪心算法的特点设计要素：(1)贪心法适用于组合优化问题，该问题满足优化原则.(2)求解过程是多步判断过程，最终的判断序列对应于问题的最优解.(3)判断依据某种“短视的”贪心选择性质，性质的好坏决()定了算法的成败.(4)贪心法必须进行正确性证明()贪法须行确性明贪心法的优势：算法简单时间和空间复杂性低算法简单，时间和空间复杂性低84.2贪心法的正确性证明数学归纳法个描算法算法1.叙述一个描述算法正确性的命题P(n)，n为算法步数或者问题规模2归纳基础P(1)或P()为真为某个自然数2.归纳基础：P(1)或P(n0)为真,n0为某个自然数3.归纳步骤：P(k)⇒P(k+1)第一数学归纳法∀k(k<)P(k)⇒P()第二数学归纳法∀k(k<n)P(k)⇒P(n)第二数学归纳法交换论证 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法的解的结构特1.分析算法的解的结构特征2.从一个最优解逐步进行结构变换(替换成分、交换次序等)3证明上述变换最终得到算法的解变换有限步结束变3.证明上述变换最终得到算法的解、变换有限步结束、变换保持最优性不降低、9最优装载Loading问题：gn个集装箱1,2,…,n装上轮船，集装箱i的重量wi,轮船装载重量限制为C，无体积限制.问如何装使得上船的集装nma∑箱最多？不妨设wi≤c.xniimax1∑=Cxwinii1≤∑=nixi,...,2,11,0==贪心法将集装箱按照从轻到重排序轻者先装10贪心法：将集装箱按照从轻到重排序，轻者先装正确性证明命题：对装载问题任何规模为n的输入，算法得到最优解.对问题规模归纳设集装箱从轻到重记为对问题规模归纳，设集装箱从轻到重记为1,2,…,n.证：k=1,只有1个箱子，算法显然正确.假设对于k个集装箱的输入，贪心法都可以得到最优解，考虑输入N={1,2,…,k+1},其中w1≤w2≤…≤wk+1.k由归纳假设，对于N’={2,3,…,k+1}，C’=C−w1,贪心法得到最优解I’.令I={1}∪I’，则I(算法解)是关于N的最优解.若不然，存在包含1的关于N的最优解I*（如果I*中没有1，用1替换I*中的第一个元素得到的解也是最优解），且|I*|>|I|；那么I*−{1}是N’的解且|I*−{1}|>|I−{1}|=|I’|与I’的最优性矛盾11与I’的最优性矛盾.最小延迟调度问题：给定客户集合A，∀i∈A，ti为服务时间，di为完成时间，ti,di为正整数.一个调度f:A→N，f(i)为客户i的开始时间.求ff最大延迟达到最小的调度，即求f使得}})({max{miniiAifdtif−+∈)()(or)()(,,,iftjfjftifjiAjiji≤+≤+≠∈∀12实例A={1,2,3,4,5},T=<5,8,4,10,3>,D=<10,12,15,11,20>调度1：f1(1)=0,f1(2)=5,f1(3)=13,f1(4)=17,f1(5)=27各任务延迟：0,1,2,16,10;最大延迟：1651317273012345调度2：f(1)=0f(2)=15f(3)=23f(4)=5f(5)=27调度2：f2(1)0,f2(2)15,f2(3)23,f2(4)5,f2(5)27各任务延迟：0,11,12,4,10;最大延迟：12515232730142355152327301314235贪心策略选择贪心策略1：按照ti从小到大安排任务i贪心策略2：按照di−ti从小到大安排任务贪心策略3：按照di从小到大安排任务贪策略按照i从小到大安任务策略1对某些实例得不到最优解. 反例反例：t1=1,d1=100,t2=10,d2=10策略2对某些实例得不到最优解.策略2对某些实例得不到最优解. 反例：t1=1,d1=2,t2=10,d2=1014算法设计算法Schedule输入ATD输入：A,T,D输出：f1排序A使得d≤d≤≤d1.排序A使得d1≤d2≤…≤dn2.f(1)←03i23.i←23.whilei≤ndo4f(i)f(i1)//任务i1结束时刻是任务i开始时刻4.f(i)←f(i−1)+ti−1//任务i-1结束时刻是任务i开始时刻5.i←i+1设计思想：按完成时间从早到晚安排任务，没有空闲15交换论证：正确性证明算法的解的性质：(1)没有空闲时间没有逆序(1)没有空闲时间,没有逆序.(2)逆序(i,j):f(i)<f(j)且di>dj引所有没有逆序没有空闲时间的调度具有相同的最引理1所有没有逆序、没有空闲时间的调度具有相同的最大延迟.证:设f没有逆序，在f中具有相同完成时间的客户i1,i2,…,ik必被连续安排.在这k个客户中最大延迟是最后一个客…,ik必被连续安排在这个客户中最大延迟是最后个客户，被延迟的时间是dttki−+∑0与i1i2ik的排列次序无关dttjij+∑=1016与i1,i2,…,ik的排列次序无关.交换论证证明思想：从一个没有空闲时间的最优解出发，在不改变最优性的条件下转变成没有逆序的解根据引理改变最优性的条件下，转变成没有逆序的解. 根据引理1，这个解和算法的解具有相同的最大延迟. 证明要点相邻逆序的存在性如果个最优调度存在逆序那么(1)相邻逆序的存在性：如果一个最优调度存在逆序，那么存在i<n使得(i,i+1)构成一个逆序.(2)交换相邻的逆序i和j，得到的解的调度仍旧最优.(3)每次交换后逆序数减1，至多经过n(n−1)/2次交换得到()每次交换后序数减多()次交换得到一个没有逆序的最优调度.17交换相邻逆序(i,j)不影响最优性(1)交换i,j对其他客户的延迟时间没影响(2)交换后不增加j的延迟(2)交换后不增加j的延迟(3)i在f’的延迟delay(f’,i)小于j在f的延迟delay(f,j),因此小于f的最大延迟r因此小于f的最大延迟rf1(i)=sf1(j)=s+tif1(j)+tj=s+ti+tjjiijdl(f’i)＋ddl(fj)f2(j)=sf2(i)=s+tjf2(i)+ti=s+tj+tiijdelay(f’,i)=s＋tj+ti－di<delya(f,j)≤rdelay(f,j)＝s+ti+tj－djdj<di⇒L2i<L1j184.3得不到最优解的处理方法讨论对于哪些输入贪心法能得到最优解：输入条件讨论贪心法的解最坏情况下与最优解的误差（见第8章）讨论贪心法的解最坏情况下与最优解的误差（见第8章）找零钱问题找零钱问题设有n种零钱，重量分别为w1,w2,...,wn,价值分别为v1=1,v2,...,vn.需要付的总钱数是y.不妨设币值和钱数都为v11,v2,...,vn.需要付的总钱数是y.不妨设币值和钱数都为正整数.问：如何付钱使得所付钱的总重最轻?令选用第i种硬币的数目是i12令选用第i种硬币的数目是xi，i=1,2,…,nxwnii}min{∑nixyxvxwniii12N}min{1∈∑∑=19nixyxviiii1,2,...,N,,1=∈=∑=动态规划算法属于整数规划问题，动态规划算法可以得到最优解设Fk(y)表示用前k种零钱，总钱数为y的最小重量递推方程xwxvyFyFkkkkkk11111})({min)(+−=++++⎥⎢+递推方程kkkkkvyxkkk11110111++++⎥⎦⎥⎢⎣⎢≤≤+++ywvywyF1111)(=⎥⎦⎥⎢⎣⎢=v1⎦⎣20Greedy算法nwww≥≥≥21假设ynnvvv≥≥≥...2211假设使用前k种零钱，总钱数为y贪心法的总重为Gk(y)，则有如下递推方程kvyGywyGkkkk1111)mod()(>+⎥⎥⎢⎢=kvyGvwyGkkkkk11111)mod()(⎥⎢>+⎥⎦⎢⎣++++ywvywyG1111)(=⎥⎦⎥⎢⎣⎢=21n=1,2贪心法得到最优解,n=1只有一种零钱，F1(y)=G1(y)，F2(y)=G2(y)n=2,使用价值大的钱越多(x2越大)，得到的解越好})({min)(222212xwxvyFyF+−=)]())(([+++xwxvyFδδ⎣⎦})({min)(22221/0222xwxvyFyFvyx+≤≤])([)]())(([2222122221+−−+++−xwxvyFxwxvyFδδ])([])([222212222221+−−++−−=xwxvywwxwvxvywδδ0)(])([22122122221≤+−=+−=wvwwvwyδδδ22n>2得到最优解的判定条件定理4.5对每个正整数k，假设对所有非负整数y有Gk(y)=Fk(y)，那么G()≤G()F()G()那么Gk+1(y)≤Gk(y)⇔Fk+1(y)=Gk+1(y)定理4.6对每个正整数k，假设对所有非负整数y有Gk(y)=Fk(y)定理4.6对每个正整数k，假设对所有非负整数y有Gk(y)Fk(y)且存在p和δ满足vk+1=pvk－δ,其中0≤δ<vk，vk≤vk+1,p为正整数，vk+1pvkδ,其中0≤δ<vk，vk≤vk+1,p为正整数，则下面的命题等价：(1)G(y)=F(y)对一切正整数y；(1)Gk+1(y)Fk+1(y)对切正整数y；(2)Gk+1(pvk)=Fk+1(pvk)；(3)w+G(δ)≤pw条件(3)需O(k)时间验证Gk+1(y)=Fk+1(y),整个验证时间O(n2)(3)wk+1+Gk(δ)≤pwk.23kkkGpvpvv∈<≤−=++)(Z,0,1δδδ实例例v=1v=5v=14v=18w=1i=1234kkkpwGw≤++)(1δ例v1=1,v2=5,v3=14,v4=18,wi=1,i=1,2,3,4.对一切y有G1(y)=F1(y),G2(y)=F2(y).验证G3(y)=F3(y)v=pvδ⇒p=2δ=10δ3δ1v4=pv3−δ⇒p=2,δ=10w4+G3(δ)=1+2=3v3=pv2－δ⇒p=3,δ=1.w3+G2(δ)=1+1=2pw3=2×1=2w4+G3(δ)>pw3pw2=3×1=3w3+G2(δ)≤pw2结论：G3(y)=F3(y),对于y=pv3=28，G4(y)>F4(y)244.4贪心法的典型应用4.4.1最优前缀码二元前缀码用0-1字符串作为代码表示字符， 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 任何字符的代码都不能作为其它字符代码的前缀非前缀码的例子非前缀码的例子a:001,b:00,c:010,d:01解码的歧义，例如字符串0100001解码1:01,00,001d,b,a解码2:010,00,01c,b,d25前缀码的二叉树及权值前缀码：{00000,00001,0001,001,01,100,101,11}频率:00000:5%,000001:5%,0001:10%,001:15%,,,,,01:25%,100:10%,101:10%,11:20%平均的二进制位数平均的二进制位数)()(1∑=niiixdxfBB=[(5+5)×5+10×4+(15+10+10)×31=i+(15+10+10)×3+(25+20)×2]/100285=2.85最优前缀码权值B最小权值B最小最优前缀码问题问题：给定字符集C={x1,x2,…,xn}和每个字符的频率f(xi),i=12n求关于C的一个最优前缀码i=1,2,…,n,求关于C的个最优前缀码.算法Huffman(C)输入：C={xxx}f(x)i=12n输入：C={x1,x2,…,xn}，f(xi),i=1,2,…,n.输出：Q//队列1.n←|C|||2.Q←C//按频率递增构成队列Q3.fori←1ton−1do生成结点4.z←Allocate-Node()//生成结点z5.z.left←Q中最小元//取出Q最小元作z的左儿子6zright←Q中最小元//取出Q最小元作z的右儿子6.z.right←Q中最小元//取出Q最小元作z的右儿子7.f(z)←f(x)+f(y)8.Insert(Q,z)//将z插入Q(Q,)Q9.returnQ实例例如100例如a:45,b:13;c:12;d:16;e:9;f:555a45;;f编码：f0000e0001253045f--0000,e--0001,d--001,c--010,b011a114dcb161213平均位数b—011,a--1fe161213平均位数：4×(0.05+0.09)3(016012013)10452245928+3×(0.16+0.12+0.13)+1×0.45=2.24算法正确性证明:引理1引理1:设C是字符集，∀c∈C,f(c)为频率，x,y∈C,f(x),f(y)频率最小那么存在最优元前缀码使得的码字等长频率最小，那么存在最优二元前缀码使得x,y的码字等长，且仅在最后一位不同.T→T’f[x]≤f[a]xaf[]f[]f[y]≤f[b]a与x交换与交换ybxbxya则与的权之差为b与y交换abTxyT’则T与T’的权之差为∑∑≥−=−∈∈CiCiTTidifidifTBTB0)(][)(][)'()('29其中dT(i)为i在T中的层数（i到根的距离）引理2引理设T是二元前缀码所对应的二叉树，∀x,y∈T,x,y是树叶兄弟z是xy的父亲令T’=T−{xy}且令z的频率树叶兄弟，z是x,y的父亲，令T=T−{x,y},且令z的频率f(z)=f(x)+f(y)，T’是对应于二元前缀码C’=(C−{x,y})∪{z}的二叉树那么的二叉树，那么B(T)=B(T’)+f(x)+f(y).证∀c∈C−{x,y},有dT(c)=dT’(c)⇒f(c)dT(c)=f(c)dT’(c)dT(x)=dT(y)=dT’(z)+1.)()()()()()()()()(,,ydyfxdxfidifidifTBTTyxiTiTTiT++==∑∑≠∈∈))()(()()()()(',''yfxfzdzfidifTziTiT+++=∑≠∈30)()()'(yfxfTB++=证明：归纳法定理Haffman算法对任意规模为n（n≥2）的字符集C都得到关于C的最优前缀码的二叉树到关于C的最优前缀码的二叉树.归纳基础n=2，字符集C={x1,x2}，Huffman算法得到的代码12是0和1，是最优前缀码.归纳步骤假设Huffman算法对于规模为k的字符集都得到最优前缀码.考虑规模为k+1的字符集C={x1,x2,...,xk+1},其中x1,x2∈C是频率最小的两个字符.令C’=(C－{x1,x2})∪{z}，f(z)=f(x1)+f(x2)根据归纳假设，Huffman算法得到一棵关于字符集C’、频率f(z)和f(xi)（i=3,4,...,k+1）的最优前缀码的二叉树T’.31证明：归纳法(续)把x1和x2作为z的儿子附加到T’上，得到树T，那么T是关于字符集C=(C’－{z})∪{x1,x2}的最优前缀码的二叉树.()字符集C(C{z}){1,2}的最优前缀码的叉树如若不然，存在更优的树T*.根据引理1，其最深层树叶是x1,x2，且B(T*)<B(T).去掉T*中的x1和x2，根据引理2，所得x1,x2，且B(T)B(T).去掉T中的x1和x2，根据引理2，所得二叉树T*’满足B(T*’)＝B(T*)－(f(x1)+f(x2))<B(T)－(f(x1)+f(x2))=B(T’)()()(f(1)f(2))()(f(1)f(2))()与T’是一棵关于C’的最优前缀码的二叉树矛盾.zzz32T’x2x1THuffman树应用:文件归并问题：给定一组不同长度的排好序文件构成的集合S={f1f}S{f1,…,fn}其中fi表示第i个文件含有的项数.使用二分归并将这些文件归并成一个有序的文件归并成个有序的文件. 归并过程对应于二叉树：文件为树叶.fi与fj归并的文件是它们的父结点.归并代价(最多的比较次数)：结点fi与fj归并代价为fi+fj−1.归并代价(最多的比较次数)：结点fi与fj归并代价为fifj1.总的代价：每个文件(树叶)的深度乘以文件大小之和再减掉归并次数n−1归并次数n1)1()(−−∑nfidiSi33∈Si实例实例192实例：S={21,10,32,41,18,70}881927311919231701873881042128703241493210214121281810顺序归并Huffman树归并代价代价顺序归并：(21+10+32+41)×3+(18+70)×2−5=483Huffman树归并：(10+18)×4+21×3+(70+41+32)×25=45634Huffman树归并：(10+18)×4+21×3+(70+41+32)×2−5=4564.4.2最小生成树无向连通带权图G=(V,E,W)，w(e)∈W是边e的权.G的一棵小成树生成树是包含了G的所有顶点的树,树中各边的权之和称为树的权，具有最小权的生成树称为G的最小生成树.树的权具有最小权的成树称为的最小成树命题4.1设G是n阶连通图，那么是的生成树当且仅当有条边(1)T是G的生成树当且仅当T有n－1条边.(2)如果T是G的生成树，e∉T，那么T∪{e}含有一个圈(回路路).问题：给定连通带权图G，求G的一棵最小生成树问题：给定连通带权图G，求G的棵最小生成树.算法：Prim算法和Kruskal算法35Prim算法算法Prim(G,E,W)1．S←{1}1．S←{1}2．whileV−S≠∅do3．从V−S中选择j使得j到S中顶点的边权最小3．从VS中选择j使得j到S中顶点的边权最小4．S←S∪{j}16151615124315524361553425663425663426566正确性证明对步数归纳定理对于任意k<存在棵最小生成树包含算法前k步定理：对于任意k<n,存在一棵最小生成树包含算法前k步选择的边归纳基础：k=1,存在一棵最小生成树T包含边e={1,i},其中{1,i}是所有关联1的边中权最小的.设为棵最小生成树假设不包含{1i}则{{1i}}含有设T为一棵最小生成树，假设T不包含{1,i},则T∪{{1,i}}含有一条回路，回路中关联1的另条边为{1j}11联1的另一条边为{1,j}，令T’=(T-{{1,j}})∪{{1,i}}，则T’也是生成树jiji则T也是生成树，且W(T’)≤W(T).37TT’正确性证明(续)归纳步骤：假设算法进行了k−1步，生成树的边为e1,e2,…,ek1,这些边假设算法进行了步成树的边为1,2,,k−1,边的k个端点构成集合S.由归纳假设存在G的一棵最小生成树T包含这些边.算法第k步选择了顶点ik+1,则ik+1到S中顶点的边权最小,设这条边为e={ii}假设T不含有e则将e加到T中形成这条边为ek={ik+1,il}.假设T不含有ek，则将ek加到T中形成一条回路.这条回路有另外一条连接S与V−S中顶点的边e,令T*=(T{e})∪{e}T*=(T−{e})∪{ek}，则T*是G的一棵生成树，包含eeeW(T*)≤W(T)Sileke含e1,e2,…,ek,W(T)≤W(T).算法时间：T(n)=O(n2)V-Sik+138Kruskal算法算法4.6Kruskal输入连通图顶点数边数算输入：连通图G//顶点数n，边数m输出：G的最小生成树按权小大排序中的边使得1.按权从小到大排序G中的边，使得E={e1,e2,…,em}2.T←∅3．repeat4.e←E中的最短边5．ife的两端点不在同一个连通分支6.thenT←T∪{e}7.E←E－{e}8.untilT包含了n－1条边39实例11161555615552435635422435635423425636256362656640Kruskal算法正确性证明命题：对于任意n>1,算法对n阶图得到一棵最小生成树.证明n=2,只有一条边，命题显然为真.假设对于n个顶点的图算法正确，考虑n+1个顶点的图G,G中最小权边e={i,j}，从G中短接i和j，得到图G’.根据归纳假设，由算法存在G’的最小生成树T’.令T=T’∪{e},则T是关于G的最小生成树.否则存在G的含边e的最小生成树T*，W(T*)<W(T).(如果e∉T*,在T*中加边e，形成回路.去掉回路中任意别的边所得生成树的权仍旧最小).在T*中短接e得到G’的生成树T*{}且树T*−{e},且W(T*−{e})=W(T*)−w(e)<W(T)−w(e)=W(T’)，与T’的最优性矛盾41与T’的最优性矛盾.算法的实现与时间复杂度数据结构：建立数组是结点的连通分支标记建立FIND数组，FIND[i]是结点i的连通分支标记.(1)初始FIND[i]=i.(2)两个连通分支合并，则将较小分支结点的FIND值更新为较大分支的标记时间复杂度：(1)每个结点至多更新logn次，建立和更新FIND数组的总时()g间为O(nlogn)(2)算法时间为()O(mlogm)+O(nlogn)+O(m)=O(mlogn)边排序FIND数组其他排序数其他4.4.3单源最短路径给定带权有向网络G=(V,E,W),每条边e=<i,j>的权w(e)为非单短路径负实数，表示从i到j的距离.源点s∈V，求从s出发到达其它结点的最短路径.Dijkstra算法：且从到的最短路径长度已知x∈S⇔x∈V且从s到x的最短路径长度已知初始：S={s}，S=V时算法结束从到相对于S的最短路径从到且仅经过S中顶点从s到u相对于S的最短路径：从s到u且仅经过S中顶点的最短路径dist[u]：从s到u的相对于S的最短路径的长度short[u]：从s到u的最短路径的长dih43dist[u]≥short[u]Dijkstra算法算法Dijkstra1S{}1.S←{s}2.dist[s]←03.fori∈V−{s}do4.dist[i]←w(s,i)//如果s到i没有边,w(s,i)=∞5.whileV−S≠∅do6.从V−S中取出具有相对S的最短路径的顶点j7.S←S∪{j};8.fori∈V−Sdo9.ifdist[j]+w(j,i)<dist[i]10.thendist[i]←dist[j]+w(j,i)//更新dist[i]44实例1013722输入：G=<V,E,W>，源点1V={123456}S={1},46336125V={1,2,3,4,5,6}S{1},dist[1]=0dist[2]=10,dist[6]=345471dist[3]=dist[4]=dist[5]=∞10137263373625S={1,6},dist[1]=0,dist[6]=3dit[2]5dit[4]9dit[5]445471dist[2]=5,dist[4]=9,dist[5]=4dist[3]=∞45实例（续）S{165}1012S={1,6,5},dist[1]=0,dist[6]=3,dist[5]=4dist[2]=5dist[4]=963373625dist[2]=5,dist[4]=9,dist[3]=∞4547611012S={1,6,5,2},dist[1]=0,dist[6]=3,dist[5]=4163373225[],[],[]dist[2]=5dist[3]=12454761dist[4]=9467实例（续）S={1,6,5,2,4},dist[1]=0dist[6]=3dist[5]=4101372dist[1]0,dist[6]3,dist[5]4dist[2]=5,dist[4]=9,dist[3]=1263373625454761S={1,6,5,2,4,3},di10di63di41012dist[1]=0,dist[6]=3,dist[5]=4dist[2]=5,dist[4]=9dist[3]=12163373225dist[3]=12解：454761解short[1]=0,short[2]=5,short[3]=12,short[4]=9，477short[5]=4,short[6]=3.算法正确性证明命题：当算法进行到第k步时，对于S中每个结点i，dist[i]=short[i]dist[i]=short[i]归纳基础k=1,S={s},dist[s]=short[s]=0,命题为真.归纳步骤假设命题对于k为真考虑k+1步选择顶点v(边归纳步骤假设命题对于k为真.考虑k+1步,选择顶点v(边{u,v}).假若存在另一条s-v路径L(绿色)，最后一次出S的顶点为x在这次从S中出来后顶点为x,在这次从S中出来后经过V−S的第一个顶点为y.xyLSdist[v]≤dist[y]//v先被选≤dist[y]+d(y,v)≤L时间复杂度T()O(2)dist[v]=short[v]su48时间复杂度T(n)=O(n2)v贪心法小结(1)适用于组合优化问题.求解过程是多步判断.判断的依据是局部最优策略，使目标值达到最大(或最小)，与前面的是局部最优策略使目标值到最大(或最小)与前面的子问题计算结果无关.(2)局部最优策略的选择是算法正确性的关键.(2)局部最优策略的选择是算法正确性的关键.(3)正确性证明方法：数学归纳法、交换论证.使用数学归纳法主要通过对算法步数或者问题规模进行归纳.如果要证法主要通过对算法步数或者问题规模进行归纳.如果要证明贪心策略是错误的，只需举出反例.(4)自顶向下求解，通过选择将问题归约为小的子问题(4)自顶向下求解，通过选择将问题归约为小的子问题.(5)如果贪心法得不到最优解，可以对问题的输入进行分析或者估计算法的近似比或者估计算法的近似比.(6)如果对原始数据排序之后，贪心法往往是一轮处理，时间复杂度和空间复杂度低49间复杂度和空间复杂度低.