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

《算法分析解析与设计-2016-第9讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计第9讲-2016山东大学计算机学院上次内容：(1)2sat的求解算法，利用一种有向图。叫项图，观察项图找规律,设计算法。需要找规律，才能设计算法。(2)三角化图中四(五)个问题的求解：三角化图的判定，字典序广度优先搜索。有完美顶点删除方案三角化图。三角化图上的团问题，着色问题，讲了这两个问题。五个问题的计算方法：团问题，着色问题，团覆盖问题，独立集问题，顶点覆盖问题，都有多项式算法。也有很多NPC问题在三角化图上仍然是NPC的。这五个问题已经不是判定问题了。判定问题§5.3子问题中P和NPC的分界人们想

2、干什么？画出一个明显的界限，应该是不可能的。其实没有什么界，需要时有，不需要时没有。其实事情做不到的，事物的好和坏，没法严格区分的。找到一个界限，将P和NPC分开，开始这样想，想象力重要，量变和质变。解一个实例应该简单，一类实例复杂点。研究者想这样。一般来说找一个明显的界限是不可能的。是否存在一个界，过了此界，就是NPC的，不过此界就是多项式的，这个界对任何一个问题大概是不会严格存在的。2Sat,3Sat2DM,3DM与前面讲过的最小迟序排工问题不同⋖先行约束排工问题：前面讲的排工，多任务排工，最小迟序排工，区间排工。

3、实例：描述实例需要4句话。(1)T={t1,t2,…,tn}，T中每个任务均可在单位时间内完成，L(ti)=1(2)T上有半序关系⋖，表达先后顺序。(3)处理机台数m。(4)完成任务的最后期限DZ+，总的最后期限。询问：是否存在排工表，：T{0,1,2,…,D-1}，满足(1)

4、{tiT

5、(ti)=k,1kD-1}

6、m，同时加工的任务数最多是m。(2)当ti⋖tj，则(ti)<(tj)，排工顺序满足半序关系。说明问题界的情况，现在解到什么程度不知道，这是当时的情况，不过可以说明要说明的主题。很多排工

7、问题变种，现在排工问题仍然是算法研究的重要内容。*先要说明半序关系怎样表达，用有向图表达。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)

8、m3，m4，m5，m6,m7,m100，半序关系任意；这些问题不知道是什么样的。没有研究清楚，没有明确的结果，也不是没有用。开始时好解，逐渐不知道好解不好解，最后肯定不好解。过度越来越难！！！从易到难的过度过程，看到一种趋势。如图：下面再从另一个角度研究问题，求解难度，正面攻击以后再从反面攻击。有些问题的子问题，说明其为NP-Hard也很有用。任何事物都有两个方面，观察了好的一面，再去观察坏的一面。一个问题的两个方面，总是在变化的。问题图的3着色问题：实例：图G=(V,E)询问：是否存在3种颜色为G着色。是

9、否存在映射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着色问题当然是多项式可解的。//已知的在三角化图上都是多项式的。比较图的团问题和着色问题的共同点和相同点

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

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