资源描述：
《算法分析与设计2007第7讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七讲上次内容：(1)证明npc问题(2)sat,3sat,3dm,vc,cl,par,vi,hc(3)进一步证明，x3c，子图同构，集合覆盖，等等，其他自己看书，原来有的人专门看怎样证明npc问题。用的是限制技术。下面继续证明：背包问题：这个问题以后会用，经常用。应用背景：挑选最大价值的东西装入背包中，很多东西，从中挑选。背包容量是有限的。实例：有限集合：U={u1,u2,…,un}，S(ui)ÎZ+表示每个元素的价值，w(ui)ÎZ+表示每个元素的重量。BÎZ+，KÎZ+。询问：是否存在U’ÍU，满足，。国家预算，科技投资，背包问题。定理：背包问题K
2、napsackÎNPC。证明：限制技术，注意针对实例限制。不能针对其他限制。限制为偶数，S(ui)=W(ui)，B=K=。上述问题变为划分问题，满足条件的背包实例一定是划分问题实例。因为划分问题是NPC，所以背包问题也是NPC。好好理解怎么回事。多任务排工问题：独立任务的多个机器排工。背景是什么：很多任务，加工时间不同，用m台机器并行加工，怎样排列任务使并行加工时间最短。实例：有限任务集合：A={a1,a2,…,an}，每个任务的加工时间长度L(ai)ÎZ+。加工机器数mÎZ+，加工最后期限DÎZ+。询问：是否存在划分A=A1ÈA2È…ÈAm，AiÇAj
3、=Æ(第8页第七讲划分本身就有这样的含义)，使£D。解释：A1中任务的总时间、A2中任务的总时间、。。。、Am中任务的总时间。那个最长。加工时间最长的机器所用时间最短。中国的排工协会。Scheduling。用最少时间完成全部任务。用最少的时间完成所有任务。定理：多任务排工属于NPC。证明：限制m=2，D=，这样限制后的实例成为划分问题实例。所以划分问题是NPC的。4.2.2局部替换技术*3sat的证明中，将一个sat子句替换为若干3sat子句，得到证明。划分三角形问题：PIT，划分三角形，原创很精彩。这也是一个原创型的证明。实例：G=(V,E)，
4、V
5、=
6、3q，qÎZ+。询问：是否存在V的划分：V=V1ÈV2È…ÈVq满足任意
7、Vi
8、=3，且Vi={vi[1],vi[2],vi[3]}中的3个点在G中形成三角形。定理：划分三角形问题属于NPC类，证明：X3CµPIT，后来我也用了一次。替换是常用的技术。实例：X={x1,x2,…,x3q}，C={c1,…,cn}，ciÍX，
9、ci
10、=3。询问：是否存在C的子集C’，严格覆盖X。第8页第七讲例子：X3C的实例，
11、X
12、=3q，
13、C
14、=n。X={x1,y1,z1,x2,y2,z2}，C={(x1,y1,z1)，(x1,y1,z2)，(x2,y2,z2)}q’=q
15、+3n=2+3*3=11有的三角图可划分4个三角形，有的三角图可划分3个三角形。一个三角图最多划分4个三角形。®X3C实例中有3元素严格覆盖，则能划分出4q+3(n-q)=q+3n个三角形。能否划分超过q+3n个三角形。¬若PIT中能划分出q+3n个三角形，必有q个三脚图能划分出4个三角形。这就是最多的。不可能超过q个，这是当然的。若少于q个，则最后划分出三角形个数少于q+3n个。例如是q1个，剩余的三脚图都是不完整的，每个最多划分3个三角形，于是三角形个数为：4q1+3(n-q1)=q1+3n个。q是上限所以得证。第8页第七讲区间排工问题：实例：有限任
16、务集合，T={t1,t2,…,tn}，只有一台机器。r(tk)：最早起始时间d(tk)：最晚结束时间L(tk)：加工长度询问：是否存在排工表：s(tk)，k=1,2,…,n，使d(tk)-L(tk)³s(tk)³r(tk)，每个任务都能按时完成。任意ti,tj，i¹j，s(ti)³s(tj)+L(tj)或s(tj)³s(ti)+L(ti)就一台机器，处理机，当然要这样了。一心不可二用。定理：区间排工属于NPC类。证明：PARµ区间排工。PAR的例子，A={a1,a2,a3,a4,a5}，S(a1)=2，S(a2)=5，S(a3)=10，S(a4)=9，S
17、(a5)=8。T={t1,t2,t3,t4,t5,t}B=，应该假设B是偶数，才好。r(t1)=r(t2)=r(t3)=r(t4)=r(t5)=0。d(t1)=d(t2)=d(t3)=d(t4)=d(t5)=B+1=35，比总价值多1。L(t1)=S(a1)=2，L(t2)=S(a2)=5，L(t3)=S(a3)=10，L(t4)=S(a4)=9，L(t5)=S(a5)=8。r()==17，d()=+1=18，L()=1。(®)若划分问题实例回答是，则将一部分总长度为第8页第七讲的元素对应的任务分别排在[0，]和[+1，B+1]区间，[，+1]排，于是为
18、满足条件的解。(¬)若有满足条件的排工，则只能排在[，+1]，其他任务排在两边，
