算法分析与设计2007第9讲

《算法分析与设计2007第9讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九讲上次内容：(1)2sat的求解算法，利用一种图。叫项图，分析项图找规律。(2)三角化图中四个问题的求解：三角化图的判定，字典序广度优先搜索。有完美顶点删除方案就是三角化图。l三角化图的团问题，着色问题，讲了这两个问题。l四个问题的计算方法：着色问题，团覆盖问题，独立集问题。§5.3子问题中P和NPC的分界人们想干什么？画出一个明显的界限，应该是不可能的。找到一个界限，将P和NPC分开，开始这样想，想象力重要，量变和质变的关系。解一个实例应该简单，一类实例复杂点。研究者想这样。是否存在一个界，过了此界，就是N

2、PC的，不过此界就是多项式的，这个界对任何一个问题大概是不会严格存在的。2sat,3sat先行约束排工问题：前面讲的排工，多任务排工，最小迟序排工，区间排工。实例：描述实例需要4句话。(1)T={t1,t2,…,tn}，T中每个任务均可在单位时间内完成，L(ti)=1(2)T上有半序关系⋖，表达先后顺序。(3)处理机台数m。(4)完成任务的最后期限DÎZ+，总的最后期限。与前面的最小迟续排工不同。询问：是否存在排工表，s：T®{0,1,2,…,D-1}，满足(1)

3、{tiÎT

4、s(ti)=k,1£k£D-1}

5、£

6、m，同时加工的任务数最多是m。(2)当ti⋖tj，则s(ti)

7、么地方。作业题。(3)半序关系为无，肯定是多项式时间可解的。因为加工长度均为1。如果任务加工长度为正整数，就不行了。(4)半序关系为树，问题是多项式时间可解的。自己试试。(5)半序关系任意，m任意，该问题是NPC的。(6)m£3，m£4，m£5，m£6,m£7,m£100，半序关系任意；这些问题不知道是什么样的。没有人研究过，没有明显结果，也不是没有用。开始时好解，逐渐不知道好解不好解，最后肯定不好解。过度越来越难！！！下面再从另一个角度研究问题，求解难度，正面进攻以后再进行反面进攻。第9页第九讲图的3着色问题：

8、实例：图G=(V,E)询问：图G是否可以用3种颜色着色。是否存在映射f：V®{1,2,3}，使得当(u,v)ÎE时，有f(u)¹f(v)。l任意图的3着色问题是NPC的。l限制顶点度数不超过常数D的团问题是P问题，为什么？所以用O(nD+1)种可能性可以一一尝试。若D为常数，团问题时间复杂度是多项式函数。但对于着色问题就不同了。3下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。21465D=3，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。定理5.8：对

9、顶点度数不超过4的图，其3着色问题属于NPC。证明：一般图3着色µ顶点度不超过4的图3着色。一种特殊的图：3(a)2(a)1(a)第9页第九讲这个图的特点：(1)可以用三种颜色着色，(2)顶点1，2，3，4度数均为26(3)顶点1，2，3，4肯定使用相同的颜色着色。才能三着色！！！所以任意举一个图的例子，都可以变为一个顶点度不超过4的图的例子，若原图可以3着色，新图也可以3着色，新图可以3着色，原图也可以3着色。34565143221所以顶点度不超过4的3着色是NPC的。定理5.9：平面图3着色是npc的。证明：

10、任意图3着色µ平面图3着色第9页第九讲先看一种特殊图：这个图的特点：(1)13个点，24条边，(2)是个平面图，可以3着色(3)X,X’必须用相同颜色着色才能3着色，(4)Y,Y’必须用相同颜色着色才能3着色，举个例子说明怎样变换第9页第九讲这个图不是平面图，在交叉处用前面的特殊图代替，就可以了。代替法也有讲究，需要讲。这样代替后的是平面图，且与原图有相同的色数，解释为什么。上述已经证明平面图3着色是NPC的。第6章：拟多项式变换与图灵规约这一章的背景：很多问题不是NP的，当然也不是NPC的，但是这些问题也很难找

11、到多项式算法。怎样说明这些问题的求解复杂度。这些问题不比NPC问题容易。*比如SAT问题的优化形式，求真值指派使满足的项数最多。这个问题称为Max-Sat。有些NPC问题很特殊：数大时难求，数小时就好求了。进一步理解时间复杂度。第9页第九讲先需要讲一个算法：TSP判定问题：实例：******询问：是否存在解(格式)，满足一定条件。TSP优化问题：实例：城市集合C={C1,