算法分析解析与设计-2016-第3讲.ppt

《算法分析解析与设计-2016-第3讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计第3讲-2016山东大学上次内容：(1)5个算法设计技术，分而治之，贪心法，回溯搜索(,-删除,分支定界)，动态规划，局部搜索(2)局部搜索设计近似算法，现在也有了。(3)说明什么是好算法，什么是坏算法。多项式时间算法是好算法，指数时间算法叫坏算法。(4)许多问题设计不出多项式时间求解算法，也有很多问题能找到多项式算法，以前的算法绝大多数都是多项式时间的。告诉人们正面的东西。(5)企图把问题分类，能否分为两类，一类可以设计多项式时间算法，另一类不能设计多项式时间算法。前人建立了一种模型，说明问题很难，怎样说明。也是多年思考认识的结果。应用

2、背景：硬件测试，软件测试，知识库表达，推理SAT问题一般描述：实例：布尔变量集合：U={u1,u2,…,un}，项集合C={c1,c2,…,cm}，ck={yk1,yk2,…,ykt},ykj{u1,u2,…,un,}.询问：是否存在U的真值指派，使c1c2…cm=1，就是为真(T)，ck=yk1yk2…ykt在人工智能的搜索求解中，推理规则均采用合取范式表示。芯片测试，测试条件都表示为逻辑表达式。SatisfiabilityProblem不需要求出解来，只需要判定是或否。TSP问题：货郎问题实例：城市集合：C={c1,c2,…,cm},d(

3、ci,cj)Z+，ci,cjC，正整数K.询问：是否存在城市排列c(1),c(2),…,c(m)，使Hamilton回路问题：实例：无向简单图G=(V,E)，

4、V

5、=n。询问：是否存在V的顶点排列v(1),v(2),…,v(n)，使(v(i),v(i+1))E(G),i=1,…,n，v(n+1)=v(1)。上述三个问题均是询问解的存在性，判断是否具有满足条件的解。这三个问题都找不到多项式时间算法，但都能找到指数时间算法。什么是多项式时间？什么是指数时间？输入长度：问题实例的规模。问题的算法时间复杂性有很多，什么样的好呢？每秒1

6、百万次/运算速度T(n)问题输入长度n102030405060n0.000010.000020.000030.000040.000050.00006n20.00010.00040.00090.00160.00250.0036n30.0010.0080.0270.0640.1250.216n510.132012431.7分25.2分130分2n0.001117.9分12.7天35.7年366世纪3n0.05958分6.5年3855世纪表说明多项式时间复杂度与指数时间复杂度，区别大。主要是增长速度区别。多项式时间算法是好算法，指数时间算法是坏算法。这样的说法未

7、必绝对合理，很多人接受。从头所起，从定义图灵机开始。§3.2确定型图灵机与P类前面定义的时间复杂度概念还比较模糊，模糊就说不清楚。下面要说明什么是多项式时间可以求解的问题，实际要定义多项式时间复杂度，什么是时间复杂度，什么是空间复杂度，重新精确定义。自圆其说，说明自然界中的问题，解决问题。英文名字：DTM(1)一个硬壳存储带：一个方格存一个符号；读写头在那里，可以左右移动，一次移动一个方格。状态控制器可以读写带方格中的内容；(2)硬壳中放入数据；带上放的符号：有限个，其中包括空白符号b，={b}，是输入符号集合。符号有限个，不能无限多个。(3)有限

8、个状态；状态个数不随问题实例长度变化而变化。Q={q0,q1,q2,…,qy,qn}，q0：起始状态，qy,qn都是停机状态，qy表示停机时回答yes，qn表示停机时回答no。qf={qy,qn}q0q1qy(4)状态转换规则。什么是状态，三要素表示DTM状态：(1)q;(2)读写头指向位置;(3)带符号s，现在不关心读写头位置，只关心读写头指定带方格的符号。在造计算机时，有一个地址寄存器，即读写头。状态转换规则就是程序：(Q-{qf})Q：这是一个映射，程序语句，怎么改变状态。(qi,si)()：含义，当前状态qi，当前读写头所指方格中

9、的符号si，则下一个状态，将带方格中的符号修改为，读写头移动一个位置：={L,R,S}程序实际就是状态转换规则：初始状态q0，按照程序转换状态，到结束时状态qf，回答yes或no。我们编的程序就是告诉计算机怎样改变状态。真正实现计算机，还有很多工作，怎样用语言的形式描述状态转换规则。哪些硬件，哪些软件，电子计算机怎样实现。先有模型，后有计算机。例子：利用Turing机判断正整数的奇偶性。实例：二进制正整数B，询问：B是否为偶数？(1)={0,1,b}；(2)Q={q0,q1,q2,qy,qn}(3)状态转换规则如下：想法，找到最后一位，判断0或1Q01

10、bq0(q0,0,r)(q0,1,r)(q1,b,l)q1(q2,