37求图着色问题的新算法
上亿文档资料，等你来发现
37求图着色问题的新算法
第25卷第4期2004年7月；微计算机应用；MICROCOMPUTERAPPLICATION；Vol.25,No.4Jul.,2004；求图着色问题的新算法3；陈卫东；(华南师范大学计算机系广州510631)；摘要:图着色问题是NP-难度的问题；关键词:图着色NP难度时间复杂度启发式算法；NewAlgorithmsChinaNormal；Keywords:g
第25卷第4期2004年7月微计算机应用MICROCOMPUTERAPPLICATIONSVol.25,No.4Jul.,2004求图着色问题的新算法3陈卫东(华南师范大学计算机系广州510631)摘要:图着色问题是NP-难度的问题。基于两种传统的启发式算法,提出了两种新的求解策略,由此给出了求图着色问题的两个新算法。与传统算法相比,其中一个新算法在时间复杂度不变的条件下,解的质量有明显提高;另一个则在时间复杂度稍有增加的前提下,显著地提高了所得解的质量。关键词:图着色　NP难度　时间复杂度　启发式算法NewAlgorithmsChinaNormalUniversity,Guangzhou,510631,China):GraphColoringProblem(GCP)isNP2hard.Analyzingtwowell2knownheuristical2,paperproposestwonovelstrategiesforsolvingGCP,andgivestwonewheuristicalgo2rithmsforGCPbasedthesestrategies.Experimentalresultsshowonealgorithmoutperformsthesetwoknownalgorithmsandtheothergreatlyimprovesonthequalityofsolutionswithalittlehighertimecom2plexity.Keywords:graphcoloring,NP2hardness,timecomplexity,heuristicalgorithm1　问题描述给定一个无环的无向图G=&V,E&,V是图的点集,E是图的边集。一个映射C:V→{1,2,…,k},若满足对任意(u,v)∈E,均有C(u)≠C(v),则称C为G的一个正常k-点着色。如果图G存在正常k-点着色,则称图G是可正常k-点着色的。图G的色数,记作((G),是指G为可正常k-点着色的最小k值。为了方便后面的描述,对于任意点u∈V,用N[u]={u}∪{v|(u,v)∈E}表示u的(闭)邻域。χ(G)-点着图的着色问题是指,针对任意给定的无环无向图G,要求找出图G的正常色。这是很有实用背景的一个组合优化问题,在调度安排、课表编制等许多方面有广泛应用[1～3]。由于其NP-难度的性质[4]及广泛的实用性,对它的求解算法进行研究具有较大的理论与现实意义。对于NP-难度的问题,若要求出问题的精确最优解,现存的任何算法的时间复杂度都是本文于收到,收到修改稿。3　基金项目:国家自然科学基金资助项目();广东省自然科学基金资助项目(021072)。392　微计算机应用2004年指数型,这对于中等规模的问题也是不现实的。因此,人们往往退而求其次,满足于能快速地找到问题的近似最优解。对于图着色问题,即要求能快速找到给定图的具有尽可能小k值的正常k-点着色。一些通用算法模型,比如禁忌搜索、模拟退火、遗传算法等都是可用于此目的的启发式方法。还有一类直接根据问题的特性设计的启发式算法,我们称之为直接启发式算法,这些方法往往简单易用,并且如果启发式信息得当,效果非常好。文献[5]中总结了用于求解图着色问题的各种启发式方法。从实用角度来看,最有名的直接启发式算法是增强SEQ算法和DSATUR算法[1,5]。基于这两种算法,人们研制了一些更为巧妙的算法,算法解的质量提高了,但是由于其过于复杂基本不能实用。本文分析了这两个传统的直接启发式算法的特点,提出了两种新的求解策略,由此给出了两个新算法。与两个传统的算法相比,新算法保持了简单易用的特点,并且其中一个新算法在时间复杂度不变的条件下,较明显地提高了解的质量,另一个则在时间复杂度稍有增加的前提下,进一步显著地提高了所得解的质量。2　传统的直接启发式算法两个传统的直接启发式算法即增强SEQ算法和而著名。。,假设颜色被依次编号为{1,,(1)增强:,着。一个结点着色后将它及其相关联的边看作从图中去。重复上述过程,直到所有结点都被着色为止。所用颜色的最。该算法的直观意义在于,优先处理使用旧颜色(目前已用过至少一次的颜色)着色容易发生冲突的结点,且在着色时尽可能使用旧颜色。(2)DSATUR算法的基本思想:每次挑选那个其邻域内已用颜色数目达最多的结点进行着色,着色时使用的颜色是编号最小的可用颜色。重复上述过程,直到所有结点都被着色为止。所用颜色的最大编号即为所用颜色数。从直观上看,给其邻域内已用颜色数目达到最多的结点优先着色,希望最终用在该邻域中的颜色数目较少,且在着色时尽可能使用旧颜色。这两个算法的最坏时间复杂度都是O(n3),其中n是图中结点个数。根据实验情况,这两个算法的效果都不错。相对而言,增强SEQ算法的结果比较依赖于图中结点的原有次序,而DSATUR算法在这图1　图着色问题的一个实例方面的鲁棒性能较好。例如,对于图1的两种结点次序(a1,a2,a3,a4,b1,b2,b3,b4)和(a1,b1,a2,b2,a3,b3,a4,b4),增强SEQ算法所用颜色数分别为2和4,而DSATUR算法所用颜色数都是2。通过分析我们发现,这两个算法的一个明显区别在于,前者关注的是结点邻域内将来的情况,即未着色的结点;而后者关注的是过去,即已经用过的颜色数目。此外,它们都有一个不足的地方,即只着眼于结点邻域这个局部范围的情况,而没有很好地兼顾全局。针对这两点,本文提出如下改进措施:第一,将两个传统算法结合起来,得到一个既关第4期微计算机应用　393注结点邻域的将来又关注其过去的策略,即最大潜在色数优先策略;第二,采用一个策略来在一定程度上能展望全局的情况,即前景评估策略。3　新的策略和算法311　最大潜在色数优先策略设点v的邻域N[v]中已着色结点的不同颜色数目为C1(v),尚未着色的结点个数为C2(v),用C3(v)=C1(v)+(C2(v)表示邻域N[v]中潜在的色数,其中α是(0,1)之间的一个实数。(值的确定原则是要使得在C3(v)中C1(v)占主导地位,同时又要考虑到C2(v)的作)m/n2,其中n、用,其大小与图的边稠密程度有关。根据实验的较佳效果,取α=015(1-ρm分别表示图中顶点数和边数,ρ=2m/(n(n-1))表示图的边稠密度。最大潜在色数优先策略即,每次选择潜在色数值C3(v)最大的结点v,且在着色时使用编号最小的可用颜色。该策略的直观意义在于,,,如果不优先处理,,启发式算法的思想,既看到了过去,,比较全面。不难看出,对于图1,,使用潜在最大色数优312。其基本思想是,根据最大潜在色数优先的原v,然后找出v的所有可用的旧颜色再加上一种新颜色构成v的候选可用颜色集CA(v)。此时并不是给结点v着编号最小的可用颜色,而是对每一种可用颜色都进行评估,选出评估结果最好的颜色给结点v。具体来说,对于每一个c∈CA(v),尝试给结点v着色c之后继续使用最大潜在色数优先策略将整个图中结点都着色完,并将最后所用颜色数目作为当前格局下结点v使用颜色c的前景评估值Eval(v,c)返回。令c3是其中评估值为min{Eval(v,c)|c∈CA(v)}的颜色。由此确定给结点v着颜色c3。在新的格局下来重复这一过程直到图中所有的结点都被着色为止。由此可见,该策略并不局限于给结点选择编号最小的可用颜色,而是有可能选择前景更好的其它颜色。其直观表示如图2所示。313　新算法根据最大潜在色数优先策略形成的算法记作GC1。前景评估策略实际上是以算法GC1为基本算法的策略,据此形成的算法记作GC2。其形式化描述如下。ProcedureInput:Output:GC2图2　前景评估策略示意图图G=&V,E&,备用颜色集C={1,2,…,n},其中n=|V|所用颜色数目k以及一种k-点着色方案394Begin　微计算机应用2004年初始化工作fori=1tondo根据最大潜在色数优先的原则来确定要着色的结点v确定v的候选可用颜色集CA(v)对于CA(u)中的每一种颜色c计算其评估值Eval(v,c),并令c3是其中评估值最小的颜色给结点v着颜色c3endfor返回所用的颜色数及对应的着色方案End在前景评估策略中,当然可用两个传统算法中的任何一个来代替GC1作基本算法使用,且效果一定不比原有基本算法差(见定理312)。例如,SEQ算法作为基本算法,用之求解图1所表示的实例,则无论图中结点原有次序如何,2种颜色即可完成着色任务。但是,一般说来,基本算法效果越好,314　算法分析定理311:对于图中结点个数为n的实例,1O(n3),算法GC2的最坏时间复杂度为O(n5)证明:在算法GC1,O(n2),然后给选好的结点确On2),因此完成图中所有n个结点的着色需要的时间为(n)中,O(n2),然后给选好的结点O(n2),对每个可用颜色计算其评估值需要时间为O(n3)(即算法GC1的时间),而可用颜色集中最多可能有n种颜色,从而完成一个结点的着色需要时间O(n4)。因此算法GC2的最坏时间复杂度为O(n5)。证毕。由图2容易知道,算法GC2的搜索范围包含了算法GC1的搜索范围,故有如下结果:定理312:算法GC2所得解的质量不低于算法GC1所得解的质量。4实验结果使用C语言编程,在PentiumⅢ的PC机上对随机产生的实例分别使用两个传统直接启发式算法和两个新算法进行求解,实验统计结果见表1。表1中n表示实例图中的顶点数,ρ表示实例图中的边稠密度。表1中每行代表20个随机实例的平均结果(从实验角度看,一般来说,对n,ρ一定的实例,同一算法所得色数相差不大,且所需运行时间也相差不大)。表1　四种算法在随机实例上的性能比较实例描述(每行20个实例)n增强SEQ算法色数DSATUR算法GC1算法GC2算法β时间&05色数时间&5色数时间&5色数5101917时间第4期微计算机应用　395续表实例描述(每行20个实例)n增强SEQ算法色数150DSATUR算法GC1算法GC2算法β时间&50105色数150时间45色数150时间45色数150时间2色数是指同一算法求解20个实例所得色数的平均值,时间是同一算法求解这些实例所需时间的平均值,时间单位为秒。色数值越小表示解的质量越高,越快。从表中数据可以看出:(1)对n,ρ一定的实例,平均来看,算法解的质量,而时间则相差不大。当然,GC1在极个别实例上所得解的质量反而变差的情况。(2)算法,但运行时间要,,算法GC2的稳定性能较好,它在我们随机产生的所有实例。在实际应用中可以根据对时间和解质量的要求来决定选用算法GC1或GC2。5结束语尽管本文给出的两个算法效果都优于两个传统的直接启发式算法,但在某些方面仍然有待改进。比如,需要进一步研究更合理地调整潜在色数中的权值(,使得算法GC1的表现更佳。此外,本文讨论的几种算法都是构造型算法,即逐步给图中结点着色最后才形成完整的着色方案。还有一类改进型方法,它们是对已有的完整着色方案不断进行改进和优化。可以考虑将本文的算法与某些改进型的算法结合起来,以期形成性能更好的算法。参　　考　　文　　献1　A.SCHAERF,ASurveyofAutomatedTimetabling.ArtificialIntelligenceReview13:87～127,1999.2　刘根泉,王树禾,肖国龙.频率分配与图的着色.电子学报,):38～463　徐　杰等.基于模拟退火算法和图的着色的调车机车安排研究.铁道学报,):24～304　M.Garey,D.Johnson,ComputersandIntractibility:AguidetothetheoryofNP2completeness,W.H.FreemanandCompany,NewYork,1979.5　D.deWerra,Heuristicsforgraphcoloring,Computing7(～208作者简介陈卫东,男(1968年生),讲师,主要研究方向为组合优化、启发式算法。包含各类专业文献、外语学习资料、应用写作文书、专业论文、幼儿教育、小学教育、各类资格考试、文学作品欣赏、37求图着色问题的新算法等内容。
　喜欢此文档的还喜欢 图的染色问题 6页 免费 着色问题分析 35页 免费 图的着色问题 40页 免费 图论学生论文 7页 免费 求图着色问题的新算法 5页 免费... 　(在本文中主要讨论顶点着色) 3、算法的基本思想 目前求图着色问题主要有以下几...在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为 一个新... 　图着色问题_IT/计算机_专业资料。回溯经典-m 图着色问题( 回溯经典 图着色问题...求图着色问题的新算法 5页 免费 第八章 图 (图着色) 17页 免费喜欢... 　图节点着色问题中的禁忌搜索算法_自然科学_专业资料。...图的节点着色问题可以描述为: 求一个最小的k,使得...把s*作为一个新解,重新叠代搜索, 直到满足退出... 　这个新结点就成为一个新的活结点,并 成为当前扩展结点。 如果在当前的扩展结点...求一个图的色 数 m 的问题称为图的 m 可着色优化问题。设计一个算法,找出... 　数学实验大作业-图的着色 1136005 班 摘要:图的着色问题是典型的优化问题,用 Matlab 求图的着色的色多项式问题,运用 B-L 约化算法求解。本文将从背景知识、数学... 　简单图着色问题探讨_法律资料_人文社科_专业资料。简单图着色问题探讨 摘要:图着色在与调度和分配有关的问题中具有多种应用,探讨了 图着色的一种算法,并给出了这... 　智能的理论、方法、技术及应用系统的一门新的技术...回溯法是一种系统地搜索问题解的搜索算法。 回溯法...如不合理则换另一种颜色值,根据图的 4 色 定理... 　如果存在 这样的着色 方法,则说图 G 是 m-可着色的,这样的着色称为图 G ...这可在着色问题的 回溯算法初次 调用该函数时赋予初值:X[i]=0,i=1,2,…,...这是什么图 求各位大侠看看 说说怎么上色。。。我纹了忘了是叫什么名字了 上什么色 最好有原图
这是什么图 求各位大侠看看 说说怎么上色。。。我纹了忘了是叫什么名字了 上什么色 最好有原图
其他回答 (1)
这应该是钟馗和小鬼的纹身。
相关知识等待您来回答
电影电视领域专家
& &SOGOU - 京ICP证050897号求坂田银时的一张图，最好是不上色的，就是只用黑线勾勒的
求坂田银时的一张图，最好是不上色的，就是只用黑线勾勒的 20
就是要漫画里的那种。
最好截的是银时的侧脸，或者半个身子也行。
还有，最好带上“洞爷湖”仨字。
最最最最最最最重要的是，要好看。
&= =。我发现我的要求……不少哈。
劳烦大家了。
补充：俺要想自己搜还来问问干啥……
其他回答 (2)
自己上宜搜找多得是
相关知识等待您来回答
动漫领域专家
& &SOGOU - 京ICP证050897号