算法分析与设计ss lecture7

Turing机的定义双向无限带的Turing基本模M=<,,qTuring机的定义双向无限带的Turing基本模M=<,,q0B,F其中QB有穷状态有穷带字符集输入字符集空白字符,q0初始状态qY,FF终结状态集Q×状态转移函:带B读写…B有限状态控制2瞬时描述-格局(ID)1q瞬时描述-格局(ID)1q2表示此刻Turing机的FSC处于状态q读写头指在串2的第一个字符.例如TuringM的某时刻的状态转移函数(q,xi)=带上的字x1x2xixn读写头指向xi则它的瞬间描述是x1x2...xi-1qxi...xnx1x2...xi-2pxi-1Yxi+1...表示由左边的ID一步达到右边的表示由左边的ID经有限步达到右边的3实L0n1n实L0n1n|n1设计接LTuring机如下M=,,,q0,Q={q0,q1,q2,q3,qY,qN={0,={0,1,X,Y,BF={qY初始将字符串放1n方格中,FSC处在状态q0,读写指向方1.将第一个0改写X,然后带头向右扫描.遇到一个1将1改为Y然后带头向左扫描遇到第一X改为向右扫描这时进入下一个巡回.每个巡回01改为Y直到接受或拒斥停机4实例（续转移函数如例如输机动作如下q00011 Xq10110Y1实例（续转移函数如例如输机动作如下q00011 Xq10110Y11Y1 Y112YYXXq0YYXXYYq3501XYBTuring机接受语言被Turing机接受语言被M接受的语言记作L(M)，是*上的字的集合当这些字左端对齐1放在带上M处于q0M的带头指向1时经过有限步M将停机在接受qY即L(M)={|*,1,2*(q0*1qY2)}如果字不是L(M)中的字, M可以不停机或停机在拒斥状态Turing机可以推广k条带Turing确定型Turing机可以推广到非确定Turing6基本Turing机的变种单向无限带Turing带方格从1开始基本Turing机的变种单向无限带Turing带方格从1开始向右无限长其它与基Turing机相同多带Turingk条双向带k个读写头k为大1的常数.初始将输入写在第一条带的1n内.其它带为空.每个读写头扫描一条带,可以改写被扫描方格的字符,读写头然后向左或向右移动一个方格.读写头FSC的状态及k条带所扫描的k个字符来决定7实例例LwcwR实例例LwcwR|w为0-1字符串设计L的TuringM2M1的时间复杂度为O(nM2的空间复杂度为O(logn).当发c时第M1有2条带,c左边的w复制到第2条带上2条带的读写头向左,输入带的读写头向右.比较两个带头的符号,如果符号一样,字符个数一样,M1x.M1至多作n+1个动作时间复杂度n+1.空间复杂(n-1)/2+1.M2有2条带第2条带作为二进制的计数器首先检查输入是否只有1cc左边和右边的符号是否一样多然后逐个比较c左边和右边的字符,用上述计数器找到对应的字符.如果所有的字符都一样M2接受停机空间复杂度为二进制的计数器的占用空间,O(logn).时间复杂O(n2).8计算复计算复杂性理论空间和时间复杂度的形式定义确定型Turing计算复杂度的有关结果带压缩线性加速带数目的减9确定型Turing空间复杂度的确定型Turing空间复杂度的形式定义&$离线的Turing1条具有端记号的只读输入带k半无限存储带.如果对每个长为n的输入串,M在任一存储带上都至多S(n)那么M在最坏情况下的空间复杂度为S(n).确定型Turing机时复杂度的形式确定型Turing机时复杂度的形式定义k条双向带Turing一条带包含输入如果对于每个长为n的输入串M在停机前至多做个动作那么称M在最坏情况下的时间复杂度为两条假设：空间复杂性至少需要时间复杂性至少需要读入输入的时因此这里作如下规定对一切nS(n)1lognmax{1,logn}的缩写对一切nT(n)n+1,T(n)max{n+1,T(n)}的缩写有关计算复杂度的结果带M2模拟M1的复杂类带压有关计算复杂度的结果带M2模拟M1的复杂类带压cS(n),0<cT(n)liminfT(n) n 时间加cT(n),带数目减少空间不变带数目减少时间增加7.1P类与NP易解的问题与难解的问题排序O(nlog7.1P类与NP易解的问题与难解的问题排序O(nlogn)Dijkstra算法O(n2)，最大团回溯法用一台每秒10次的超大型计算机，上述算法的时间105log21051.7106，t=1.710-310万个数据排序1万个顶点的图的单源最短路径(104)2=108,t=0.1100个顶点的图的最大团,t=1.81032/109=1.81021秒=5.71015年,即5千7百万亿年1分钟能解多大的问题.161010次运算可给2109=20亿个数据排序用Dijkstra算法可解2.4105个顶点的图的单源最短路径问题回溯法1天只能解41个顶点的图的最大团问题算法的时间复杂度f算法的时间复杂度fg是多项式相关的如果存在多pq使得对任意nN,f(n)p(q(n))g(n)q(f(n)).例如nlognn2,n2+2n+5n10都是多项式相关的,lognn,n52n不是多项式相关的.问题的实例I的规模:I的二进制编码的长度记作定义7.1 如果存在函数f:NN使得对任意的规模为n的实例I,算法A对I的运算在f(n)步内停止,则称算法A的时复杂度多项式时间算法:以多项式为时间复杂度易解的问题:有多项式时间算法难解的问题不存在多项式时间算法几点说1当采用合理的编几点说1当采用合理的编码时输入的规模都是多项式相关的.“合理的”是指在编码中不故意使用许多冗余的字符例如设实I是一个无向简GV,EV={a,b,c,d},E={(a,b),(a,d),(b,c),(b,d),(c,d)用邻接矩阵表示e1=0101/1011/0101/1110用关联矩阵表示,编码e2=11000/10110/00101/01011/,长G有n个顶点m条边用邻接矩阵时|I|=n(n+1),用关联矩阵时|I两者多项式相关自然数应采用 (k2)进制编码不能采用一进制编码n的二进制编码有log2(n+1)位一进制编码有n位两者不是多项式相关的.几点说明时间复杂度常表成几点说明时间复杂度常表成计算对象的某些自然参数的函数，如图的顶点数或边数的函数.实例的二进制编码的长度与这自然参数通常是多项式相关的运行时间通常是计算执行的操作指令数，执行的指令数与实际运行时间是多项式相关的要求每一条指令的执行时间是固定的常数规定一个基本操作指令集，可由位逻辑运算与、或、非组成，任何可用这个基本操作指令集中常数条指令实现的操作都是合理的指令，由有限种合理的指令构成的操作指令集是合理的操作指令集.在上述约定下作指令集无关，算法是否是多项式时间的与采用的编码和操从而一个问题是易解的、还是难解的也与采用的编码和操作指令集无关易解的问题与难解的问题易解的问易解的问题与难解的问题易解的问题如排序、最小生成树、单源最短路径已证明的难解问题(1)不可计算的即根本不存在求解的算法如希尔伯特第十问题丢番图方程(有一个或几个变量的整系数方程)是否有整数解有算法但至少需要指数或更多的时间或空间，如带运算的正则表达式的全体性即任给字母表A上的带幂运问:R=A*?这个问题至少需要指数空间的正则表达式既没有找到多项式时间算法、又没能证明是难解的问题如哈密顿回路问题、货郎问题、背包问题7.1.2判定问题判定问题:答案只有两个是否7.1.2判定问题判定问题:答案只有两个是否<D,Y其中D是实例集合YD是所判定问答案为Yes的实例哈密顿回路任给无向图问G有哈密顿回路吗货郎(TSP):n个城市城市i与城j之间的正整数距离d(i,j),ij1ijn以及正整D问有一条每一个D市恰好经过一次最后回到出发点且长度不超的巡回路吗即12n的排使得d((i),(i1))d((n),(1))Di0-1背包的判定问题与优化问0-1背包的判定问题与优化问0-1背包n件物品和一个背包i的重wi,价vi1in,以及背包的重量B和价值目K,其wiviB,K均为正整数问能在背包中装入总价值不少于KB的物品吗即存在子集T{1,2使K且搜索问题、组合优化问题与判定问题的对应如果搜索问题、组合优化问题有多项式时间算法,则对应的判定问题也有多项式时间算法;通常反之亦真组合优化问题与判定问题*由组合优化问题与判定问题*由3部分组成组合优化问题(1)实例集DID*有一个有穷非空集S(I其元素称作I的可行解sS(I),有一个正整数c(s),称作s的值s*S(I),对所sS(I),当*是最()化问题时c(s*)(c(s*)c(s)s*I的最优解c(s*)I的最优值记作*对应的判定问题D,Y>定义如下DI,K|ID*KZ*其中Z*是非负整数集合.当*是最小化问题时Y={(I,K)|OPT(I)K};当*是最大化问题时Y={(IK)|OPT(I)K(nondeterministic所有多项式时间可解的判定(nondeterministic所有多项式时间可解的判定问题组成的问题类定义P类设判定问题定义=<D,Y>,如果存在两个输入变量p，对每一个实例ID,IY多项式时间算A和多项式t,|t|p(|I|A对输It输出“Yes”且仅当存在称 是多项式时间可验证的,A是IY时,tIY的证据的多项式时间验证算法由所有多项式时间可验证的判定问题组成的问题类称类TSP(货郎),0-1背包HC(哈密顿回路非确定型多项式时间算法非确定型多项式时间算法非确定型多项式时间算(1对给定的实I首先“猜想”一t|t|p(|It是否是证IY的证(2)然后检猜想和检查可以在多项式时间内完当且仅当IY时能够正确地猜想到一个证据*注：非确定型多项式时间算法不是真正的算定理 t问题多项式时间变换与NP完全性多项式时多项式时间变换与NP完全性多项式时间变换如何比较两个问题的难度定义 设判定问题1=<D1,Y1>,2=f:D1D2满足条件如果函(1)是多项式时间可计算的(2)对所ID1IY1则称f是1到2的多项式时间变换如果存12的多项式时间变换则称可多项式1间变换2,记作1p例例 HC例例 HC的每一个IG=<V,E>,TSP对应的f(I为V,任意两个不同的城市的距离uv之间若(u,v否则d(u,v)以及D|V例任给连通的无向赋权图最小生成树例任给连通的无向赋权图最小生成树以及正整B,其中权W:EZ+,问有权不超过B的生成树吗最大生成树任给连通的无向赋权图以及正整D,其中权W:EZ+,问G有权不小于D的生成树吗例 最大生成树p最小生成树证任给最大生成树的实例I:连通的无向赋权图和正整数D最小生成树的对应f(I图G=<V,E,W>和正整B=(n1)MD,其中 M=max{W(e)|eE W(e)=MW(e)如果存在G的生成树T,使W(e)(n1)MW(e)(n1)MDe反之亦然e多项式时间可计算f变换实例262633554474145317最小生变换实例262633554474145317最小生成树T’的实例G’W(T')32最大生成树的实GM8，W(T)16W'(e)(n1)MWeTp的性定理7.2pp的性定理7.2p具有传递性.即,设1p2,2p3,则1p3.i=<Di,Yii=1,2,3,fg1223的多项式时间变换.对每一个ID1,令h(I)=g(f(I)).fg的时间上界分别为pq不妨pq是单调递增的.h的步数不p(|I|输的出作为合理的指令一步只能输出长度不超过固定值字符串,|f(I)|kp(|I|于是p(|I|)+q(|f(I)|)p(|I|)+q(kp(|I得证h是多项式时间可计算的对每一个IY1f(I)Y2h(I)得证h3的多项式时间变换1p的性1p2p的性1p2,2P蕴涵1P.定理1=<D1,Y12=<D2,Y2>,f12的多项式时间变换A是计f的多项式时间算法B2的多项式时间算法.如下构造1的算C:对每一ID1,应用A得到f(I(3)C输出Yes当且仅B输出设1p2,则1是难解的蕴2是难解的推论由例7.2及最小生成树P,得知最大生成树P.由例7.1HCP.反过来HC是难解的TSP也是难解的7.2.2NP完全性如果对所有NP,p7.2.2NP完全性如果对所有NP,p则称定义7.5定理7.4推论定理7.5NP难的.推论7.3, 则是NP难的NP难的NP,NP完全的P,如果存在NP难的问题假设PNP,那么,如果是NP难的,p,如果存在NP难的问题是如果NP并且存在是NP完全的.NP完全问题p证明NP完全性的捷径证明NP;找到一个已知的NP完全问题,并证明p.Cook-Levin定理合式公Cook-Levin定理合式公式：由变元、逻辑运算符以及圆括号按照一定的规组成的表达式变元和它的否定称作文字有限个文字的析取称作简单析取式有限个简单析取式的合取称作合取范式给定每一个变元的真假值称作一个赋值如果赋t使得合式公F为真,tF的成真赋值.如果F存在成真赋值,则称F是可满足的例如F1=(x1x2)(x1x2x3)x2是一个合取范式F1是可满足的令t(x1)=1,t(x2)=0,t(x3)=1是F1的成真赋值F2=(x1x2x3)(x1x2x3x2x3不是可满足的Cook-Levin定理可满足(SAT):任给一个合取Cook-Levin定理可满足(SAT):任给一个合取范F,F是可满足的吗定理(Cook-Levin定理是NP完全的证明思想：对于任意一个NP类中语言L，存在一个接受它非确定型图灵机构造L到SAT的多项式变换对于L中的任意串x，M对x的接受计算变换成一个SAT问题的肯定实定理7.7P=NP的充分必要条件是存在NP完全问题P.7.3几个NP完全问题恰好覆最大可满足子集7.3几个NP完全问题恰好覆最大可满足子集有向双机调背独立装团最大可满足性与三元可满足性最大可最大可满足性与三元可满足性最大可满足性(MAX-任给关于变元x1,xn的简析取C1,C2,,Cm及正整K问存在x1x2,的赋值使得C1,C2,,Cm中至少有个为真吗3元合取范式每一个简单析取式恰好有3个文字的合取范式.三元可满足性(3SAT):任给一个3元合取范式F,问F是可满足的吗?子问题：设判定问题=<D,Y>,=<D,Y>,如果DD,YDY,是的特殊情况,的子问题SAT是MAX-SAT的子问题(取定理7.8MAX-SAT是NP完全3SAT是SAT的子问题定理3SAT是NP完全的7.3.2顶点覆盖、团与独立集设无7.3.2顶点覆盖、团与独立集设无向图G=<V,EVV.V是G的一个顶点覆盖 G的每一条边都至少有一个顶点在团对任u,vV且uv,都有(u,v)E.独立集对任u,vV,都有(u,v)E.中引理7.1对任意的无向图G=<V,E>和子集VV,下述命题是等价的:(1)是G的顶点覆盖VV是G的独立集VV是补Gc=<V,Ec>的团顶点覆盖、团与独立集任顶点覆盖、团与独立集任给一个无向图G=<V,E>和非负整数顶点覆盖问G有顶点数不超K的顶点覆盖吗团任给一个无向图G=<V,E>和非负整数J|V|问G有顶点数不小于J的团吗?独立集任给一个G=<V,E>和非负J|V|问G顶点数不小于的独立集吗定理定理顶点覆盖NP完全的独立集和团是NP完全的4哈密顿回路、4哈密顿回路、货郎问题与恰好覆盖有向哈密顿回路:任给有向图D,问:D中有哈密顿回路吗?定理7.12有向HC是NP完全的.定理7.13HC是NP完全的定理7.14TSP是NP完全的恰好覆盖给定有A={a1,a2,,an}和A的子集的集合{S1,S2,,Sm},问:存在子集UW使得U中子集彼此不交且它们的并集等于A? 称U是A的恰好覆盖.例如设A={1,2,3,4,5S1={1,2S2={1,3,4},S3={2,4},则{S2,S4}是A的恰好覆盖定理恰好覆盖是NP完全的子集和、背包、装箱与双机调子集和、背包、装箱与双机调度子集和:给定正整数集合X={x1,x2,,xn}及正整数N,问存X的子集T,使得T中的元素之和等于N吗装箱给定n件物品物品j的重量为正整数wj,1jn以及箱子数K.规定每只箱子装入物品的总重量不超过正整数B,问能用K只箱子装入所有的物品吗?双机调度有2台机器n项作J1,J2,,Jn,这2台机器完相同每一项作业可以在任一台机器上进行没有先后顺序Ji的处理ti1in截止时间为ti在截止时都是正整数,问能把n项作业分配给这2台机器D内完成所有的作业吗NP完全性子集和是NPNP完全性子集和是NP完全的.0-1背包是NP完全的双机调度是NP完全的装箱是NP完全的定理定理7.17定理7.18定理注意0-1背包问题优化形式的动态规划算法其时间复杂为O(nB),其中n是物品的个数,B是重量限制.这不是多项时间算法,而是指数时间算法伪多项式时间算法算法的时间|I|max(I的某个二元多p(|I|max(I))为上界,其中max(I)是实I中数的最大绝对值.NP完全性NP完全性理论的应用用NP完全性理论进行子问题分析子问题的计算复杂性子问题的NP完全性证明NP难度搜索问Turing归约NP-hard,NP-子问题的计算复子问题的计算复杂性?P努力扩大已知区域，缩小未知区当PNP时，存在不属于NPC也不属于P的问有先行约束多处理机有先行约束多处理机调度问题优化问题给定任务Tm台机器,tT,l(t)Z+,T上的偏序:T01D}满足下述条件T为可行调度tT,(t)+l(t)i,0iD,|{tT:(t)i<(t)+l(t)}|(3)t,tطt’(t)+l(t)求使D最小的可行调度条件说明任务在截止时间前完成同时工作的台数不m有偏序约束的任务必须按照约束先实112任务集如图所D最小的可行调度求使得12实112任务集如图所D最小的可行调度求使得121 判定问题实例：任务集T,m台机器,tT,l(t)判定问题实例：任务集T,m台机器,tT,l(t)Z+,T上的偏截止时问：是否存在小于等于的可行调度？子问题通过限制参数(机器数、工作时间、偏序)构成参限偏树任m大小m1,2,…,某个常数m任意l大小l为常l任意调度问题的子问题结构从上到下：偏序任意、树形偏序、无偏序约从调度问题的子问题结构从上到下：偏序任意、树形偏序、无偏序约从左到右：处理器台数限制逐步放从前到后：各任务等长工作时间、任意工作时l任意任意为树m任意搜索问题与优化问题的难度Turing归约搜索问题与优化问题的难度Turing归约设1,2是搜索问题，A是利用解2的假想子程序s解1算法，且只要s是多项式时间的，A也是多项式时间的，A是从1到2的多项式时间Turing归约.这时也称算法1Turing归约NP难度2，记1∝T2.设是搜索问题，如果存在NP完全问题’使得’T称是NP-hard.这意味着在多项式可计算的角度看，至少和NPC问题一样难.许多NP完全问题对应的优化问题都是NP-hard实例—证明NP等价例货郎问题（TSO实例—证明NP等价例货郎问题（TSO）是NP等价的证：易证TSON