第5章地图着色问题.ppt

部分可行解 dominating set problem The?dominating set problem?concerns testing whether γ(G)?≤?K?for a given graph?G?and input?K; it is a classical?NP-complete?decision problem?in?computational complexity theory(Garey Johnson 1979). dominating set problem Therefore it is believed that there is no?efficient algorithm?that finds a smallest dominating set for a given graph. 关于冰激凌问题的讨论（一） 没有人知道是否有一个算法可以明显地优于蛮力算法来得到一个最小的支配集 蛮力算法所需要的时间随着结点数量的增加而呈指数级增大——这被称作指数级时间复杂度算法 如果一个算法的运行时间随着交叉点数量的增加呈平方或者立方或者任何其它幂级数的增长，则称该算法是一个多项式时间复杂度算法 冰激凌销售车问题是数量众多的不知道多项式时间复杂度算法是否存在的问题中的一个 关于冰激凌问题的讨论（二 ） 一个多项式时间复杂度算法对足够大的地图来说总是比较快的 ？？？ 如果n117 计算n17和2n哪个大 11717 =1.4426455806521081e+35 2117 =1.661534994731145e+35 11817 =1.6672246556491878e+35 2118 =3.32306998946229e+35 关于冰激凌问题的讨论（三） 是否有一个多项式时间复杂度算法来得到最小的配置集呢 ？ 不确定 检验一种方案是否是最小支配集同样困难 蛮力法检验是指数级的 对多项式时间复杂度算法，目前既没有人能证明算法存在，也没有证明这种算法不存在 关于冰激凌问题的讨论（四） 证明了一些问题，它们的时间复杂性是多项式阶的，这只需设计一个实现它的时间复杂性是多项式阶的算法即可，例如排序问题 这样一类问题将被称之为P类问题 还有一类问题，人们已经设计出实现它的时间复杂性为指数阶的算法，并且已证明该问题不存在多项式阶的算法，例如梵塔问题 这样一类问题人们称之为顽型问题 关于冰激凌问题的讨论（五） 但是有这样一类问题，人们目前已设计的实现它的算法其时间复杂性为指数阶的，但还不能肯定它有或没有多项式阶的算法，例如当m＞2时任意图的m-可着色问题 人们称这类问题为NP问题，NP是Nondeterministic Polynomial的缩写，即非确定的多项式的意思 关于冰激凌问题的讨论（六） P问题是确定性计算模型下的易解问题 NP问题是非确定性计算模型下的易验证问题 还有一类问题 如果一个这样的问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，这类问题称为NP完全问题（NP Complete） 目前还没有一个NP完全问题有多项式时间算法 Q A * 有一个制图师对地图上的国家进行着色，每个国家可以被涂成任何颜色， 但是相邻国家的颜色要不同，而且，这个制图师家庭拮据，不能供应很 多蜡笔，因此每幅地图要采用尽可能少的颜色数来着色。 【练习1】图5.1有三幅地图，请为图中的区域进行着色，相邻区域颜色不同， 要求每幅图中使用的颜色数尽可能少。 注意，这里的相邻指两个区域有一段长度不为0的公共边界。 如果两个区域有一个公共顶点，则不是相邻的。 * 对于图5.1a，只需要两种颜色。从任意一块区域开始，试着对其着色。 一旦该区域涂上颜色，那么与它相邻的其他区域就只能使用其他颜色了。 如果与其相邻的区域互不相邻，则可以是使用另一种相同的颜色。 如果它的相邻区域又有相邻关系，则就需要三种颜色。 只要有两块区域相邻，就意味着至少要两种颜色， 所以，对图5.1a，如果能用两种颜色完成涂色，就已经是最少颜色了。 * 事实上，图5.1b需要3种颜色，图5.1c需要4种颜色。 对于图5.1b，存在两两相邻的三个区域（图5.2中的A、B、C）， 如果A、B已经使用了两种颜色，那么C就只能使用第三种颜色了， 所以，如果能用三种颜色完成图5.1b的涂色，就已经是最少颜色了。 * 对图5.1c，区域A有5个相邻区域B、C、D、E、F， 其中B、C、D、E可以间隔使用另外两种颜色，这 样B和E使用的是不同的颜色，而F即不能和A相同， 也不能和B、E相同，只有使用第4种颜色了。 当人们面对一个全新的问题时，如果找不到一个现成的解决方案，经常会把各种可能的途径都尝试一遍。虽然试误的过