算法分析与设计-2016-第9讲

算法分析与设计第9讲-2016山东大学计算机学院上次内容：(1)2sat的求解算法，利用一种有向图。叫项图，观察项图找规律,设计算法。需要找规律，才能设计算法。(2)三角化图中四(五)个问题的求解：三角化图的判定，字典序广度优先搜索。有完美顶点删除方案三角化图。三角化图上的团问题，着色问题，讲了这两个问题。五个问题的计算方法：团问题，着色问题，团覆盖问题，独立集问题，顶点覆盖问题，都有多项式算法。也有很多NPC问题在三角化图上仍然是NPC的。这五个问题已经不是判定问题了。判定问题§5.3子问题中P和NPC的分界人们想干什么？画出一个明显的界限，应该是不可能的。其实没有什么界，需要时有，不需要时没有。其实事情做不到的，事物的好和坏，没法严格区分的。找到一个界限，将P和NPC分开，开始这样想，想象力重要，量变和质变。解一个实例应该简单，一类实例复杂点。研究者想这样。一般来说找一个明显的界限是不可能的。是否存在一个界，过了此界，就是NPC的，不过此界就是多项式的，这个界对任何一个问题大概是不会严格存在的。2Sat,3Sat2DM,3DM与前面讲过的最小迟序排工问题不同⋖先行约束排工问题：前面讲的排工，多任务排工，最小迟序排工，区间排工。实例：描述实例需要4句话。(1)T={t1,t2,…,tn}，T中每个任务均可在单位时间内完成，L(ti)=1(2)T上有半序关系⋖，表达先后顺序。(3)处理机台数m。(4)完成任务的最后期限DZ+，总的最后期限。询问：是否存在排工表，：T{0,1,2,…,D-1}，满足(1)|{tiT|(ti)=k,1kD-1}|m，同时加工的任务数最多是m。(2)当ti

⋖tj，则(ti)<(tj)，排工顺序满足半序关系。说明问题界的情况，现在解到什么程度不知道，这是当时的情况，不过可以说明要说明的主题。很多排工问题变种，现在排工问题仍然是算法研究的重要内容。*先要说明半序关系怎样表达，用有向图表达。T={t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11}，用有向无环图表示半序关系。

123411个任务4台机器(1)当m=1时，该问题是多项式可解的,为什么？(2)当m=2时，也是多项式时间可解的，总是同时安排两个任务，当作业。作业题。(3)半序关系为无，肯定是多项式时间可解的。因为加工长度均为1。(4)半序关系为树，问题是多项式时间可解的。自己试试，作业题。(5)半序关系任意，m任意，该问题是NPC的。(6)m3，m4，m5，m6,m7,m100，半序关系任意；这些问题不知道是什么样的。没有研究清楚，没有明确的结果，也不是没有用。开始时好解，逐渐不知道好解不好解，最后肯定不好解。过度越来越难！！！从易到难的过度过程，看到一种趋势。如图：下面再从另一个角度研究问题，求解难度，正面攻击以后再从反面攻击。有些问题的子问题，说明其为NP-Hard也很有用。任何事物都有两个方面，观察了好的一面，再去观察坏的一面。一个问题的两个方面，总是在变化的。问题图的3着色问题：实例：图G=(V,E)询问：是否存在3种颜色为G着色。是否存在映射f：V{1,2,3}，使得当(u,v)E时，有f(u)f(v)。任意图的着色问题是NPC的。任意图的团问题是NPC的，但任意图是否存在3个点的团的问题是多项式可解的。任意图的三着色问题就是NPC的。限制顶点度数不超过常数D的团问题是P问题，为什么？所以用O(nD+1)种可能性可以一一尝试。例如D=4，D=3。三角化图上，团问题与着色问题都是多项式时间可解的，但从另一个方面限制就不一样了。三角化图上，3着色问题当然是多项式可解的。

//已知的在三角化图上都是多项式的。比较图的团问题和着色问题的共同点和相同点。下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

(1)该图能否三着色(2)是否含有三个点的团下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

错了下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

下面该讲怎样着色，图的着色。先给一个点着色，然后给其相邻点着色，不断进行，尝试所有可能。D=4，常数，用上面的图解释怎样着色。限制顶点度为常数的着色问题并不好解。

另一种着色方案定理5.8：在顶点度数不超过4的无向简单图上的3着色问题属于NPC类。(在顶点度数不超过4的无向简单图上，团问题属于P类。)证明：需要知道一般图的3着色是NPC问题。一般图3着色顶点度不超过4的图3着色。一种特殊的图：8个点，13条边。

实例：无向图G=(V,E)，任意vV,d(v)4询问：是否存在f:V{1,2,3}，使得任意(u,v)E，f(u)f(v)定理5.8：在顶点度数不超过4的无向简单图上，3着色问题属于NPC类。(在顶点度数不超过4的无向简单图上，团问题属于P类。)证明：一般图3着色顶点度不超过4的图3着色。一种特殊的图：8个点，13条边。

定理5.8：在顶点度数不超过4的无向简单图上，3着色问题属于NPC类。(在顶点度数不超过4的无向简单图上，团问题属于P类。)证明：一般图3着色顶点度不超过4的图3着色。一种特殊的图：8个点，13条边。

定理5.8：在顶点度数不超过4的无向简单图上，3着色问题属于NPC类。(在顶点度数不超过4的无向简单图上，团问题属于P类。)证明：一般图3着色顶点度不超过4的图3着色。一种特殊的图：8个点，13条边。

定理5.8：在顶点度数不超过4的无向简单图上，3着色问题属于NPC类。(在顶点度数不超过4的无向简单图上，团问题属于P类。)证明：一般图3着色顶点度不超过4的图3着色。一种特殊的图：8个点，13条边。

这个图的特点：(1)可以用三种颜色着色，每个顶点的度不超过4。(2)顶点1，2，3，4，5，6的度数均为2(3)顶点1，2，3，4，5，6必须使用相同的颜色着色。才能三着色！！！所以任意举一个图的例子，都可以变为一个顶点度不超过4的图的例子，原图可以3着色新图也可以3着色；新图可以3着色，原图也可以3着色。7*(6-2)+1个顶点123123所以顶点度不超过4的3着色是NPC的。一个点的度最大为n-1，替换为三角图后，增加n-3个三角形的组合图，增加的顶点数目7(n-3)+1，多项式时间可以完成。定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y判定任意图是否可以三着色，属于NPC类。定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y实例：平面图G=(V,E)询问：是否存在f:V{1,2,3}，使得任意(u,v)E，f(u)f(v)所以顶点度不超过4的3着色是NPC的。一个点的度最大为n-1，替换为三角图后，增加n-3个三角形的组合图，增加的顶点数目7(n-3)+1，多项式时间可以完成。定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y所以顶点度不超过4的3着色是NPC的。一个点的度最大为n-1，替换为三角图后，增加n-3个三角形的组合图，增加的顶点数目7(n-3)+1，多项式时间可以完成。定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y所以顶点度不超过4的3着色是NPC的。一个点的度最大为n-1，替换为三角图后，增加n-3个三角形的组合图，增加的顶点数目7(n-3)+1，多项式时间可以完成。定理5.9：平面图3着色是NPC的。证明：任意图3着色平面图3着色先看一种特殊图：Y’XX’Y八卦图的特点：(1)13个点，24条边，(2)是个平面图，可以3着色(3)能3着色X,X’同颜色，Y,Y’同颜色。举个例子说明怎样变换

这个图的特点：(1)13个点，24条边，(2)是个平面图，可以3着色(3)X,X’必须用相同颜色着色才能3着色，(4)Y,Y’必须用相同颜色着色才能3着色，举个例子说明怎样变换

这个图的特点：(1)13个点，24条边，(2)是个平面图，可以3着色(3)X,X’必须用相同颜色着色才能3着色，(4)Y,Y’必须用相同颜色着色才能3着色，举个例子说明怎样变换

这个图的特点：(1)13个点，24条边，(2)是个平面图，可以3着色(3)X,X’必须用相同颜色着色才能3着色，(4)Y,Y’必须用相同颜色着色才能3着色，举个例子说明怎样变换

这个图的特点：(1)13个点，24条边，(2)是个平面图，可以3着色(3)X,X’必须用相同颜色着色才能3着色，(4)Y,Y’必须用相同颜色着色才能3着色，举个例子说明怎样变换

每条边最多与|E|-1条边相交，每个交点增加不超过13个点。交点数目是多项式个，则增加的点数目当然是多项式个。所以多项式时间能完成八卦图1235467891012345678910这个图不是平面图，在交叉处用前面的特殊图代替，就可以了，代替完成就变成平面图了。代替法也有讲究，需要讲。这样代替后的是平面图，且与原图有相同的色数，解释为什么。上述已经证明平面图3着色是NPC的。

第6章：拟多项式变换与图灵规约这一章要干什么？(1)NPC类问题中的特殊现象，数值参量对NPC问题计算复杂性的影响。数大时难求，数小时就好求了。界定它们的复杂性，有这种现象，就要观察它们的规律性，说明它们的存在性，刻画它。有些NPC问题很特殊：进一步理解时间复杂度。先需要讲一个算法：(2)很多问题不是NP的，当然也不是NPC的，但是这些问题也很难找到多项式算法，比NPC问题还要难，所以需要将NPC问题推广。怎样说明这些问题的求解复杂度。这些问题不比NPC问题容易。

*比如SAT问题的优化形式，SAT实例：U,C询问：是否存在U的真值指派，使C中项全部满足。求真值指派使满足的项数最多，这个问题称为Max-SAT。Max-SAT实例：U,C，搜索问题询问：求解U的真值指派，使C中满足的项数目达到最大。TSP判定问题：实例：城市集合C={C1,C2,…,Cm}，定义距离：d(Ci,Cj)Z+，BZ+。询问：是否存在货郎旅游，其长度不大于B。TSP优化问题：搜索问题实例：城市集合C={C1,C2,…,Cm}，定义距离：d(Ci,Cj)Z+，询问：求解城市排列C(1),C(2),…,C(m-1),C(m)，满足最优的条件d(C(1),C(2),…,C(m-1),C(m))=min{d(P[C1,…,Cm])|P[C1,…,Cm]为任意排列}

前i个元素中是否存在子集，其中元素价值之和为0A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF12345(i)若t(i-1,j)=T，则t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，则t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12345(i)若t(i-1,j)=T，则t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，则t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12TTFFFFFFFTTFFFs(a2)=9345(i)若t(i-1,j)=T，则t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，则t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12TTFFFFFFFTTFFFs(a2)=93TTFFFTTFFTTFFFs(a3)=545(i)若t(i-1,j)=T，则t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，则t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12TTFFFFFFFTTFFFs(a2)=93TTFFFTTFFTTFFFs(a3)=54TTFTTTTFTTTFTTs(a4)=35(i)若t(i-1,j)=T，则t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，则t(i,j)=T。A={1,9