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

《图顶点m着色的一种新算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com1992年3月计算机学报第3期图顶点m着色的一种新算法2一I周_-●-六---_工一．程●-_l代____杰-一陈廷槐仍o／,(重庆太学计算机系，重庆63OO44)ANEWALGoRITHMFoRSoLVlNGVERTEXCoLoRINGPR0BLEMZhouLiuding，ChengDajieandChenTinghuaitD呻L4{Camg~ter-ChongUniwersisy，O63~044)AbstractAninceIi~gencbacktrackingalgorithmfors0lyingVertex-Co

2、loringPr。．HemispresentedAnalyticalandexperimentalresuitsshowthatiheirex．valgori&mbtef[hantheconventionaloneKeywordsImelligembad【tracking,vertexcoloring，algcJrithmanalv5is．摘要每文提出了一种求解目顶点m着色的“智能回湖算法．实验结果表明，时求解适当规模的顶点着色问题，新算法较常规算法快2～7倍．分析结果表明．对求解难度更大的这类问题，新算法刚会更优．星妻安析，，』一、引言图顶点m着色问题是～个ⅣP—c

3、组台问题，但它有着广泛的应用，其一是VLS!印刷电路制板．其定义是，在一个Ⅳ顶点的圈G(V，日)中，用m种色给G中所有顶点⋯，逐一着上，，}色中的一色，且使任两个相邻顶点异色．将其抽象成一般组合模型，就是求出对应于，，。，Ⅳ的一个N元组x一(，≈，⋯．)，其中．∈M一{1，2，3，⋯，}，且应满足给定的约束条件BoundⅣ(，如，--．，Ⅳ)，即对所有1．(1≤i<≤Ⅳ)，若与相邻则≠i．求解该问题的算法有两类：一类是Christofides算法，～类是DFS算法(即回溯算法)．本文1989年I1月17日收到．该算法尾国棠自然科学基金项目VLS

4、设计专家系统中的一部分

5、．周焘丁，千震庆大学获硕士学位翻博士学垃，丰鼋从事井行机体系牿构，串、并行革法，计算复杂性和^工智能的研究工作t疆代杰，重庆大学计算机系系主岳，教授，主要n亭并行机罐系培掏显并行处理、A工智能显专家系统的研究工作维普资讯http://www.cqvip.com3期周六丁等：图顶点m着色的一种新算法Chrlstofides算法的基本步骤是；用代数法求出G的所有极大独立集(，，·一。})，再对其中之一p(1≤i≤)求出G—的所有极大独立集(vl，V!，·一．})，·。。，这样可得到一组极大独立集(vi-，，⋯，)．它对应G的一种典型上色．若l≤m(m为给定的颜色数)，算法

6、正常结束．否则还需用回溯法寻找另一组极大独立集．该算法不易实现且计算代价仍很高，人们采用较少．DFS算法的基本步骤是；按递增选色序(假定m种色对应M一{l，2，3，·一，m})，首先确定的值，再按约束条件逐一确定，·一，一的『直．若在给定值耐找不到满足约束条件Bound~(x￡，：，⋯，)的任一值(Boundi(xl，，·--，∞一1，)，意指若与(1≤i≤j—1)相邻赃∞≠而)，则需回溯至Ⅱ上一层给一重新定一满足Boundj一．(，屯，·一，卸一)的值．若一的下一“台适”值存在，则向下试探，否则再可溯．缓算击人们常使用．二、DFS算法的弱点和新算法的思想及方法DFS

7、算法简单易行，但其效率较低．其原因是它从未利用试探一回溯过程的失败经验以加速．下面以图G顶点3着色(见图1)为例加以说明．假定用DFS算法已给G的，，·一，逐一着上一种满足约束条件的颜色(即“台适”色)，正对着一“台遣”色(图1括孤内是色标)．由于岫着1色将与，，的当前着色“冲突”，着2色将与如，当前着色“冲突，，着3色将与。当前着色“冲突”．这里定义两顶点，的着色“冲突”为：与f相邻且两顶点着同色．按DFS，需调整着色，调整的着色。再试给。着色，⋯⋯，要经过漫长的过程才能对的着色进行调整．事实上，由于，，巳分别着上l，2，3色且与它们均相邻，若，，的着色不调整，，是

8、无一“台适”色可着．而对，蜥，的反复调整垒是无用功．这是DFS法的一大弱点，因而我们想到用“智能”回溯策略取代DFS的逐层回溯策略，使之具有“智能”性和“完备”性．所谓“智能”佳意指能实现多层回溯(如从回嘲到．)，“完备”性意指若给定问题有解，该策略一定能找出所有解．图l图G顶点3着色时的一种格厨图2圈G预点3着色的一个解(，_．'已着色，正为着色)(括号中的数表示颜色标号)维普资讯http://www.cqvip.com计算机学报假定给定问韪有Ⅳ个顶点，有m种色可选并假定“智能回溯法按深度优先顺序逐一对，，⋯，试着色(这与DPS法相同)．下面讨论实