算法分析与设计2007第8讲(同名22020)

算法分析与设计2007第8讲(同名22020)

ID:14360712

大小:736.00 KB

页数:112页

时间:2018-07-28

算法分析与设计2007第8讲(同名22020)_第1页
算法分析与设计2007第8讲(同名22020)_第2页
算法分析与设计2007第8讲(同名22020)_第3页
算法分析与设计2007第8讲(同名22020)_第4页
算法分析与设计2007第8讲(同名22020)_第5页
资源描述:

《算法分析与设计2007第8讲(同名22020)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第八讲上次内容:(1)限制技术,局部替换技术,分支技术证明NPC。(2)划分三角形,多任务排工,区间排工,最小迟序排工,是NPC。(3)NPC问题子问题是NPC吗?是多项式时间可解的吗,具体问题看。(4)Sat,3Sat,3DM,par,vc,VI,CL,HC,X3C,MC,PIT,Scedule1,Schedule2,Schedule3,§2SAT问题属于P类正面结果促进较大,反面结果否定。矛盾的两个方面,寻找规律。实例:U={u1,u2,…,un},C={C1,…,Cm},CiÍUÈ{,…,},

2、Ci

3、=2。

4、询问:是否存在U的真值指派使C满足。C1Ù…ÙCm=1。要考虑怎样解:通过例子U={u1,u2,u3,u4,u5,u6}C={(u1,),(u2,u5),(,u5),(,u4),(,u6),(,)}根据上述实例构造有向图:规则,(x,y)®u1u2u3u4u5u6112第八讲存在一条从u1到的通路,u1赋值1肯定不行。引理:在2SAT项图中,若存在uj®的通路,则uj≠1。即uj=0才可能使所有项满足。就是只能赋值0。证明:uj®w1®w2®…®wk®,则有如下项:(,w1),(,w2),…,(,)。若uj=1,

5、则必有一个项不能满足。说明一下。引理:若在2sat项图中,存在路径®uj,则uj¹0,必须uj¬1才可能使所有项满足。证明:设路径为:®z1®z2®…®zl-1®zl®uj,则该路径对应如下项:(uj,z1),(,z2),(,z3),…,(,zl),(,uj),矛盾。定理:若存在uj,在2sat项图中,存在通路:®uj,uj®,则不存在真值指派,使所有项均满足。定理:若对任意:uj,j=1,…,n,通路P(®uj)和P(uj®)不同时存在,则一定存在U的真值指派使所有项满足。证明:只要设计出算法就可以了,就是当下述

6、条件成立时:通路P(®uj)和P(uj®)不同时存在时,设计出给每个uj赋值的算法。(1)找通路,先赋值,对于uj,j=1,…,n112第八讲若uj®,则uj=0;若®uj,则uj=1。(2)扩展赋值,两种情况。ui=1,xÎ{uj,}。存在边ui®x,则x=1。x=uj,则uj¬1;x=,则uj¬0。ui=0,xÎ{uj,}。存在边x®ui,则x=0。x=uj,则uj¬0;x=,则uj¬1。证明不会出现矛盾:112第八讲(3)剩余变量赋值,怎么赋值?其余赋予相同的值(0或1)。实际上根本用不着第2步。112第八讲

7、请证明正确性。自己完成。§5.2一类NPC问题在三角化图上的解三角化图的了解。(1)几个概念,讲这个内容告诉大家很多知识,常识也很有用。G=(V,E)w(G):团数,G的最大完全子图定点个数,c(G):色数,G中定点着色所需最小色数,图三着色是NPC,图k着色是NPC,平面图:(1)图三着色是NPC。以后证明。(2)4112第八讲着色未知,已经用计算机证明出来了,大概现在研究这个问题的人很少。(3)5着色是多项式时间可解的,容易证明。平面图。a(G):G的独立数,G的最大独立集的顶点个数,k(G):G的团覆盖数,覆

8、盖G的所有顶点所需要的完全子图最小个数。团覆盖问题。团覆盖也有很多应用,在很多方面。结论:w(G)£c(G)//w(G):团数,G的最大完全子图定点个数,//c(G):色数,G中定点着色所需最小色数,a(G)£k(G)(2)什么是三角化图:任意四边形以上的多边形中都有一条弦。首先举个例子:说明什么是完美顶点删除方案。我所见过的应用,完美进化树,当时不知怎么回事。单纯顶点:与v临接的点在图中是完全子图,任意u1,u2ÎAdj(v),(u1,u2)ÎE,则v是单纯顶点。完美顶点删除方案:存在一个顶点序列v1,v2,…,

9、vn,使vk在G(vk+1,…,vn)中是单纯顶点,则顶点序列称为完美顶点删除方案。112第八讲k=1,2,…,n-1,G(vk+1,…,vn)称为由vk+1,…,vn导出的子图。三角化图的定义:若图G存在完美顶点删除方案,则G是三角化图。以下就用这个判断。举例子:1,5,2,3,4,6,7,8,9结论:(1)可以多项式时间判断三角化图。(2)在三角化图上,团问题,着色问题,独立集问题,团划分问题都可多项式时间解决。5.2.2用字典续广度优先搜索判断三角化图Tarjan的算法,最有名的工作是判断平面图,例子说明:判

10、断三角化图很显然是多项式时间可解的。112第八讲adj(a)={b,e}adj(b)={a,c,d,e}adj(c)={b,d}adj(d)={b,c,e}adj(e)={a,b,d}开始任意选择顶点aivabcde0LabelfffffNumber-----1Labelf{5}ff{5}Number5----2Labelf{5}{4}{4}{5,4}Num

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。