利用蚂蚁算法求解图着色问题.doc

利用蚂蚁算法求解图的着色问题利用蚂蚁算法求解图的着色问题第26卷第3期2005年9月内蒙古农业大学JournalofInnerMongo~:1009—3575(2005)03—0079—(天津大学管理学院,天津300072)摘要:图的着色问题是一典型的优化的问题,用蚂蚁算法求解图着色问题,,有效避免了解此问题时极易陷入局部极小的缺陷,重介绍了用蚂蚁算法解k***,:图的着色;蚂蚁算法中图分类号::AANTALGORITHMSFORS0L?NGGRAPHCOLoRINGWANGXiu—hong,ZHAOSheng—mill(SchoolofManagement,TianjinUniversity,Tianjin300072,China)Abstract:—efficiencyandhighastringencyofprocedurerunningavoidingunderstandingeffectivelythisproblemthehoursinksintothepartialdin—kyblemisheasiest,—,theemulationresultsshowedthesuperiorityofantalgorithmsinsol—vingoptimalbroblemsKeywords:GraphColoring;Antalgorithms1图的着色问题简介地图的着色问题是用不同的颜色给地图着色使得相邻的地区以不同的颜色表示,:用k种不同的颜色分别在n各地区上,使其相邻的颜色不同以使之易于区别,其约束条件为两个:?着的颜色数目为k;?,如果用多种颜色有限几个地区的地图着色,这个问题很容易解决,但是,如果要求用规定的少数几种颜色给1个有较多地区的地图着色,,早在100多年以前就有许多人对该问题感兴趣,【l基于顺序逼近的方法用计算机辅助证明和解决了4***着色问题,然而他们的方法在解决较大规模的问题时,花费的时间很长,计算时间与O(n)成正比(n为地图中的地区数)【,能在其走过的路径上释放1种信息激素,而且每个蚂蚁在运动过程中都能感知这种物质,