图顶点着色问题是组合最优化中典型的NP难问题,也是图论中研究得最久的一类问题,有着广泛的实际应用。针对图着色问题的大规模实例的近似算法有很多种,比如遗传算法、模拟退火算法、蚁群算法、禁忌搜索算法以及很多复合以上基本近似算法的混合算法等。　　禁忌搜索算法(tabu search)是一种局部搜索算法,它常能有效的应用于一些典型组合优化问题,它在图着色问题已有很好的应用。格局监测策略是在最小顶点覆盖问题上提出的改进禁忌算法的一种策略,并已经在最小顶点覆盖问题和SAT问题上证实能明显改进禁忌算法的效率。　　本文主要工作是在已有的图着色禁忌算法的基础上应用格局检测(CC)这一策略,设计了一种新的算法来改进已有的算法,并通过实验数据纵向对比基本的图着色问题的禁忌搜索算法以及横向对比模拟退火等其他图着色问题的近似算法的效率,来验证格局检测策略在图着色问题上的有效性,以及这种策略在组合优化问题上有一定的普适性。