南开大学计算机算法设计与分析培训资料.ppt

计算机算法设计与分析;引 子;有趣的问题;汉诺塔问题;绪 论;1.1 交通信号灯问题;1.1.3 图着色问题 已知：n点无向图G = V, E , ||V|| = n 。 求：G的最小色数(color number)k，使得用k种颜色对G的顶点着色，可令任二相邻顶点着色不同。 地图着色问题，交通信号灯问题都可以归结为图的顶点着色问题;2.图着色(Graph Coloring）问题 图着色问题是一个经典的组合算法问题，源于地图着色问题。 在绘制地图时，总是要求相邻的国家着上不同的颜色以示区别。1852年一位英国大学生古德里（F.Guthrie）提出了一个猜测：为了给任一个平面地图着色，并使任何有公共边界的区域颜色不同，至多需要四种颜色。这就是四色问题，又称四色猜想。古德里仅仅是提出了这个猜想，他和他的老师未能证明。;2. 图着色(Graph Coloring）问题 当把地图(Map)上的一个国家与图(Graph)上的一个顶点对应，两个国家的相邻关系对应于无向图上的边，于是，上面关于地图的“四色问题”实际上是无向图的顶点着色问题的特例。 无向图的顶点着色问题是一个有名的NP完全问题，这类问题属于“计算机难解”问题，关于着色问题算法的研究已有许多学者的大量成果。 ;Fig.1.2给出的无向图对应于五叉路口实例，该图有13个结点和20条边，其中ba, dc, ed三个顶点是孤立点，说明这三条路线与其它所有路线不相交，就是所谓的“拐小弯”。 ;1.1.4 算法设计讨论 1. 穷举法 令色数k从2开始，用k种颜色分别对13个顶点着色，共有k13种情形，当 K ＝ 5 时，需要进行 20 × ( 213 + 313 + 413 + 513 )次比较 。413=226 2. 剪枝法 对穷举法的改进。不必穷举所有可能的着色法，例如： 顶点ab着色为c1，则点ab的所有邻点ea, da, bc, bd都不必着色为c1；… 第一个点，例如ab，可以只着一种颜色，因颜色的对称性，ab取其它( k – 1 )种颜色的情形可不必再检查。此剪枝法一项可以把计算量缩小到原来的1/k。 3. 启发式(Heuristic)算法 依赖于人的直觉知识：为了用最小色数为所有顶点着色，也就是要每一种颜色在不出现冲突的条件下为尽量多的顶点着色。 ;算法1.1 启发式算法实现图着色 用k = 1, 2, 3,…来表示颜色1#, 2#, 3#, …, Color[i]=3表示对i顶点着3#色，i,j∈E表示顶点i,j相邻，Color[i]=0表示顶点i未着色 此法又称贪心法，比穷举算法和剪枝算法快得多，当n不太小时，其计算量比前者要少千万倍甚至更多，不过它不一定总是得到最优解。;1.1.4 讨论 1. 权衡(trade-off)的概念 穷举法：思想最简单、最直观，但计算量最大。 改进的穷举法：比前者要快，容许的n值可以再大一些，不过对于大的n，计算量仍会很大，它比穷举法有所改进的代价是程序较为复杂。 启发式的贪心算法：简单，快速，但不能保证总是得到最优解。 2. 最优性(Optimality) GreedyColor算法是一种“近似最优”算法。执行的结果是， k=4，13条路线分为4组：（括号里的路线为补充的不冲突项） ab , ac , ad , ba , dc , ed ; bc , bd , ea ,(ba , dc , ed); da , db ,(ba , dc , ed , ad); eb , ec ,(ba , dc , ed , ea).;一般的说可能还有更好的分组方法，例如分为三组。不过，在这个实例中，却不难证明分为4组已不能改进。这是因为从Fig.1.2中发现ac, bd, da, eb 4个顶点组成一个完全子图（又称团，Clique），4点的无向完全图至少需4色，因此这个解已不可改进。 ;3.算法设计讨论 · 算法的研究与许多实际应用问题直接相关，它不仅是个理论问题； · 一些典型的算法问题的研究，如着色问题、旅行商问题、背包问题等等，常常在应用算法的设计中发挥作用； · 用来解一个问题，可以有多种不同的算法，它们的效果可能差别很大，如何设计有效的算法是算法理论的主要目标。 ;1.2 什么是算法;1.2.2 算法与问题 例： 整数乘法问题 全部可能输入集合：{ a,b|a,b∈Z }，其中Z表示整数集； 一个实例：2, 4,求：2 × 4 = ? 旅行商问题( Traveling Salesman Problem ) 实例集为：{ n , Wn*n = [Wij] | n∈Z , Wij∈R , i ,