算法分析和设计2007第9讲.doc

上次内容： (1)2sat的求解算法，利用一种图。叫项图，分析项图找规律。 (2)三角化图中四个问题的求解：三角化图的判定，字典序广度优先有哪些信誉好的足球投注网站。有完美顶点删除方案就是三角化图。 三角化图的团问题，着色问题，讲了这两个问题。 四个问题的计算方法：着色问题，团覆盖问题，独立集问题。 §5.3子问题中P和NPC的分界 人们想干什么？画出一个明显的界限，应该是不可能的。 找到一个界限，将P和NPC分开，开始这样想，想象力重要，量变和质变的关系。解一个实例应该简单，一类实例复杂点。研究者想这样。 是否存在一个界，过了此界，就是NPC的，不过此界就是多项式的，这个界对任何一个问题大概是不会严格存在的。 2sat, 3sat 先行约束排工问题：前面讲的排工，多任务排工，最小迟序排工，区间排工。 实例：描述实例需要4句话。 (1)T={t1, t2,…,tn}，T中每个任务均可在单位时间内完成，L(ti)=1 (2)T上有半序关系?，表达先后顺序。 (3)处理机台数m。 (4)完成任务的最后期限D(Z+，总的最后期限。与前面的最小迟续排工不同。 询问：是否存在排工表，(：T({0,1,2,…,D-1}，满足 (1)|{ti(T| ((ti) = k, 1(k(D-1}|(m，同时加工的任务数最多是m。 (2)当ti?tj，则((ti)((tj)，先加工后加工。 说明问题界的情况，现在解到什么程度不知道，这是当时的情况，不过可以说明问题。 很多排工问题变种，现在排工问题仍然是算法研究的重要内容。排工协会，专门研究排工。 *先要说明半序关系怎样表达，用有向图表达。 T={t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11} (1)当m=1时，该问题是多项式可解的,为什么？ (2)当m=2时，也是多项式时间可解的，总是同时安排两个任务，当作作业研究问题时要看清楚难在什么地方。作业题。 (3)半序关系为无，肯定是多项式时间可解的。因为加工长度均为1。如果任务加工长度为正整数，就不行了。 (4)半序关系为树，问题是多项式时间可解的。自己试试。 (5)半序关系任意，m任意，该问题是NPC的。 (6)m(3，m(4，m(5，m(6, m(7, m(100，半序关系任意；这些问题不知道是什么样的。没有人研究过，没有明显结果，也不是没有用。 开始时好解，逐渐不知道好解不好解，最后肯定不好解。过度越来越难！！！ 下面再从另一个角度研究问题，求解难度，正面进攻以后再进行反面进攻。 图的3着色问题： 实例：图G=(V,E) 询问：图G是否可以用3种颜色着色。 是否存在映射f：V({1,2,3}，使得当(u,v)(E时，有f(u)(f(v)。 任意图的3着色问题是NPC的。 限制顶点度数不超过常数D的团问题是P问题，为什么？所以用O(nD+1)种可能性可以一一尝试。若D为常数，团问题时间复杂度是多项式函数。但对于着色问题就不同了。 下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。 D=3，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。 定理5.8：对顶点度数不超过4的图，其3着色问题属于NPC。 证明： 一般图3着色(顶点度不超过4的图3着色。 一种特殊的图： 这个图的特点： (1)可以用三种颜色着色， (2)顶点1，2，3，4度数均为2 (3)顶点1，2，3，4肯定使用相同的颜色着色。才能三着色！！！ 所以任意举一个图的例子，都可以变为一个顶点度不超过4的图的例子，若原图可以3着色，新图也可以3着色，新图可以3着色，原图也可以3着色。 所以顶点度不超过4的3着色是NPC的。 定理5.9：平面图3着色是npc的。 证明：任意图3着色(平面图3着色 先看一种特殊图： 这个图的特点： (1)13个点，24条边， (2)是个平面图，可以3着色 (3)X,X’必须用相同颜色着色才能3着色， (4)Y,Y’必须用相同颜色着色才能3着色， 举个例子说明怎样变换 这个图不是平面图，在交叉处用前面的特殊图代替，就可以了。代替法也有讲究，需要讲。这样代替后的是平面图，且与原图有相同的色数，解释为什么。 上述已经证明平面图3着色是NPC的。 第6章：拟多项式变换与图灵规约 这一章的背景： 很多问题不是NP的，当然也不是NPC的，但是这些问题也很难找到多项式算法。怎样说明这些问题的求解复杂度。这些问题不比NPC问题容易。 *比如SAT问题的优化形式，求真值指派使满足的项数最多。这个问题称为Max-Sat。 有些NPC问题很特殊： 数大时难求，数小时就好求了。进一步理解时间复杂度。 先需要讲一个算法： TSP判定问题： 实例：****** 询问：是否存在解(格式)