图顶点m着色的一种新算法.pdfVIP

维普资讯 1992年3月 计 算 机 学 报 第3期 图顶点m着色的一种新算法 2 一 I 周六工． 程代杰 陈廷槐 仍 o／, _ - ● - - - - _ 一 ●- _ l_ _ _ _ - 一 (重庆太学计算机系，重庆 63OO44) A NEW ALGoRITHM FoR SoLVlNG VERTEX CoLoRING PR0BLEM ZhouLiuding，ChengDajie and ChenTinghuai tD呻L 4{Camg~ter-Chon g Uniwersisy，O 63~044) Abstract An inceIi~gencbacktrackingalgorithm for s0lying Vertex-Coloring Pr。． Hem ispresented Analyticaland experimentalresuitsshow thatihe irex ．v algorim b tef [han theconventionalone Key words Imelligem badt【racking,vertex coloring algcJrithm analv5is． ， 摘要 每文提 出了一种求解 目顶点m着色的 “智能 回湖算法．实验结果表明， 时求解适 当规模的顶点着色问题 ，新算法较常规算法快 2～7倍． 分析结果表 明．对求解难度更大的这类问题 ，新算法 刚会更优． 星星妻安析析，，』』 一 、 引 言 图顶点m着色问题 是～个 ⅣP—c组台问题 ，但它有着广泛的应用，其一是 VLS! 印刷 电路制板 ． 其定义是，在一个 Ⅳ顶点的圈 G(V，日)中，用m种色给G中所有顶 点 … ， 逐一着上，，}色中的一色，且使任两个相邻顶点异色．将其抽象成一般组 合模型，就是求出对应于 ， ， 。，Ⅳ的一个N元组 x一 ( ，≈，… ． )，其中 ． ∈M 一 {1，2，3，… ， }，且 应满足给定的约束条件 BoundⅣ( ，如，--．， Ⅳ)，即对 所有 1．(1≤ i ≤Ⅳ)，若 与 相邻则 ≠ i． 求解该问题的算法有两类： 一类是 Christofides算法 ，～类是 DFS算法(即回 溯算法) ． 本文 1989年 I1月 17日收到．该算法尾国棠 自然科学基金项 目 VLS|设计专家系统 中的一部分．周焘丁，千 震庆大学获硕士学位翻博士学垃，丰鼋从事井行机体系牿构，串、并行革法，计算复杂性和^工智能的研究工 作t疆代杰，重庆大学计算机系系主岳，教授，主要n亭并行机罐系培掏显并行处理、A工智能显专家系统的研 究工作 维普资讯 3期 周六丁等：图顶点 m着色的一种新算法 Chrlstofides算法的基本步骤是；用代数法求出G的所有极大独 立 集 ( ， ，·一。 })，再对其中之一 p(1≤ i≤ )求出 G—