算法分析与设计第3讲.docx
《算法分析与设计第3讲.docx》由会员分享，可在线阅读，更多相关《算法分析与设计第3讲.docx（14页珍藏版）》请在冰点文库上搜索。
算法分析与设计第3讲
上次内容：
（1）5个算法设计技术，分而治之，贪心技术，回溯，动态规划，局部搜索
（2）局部搜索设计近似算法，现在也有了。
（3）许多问题设计不出多项式时间求解算法，也有很多问题能找到多项式算法，大学学的算法都是多项式时间的。
（4）企图把问题分类，能否分为两类，一类可以设计多项式时间算法，另一类不能设计多项式时间算法。
前人建立了一种模型，说明问题很难，怎样说明。
实际也是多年研究的结果，科学就是解释现象。
例子：
先讲问题，这些问题找不到多项式时间算法。
实例：
布尔变量集合：
U={u1,u2,u3,u4,u5}，C={{
},{
},{
},{
}}
询问：
是否存在真值指派，使（
）（
）（
）（
）=1
布尔变量字母:
ui,
项（Clause）:
C1={
},…,Cm
SAT问题一般描述：
实例：
布尔变量集合：
U={u1,u2,…,un}，项集合C={c1,c2,…,cm}，
ck={yk1,yk2,…,ykt},ykj{u1,u2,…,un,
}.
询问：
是否存在U的真值指派，使c1c2…cm=1，就是，
ck=yk1yk2…ykt
在人工智能的搜索求解中，推理规则均采用合取范式表示。
硬件测试，逻辑表达式判定求解
TSP问题：
货郎问题
实例：
城市集合：
C={c1,c2,…,cm},d（ci,cj）Z+，ci,cjC，正整数K.
询问：
是否存在城市排列c
（1）c
（2）…c（m），使
Hamilton回路问题：
实例：
无向简单图G=（V,E），|V|=n。
询问：
是否存在定点排列v
（1）,v
（2）,…,v（n），使（v（i）,v（i+1））E（G）,i=1,…,n-1，（v（n）,v
（1））E（G）。
上述两个问题均是询问解得存在性，判断是否具有满足条件的解。
这三个问题都找不到多项式时间算法，但都能找到指数时间算法。
什么是多项式时间？
什么是指数时间？
输入长度：
问题实例的规模。
书上的表：
表上是以前的计算机的计算时间。
问题的算法时间复杂性有很多，什么样的好呢？
T（n）
问题输入长度n
10
20
30
40
50
60
n
0.00001
0.00002
0.00003
0.00004
0.00005
0.00006
n2
0.0001
0.0004
0.0009
0.0016
0.0025
0.0036
n3
0.001
0.008
0.027
0.064
0.125
0.216
n5
10.1
320
1243
1.7p
25.2p
130p
2n
0.001
1
17.9p
12.7天
35.7年
366世纪
3n
0.059
58分
6.5年
3855世纪
表说明多项式时间复杂度与指数时间复杂度，区别大。
主要是增长速度区别。
§3.2确定型图灵机与P类
下面要说明什么是多项式时间可以求解的问题，实际要定义多项式时间复杂度，什么是时间复杂度，什么是空间复杂度。
自圆其说，说明自然界中的问题，解决问题。
英文名字：
DTM
（1）一个硬壳；
存储带：
一个方格存一个符号；
读写头在那里，可以左右移动，一次移动一个方格。
状态控制器可以读写带方格中的内容；
（2）硬壳中放入数据；
带上放的符号：
有限个，其中包括空白符号b，
={b}，是输入符号集合。
符号有限个，不能无限多个。
（3）有限个状态；状态个数不随问题实例长度变化而变化。
Q={q0,q1,q2,…,qy,qn}，q0：
起始状态，qy,qn都是停机状态，qy表示停机时回答yes，qn表示停机时回答no。
qf={qy,qn}
（4）状态转换规则。
什么是状态，三要素表示DTM状态：
（qk,读写头位置，读写头指向位置的带符号），现在不关心读写头位置，只关心读写头指定带方格的符号。
在造计算机时，有一个地址寄存器。
（Q-{qf}）Q：
这是一个映射。
（qi,si）（
）：
含义，当前状态qi，当前读写头所指方格中的符号si，则下一个状态qi’，将带方格中的符号修改为si’，读写头移动一个位置：
={L,R,S}
程序实际就是状态转换规则：
初始状态q0，按照程序转换状态，到结束时状态qf，回答yes或no。
我们编的程序就是告诉计算机怎样改变状态。
真正实现计算机，还有很多工作，怎样用语言的形式描述状态转换规则。
哪些硬件，哪些软件，电子计算机怎样实现。
例子：
利用Turing机判断正整数的奇偶性。
（1）={0,1,b}；
（2）Q={q0,q1,q2,qy,qn}
（3）状态转换规则如下：
Q
0
1
b
q0
（q0,0,r）
（q0,1,r）
（q1,b,l）
q1
（q2,0,s）
（q2,1,s）
（q2,b,s）
q2
（qy,0,s）
（qn,1,s）
（q2,b,s）
以下是输入的带符号，输入数据，实例，
b
b
1
0
1
0
b
b
b
b
-2
-1
0
1
2
3
4
5
6
7
（1）q0,1,r---q0,0读写头位置1;
（2）q0,0,r---q0,1读写头位置2
（3）q0,1,r---q0,0读写头位置3;
（4）q0,0,r---q0,b读写头位置4；
（5）q0,b,l---q1,0读写头位置3;
（6）q1,0,s---q2,0读写头位置3
找到最后一位，判断0/1，确定奇偶性。
定义3.1：
把问题的任意实例I输入给DTM，都能经过DTM有限步计算到达停机状态qf{qy,qn}，则称问题是确定turing机可计算的，否则称为确定turing机不可计算的。
有的问题不可计算。
不是所有问题都可以DTM计算。
前面的Sat问题，TSP问题，Hamilton回路问题都是DTM可计算的。
团问题：
实例：
无向图G=（V,E），正整数JZ+，
询问：
是否存在G的一个完全子图G’,|V（G’）|J？
输入数据格式认为是一种语言，规则当然是语言
问题的描述：
<,L,>
描述问题的符号集合，
形式化描述实例，输入数据的格式是什么，L，也称为一种语言。
L也可以认为是符号串集合。
针对任意一个输入IL，回答是什么？
（I）{yes,no}
***实例有了以后，就有答案了，解也就有了,回答yes的解可能多个。
每个实例对应一个确定的答案。
实质上，（I）函数就描述问题的询问
定义3.2：
问题<,L,>是用某个DTM程序可解的，任意实例IL，只要I写在带上，从q0状态开始执行，总可经过有限步计算停机，且在带上保留着该问题的解答（I）{yes,no}。
所用的状态数为计算的时间复杂度：
TM（I）。
计算中所占用的带方格数为空间复杂度SM（I）。
但是前面我们经常用T（n），而不去考虑T（I）,用某个实例的时间复杂性不能肯定客观地说明算法好坏。
L（n）={I|IL,|I|=n}，实例集合，长度为n的语言集合。
问题规模怎么描述。
TM（n）=max{TM（I）|IL（n）}，问题输入长度为n时的时间复杂度。
SM（n）=max{SM（I）|IL（n）}，问题输入长度为n时的空间复杂度。
这样定义是客观的，
所有长度为n的实例中，计算时间最长的那个实例的时间复杂度定义为T（n）。
本质上，TM（n）也是几乎不可能精确得到的，我们往往只能得到TM（n）的一个上界。
定义3.4:
多项式时间可解的：
存在存在多项式函数P（n），使TM（n）P（n）。
则称问题是多项式时间可计算的。
P类问题------DTM多项式时间可计算的。
§3.3非确定图灵机与NP类
先考虑多项式时间可验证的问题，那就要先定义这种问题。
Rabin与Scott两位科学家发明了这种非确定型计算
素数分解问题：
实例：
大整数n
询问：
是否存在两个（素）数p1,p2，使得：
p1*p2=n?
密码学上十分重要的问题。
验证容易，求解难。
货郎判定问题，团问题都是这样，Hamilton回路问题。
Sat问题：
实例:
U={u1,u2,u3,u4,u5},
C={（u1,u2,
）,（u2,
u5）,（
u3,
）,（u2,u3,u5）}
询问：
是否存在U的真值指派使C中的项均满足。
解释何谓满足，就是使项对应布尔表达式取值为1。
TSP问题：
实例：
城市集合：
C={c1,c2,…,cm},d（ci,cj）Z+，ci,cjC，正整数K.
询问：
是否存在城市排列c
（1）c
（2）…c（m），使
验证容易求解难。
三个问题都是这样。
Hamilton回路问题：
实例：
无向简单图G=（V,E），|V|=n。
询问：
是否存在定点排列v
（1）,v
（2）,…,v（n），使（v（i）,v（i+1））E（G）,i=1,…,n-1，（v（n）,v
（1））E（G）。
所以给出NTM模型如下：
给DTM强加另外一种超人的能力。
现在讲述的NTM并不是Rabin的NTM，等价？
（1）硬壳：
（2）机器的符号，={b}
（3）状态集合：
Q={q0,q1,q2,…,qf}，qf{qy,qn}
（4）状态转换函数：
（qi,si）（qi’,si’,）
，哪一个状态，哪一个符号，怎么移动，NTM自己通过猜测部件获得选择。
解释什么是NTM，
●实际就是验证机器，由猜测部件猜测最好的动作，然后状态控制器去执行动作。
求出最优解。
根据猜测部件求出的解回答结果。
●猜测部件猜测正确，则多项式时间内可以回答正确答案。
我们只需要编验证程序就可以。
●猜测部件猜测错了，就不能保证最后回答对了。
猜测部件应该能够保证，若是就能猜出来。
●相当于验证了。
猜测一个动作就相当于猜测一个解。
一步一步猜，所以一步一步改变状态。
●Sat问题若猜测部件给定一个解，能否编一个程序验证是否满足？
能否编一个程序对任意猜测的解去验证是否满足？
当然能，这有什么不确定的地方？
因为不知道猜测什么解，所以下一步不确定。
●问题是猜测部件有多大能力。
可以认为猜测解。
TSP的非确定型程序
v[1],…,v[m]：
所有图的点
[1]Guess（x[1m]）
[2]P[1]=x[1],L=0.
Fori=2Tomdostep1
Ifx[i]{P[1],…,P[i-1]}returnerror
Ifx[i]=v[1]{L=L+d（P[i-1],v[1]）；P[i]=v[1]}
Ifx[i]=v[2]{L=L+d（P[i-1],v[2]）；P[i]=v[2]}
…
Ifx[i]=v[m]{L=L+d（P[i-1],v[m]）；P[i]=v[m]}
Endfor
IfL≤KreturnYESelsereturnNO.
定义3.5：
NTM可解，<,L,>给定，任意IL,NTM总可在有限步停机，给出正确答案。
定义3.6:
时空复杂度。
L（n）={I|IL,（I）=1,|I|=n}，回答是的实例长度为n的集合。
TNTM（n）=max{TNTM（I）|IL（n）}
时间复杂度只算执行人编的程序的时间，猜测时间不算。
SNTM（n）=max{SNTM（I）|IL（n）}
定义3.7：
NP类问题，TNTM（n）P（n）。
问题类。
NTM多项式时间可解的问题。
是否可以编个程序，解答SAT问题，解答Hamilton回路问题。
说明：
●P类，NP类，多项式时间可验证的问题类NP类。
●PNP
●定理3.1：
NP类的问题，均可用DTM在T（n）=O（2P（n））时间内求解。
存在P（n）。
●简单说明怎样证明。
因为每一步有好几个选择，用O（2P（n））可以全部枚举出来。
不让猜测部件猜了，把所有可能的解都举出来，每个都验证，因为一次验证多项式时间：
q（n）,解的长度不会超过q（n），总时间复杂度不超过：
||q（n）=2P（n）
§3.4多项式变换与NPC类
前面的东西没法证明TSP问题不存在多项式时间复杂度。
举例子，很多人花费大量时间企图证明TSP问题不存在多项式算法，但是都没有证出来。
求解问题时想到用变换。
实际上求解问题用变换效果并不好。
但是可以用变换证明问题的计算难度。
用一个问题的语言描述另一个问题，任何一个实例都行方可。
把一个问题转换为另一个问题解决。
用1的语言描述2，若1存在多项式算法，则2也存在多项式算法。
举个例子：
sat,n皇后问题
x11
x12
x13
x1n
x21
x22
1
x2n
1
1
1
1
1
1
1
1
1
1
1
1
1
xn1
xnn
第一行：
{x11,…,x1n},{x1i,x1j}（ij,1i,jn）
…
第n行：
{xn1,…,xnn},{xni,xnj}（ij,1i,jn）
第1列：
{x11,…,xn1},{xi1,xj1}（ij,1i,jn）
…
第n列：
{xn1,…,xnn},{xin,xjn}（ij,1i,jn）
加上斜线：
大家写完。
Sat问题：
实例:
U={u1,u2,u3,u4,u5},C={（u1,u2,
）,（u2,
u5）,
（
u3,
）,（u2,u3,u5）}
询问：
是否存在U的真值指派使C中的项均满足。
1说明别人做过n皇后问题，速度很快，就是找不出好算法来。
2说明怎样做？
变量：
x11,x12,…x1n,…xn1,…,xnn
每行只有一个取1：
{xi1,…,xin}，{
}，。
。
。
，{
}。
每列只有一个取1：
每个斜线只有一个取1。
项个数，不超过
，时间复杂度O（n3）
变换：
reduction
Hamilton回路可以用Sat表达：
x11x12x13x14
x21x22x23x24
x31x32x33x34
x41x42x43x44
y11y12,y13,y14
y21y22y23,y24
y31y32y33y34
y41y42y43y44
（1）（x11,x12,x13,x14）,（
），…………
（2）（
yjk）,（
ykj）,jk。
（解释）
（
yjk）,（
ykj）,jk。
（
yjk）,（
ykj）,jk。
（
yjk）,（
ykj）,jk。
（3）（y12）,（y21）,（y14）,（y41）,（y23）,（y32）,（y24）,（y42）,（y34）,（y43）,（
）,（
）
下课后，大家自己算用了多少个项，分析时间复杂性。
多项式变换定义：
希望将1变为2，若2多项式时间可解，则1也多项式时间可解。
●1=<1,L1,1>；2=<2,L2,2>
●变换f：
1*2*，IL1，f（I）L2，1（I）=2（f（I））
●f变换可以在p（|I|=n）时间内计算完成。
则f称为由1到2的多项式规约。
若1可以多项式归约到2，则若2存在多项式算法，则1也有多项式算法。
前面的多项式规约进一步修改如下：
●1=<1,L1,1>；2=<2,L2,2>
●变换f：
1*2*，IL1，f（I）L2，
1（I）=12（f（I））=1
升级会员 