###
DOI:
Journal of Software:2000.11(2):256-259

k-着色问题及其均场退火求解算法
胡卫明,徐俊华,何志均
(北京大学计算机科学技术研究所文字信息处理技术国家重点实验室,北京,100871;浙江大学计算机科学与工程学系,杭州,310027)
A Mean Field Annealing-Based Algorithm for k-Colorable Problem
HU Wei-ming,XU Jun-hua,HE Zhi-jun
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2459   Download 2294
Received:September 21, 1998    Revised:March 05, 1999
> 中文摘要: 均场退火方法既可以看作是一种新的神经网络计算模型,又可视为是对模拟退火的重大改进.该文把具有相邻约束的多层通孔最小化问题转换为更具广泛意义的k-着色问题,并提出了k-着色问题的均场退火求解算法.算法在线段相交图模型的基础上,提出了相邻矩阵和交叠矩阵等概念,并利用换位矩阵,将问题映射为相应的神经网络,再构造了该问题的能量函数.能量函数中的目标项、违背交叠约束的惩罚项、违背相邻约束的惩罚项和神经元归一化处理保证了网络能够求解到一个合法解.实验结果表明,这是一个有效的算法.
Abstract:The mean field annealing approach is a new neural network model,which improves the simulated annealing approach greatly.In the paper,the via minimization problem in multi-layer routing with adjacent constraints is translated to a k-colorable problem which has more general meanings,and a mean field annealing algorithm for the k-colorable problem is proposed.On the basis of the segment-crossing graph model,the adjacent matrix and the crossing matrix are introduced.A permute matrix of binary variables is used to map the problem to the neural network,and then the energy function is presented.The object item,crossing constrained item and adjacency constrained item in the energy function,and the normalization of neurons prove that the effective result can be gotten.The experimental results show that it is an effective method.
文章编号:     中图分类号:    文献标志码:
基金项目:本文研究得到国家自然科学基金(No.69576009)和中国博士后科学基金资助. 本文研究得到国家自然科学基金(No.69576009)和中国博士后科学基金资助.
Foundation items:
Reference text:

胡卫明,徐俊华,何志均.k-着色问题及其均场退火求解算法.软件学报,2000,11(2):256-259

HU Wei-ming,XU Jun-hua,HE Zhi-jun.A Mean Field Annealing-Based Algorithm for k-Colorable Problem.Journal of Software,2000,11(2):256-259