k-着色问题及其均场退火求解算法

• 作者: 何志均 徐俊华 胡卫明
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 多层通孔最小化 k-着色问题 均场退火方法
• 年，卷（期）: 2000,（2）
• 页码范围: 256-259
• 页数: 4页
• 分类号: TP18
• 字数: 2996字
• 语种: 中文

摘要

均场退火方法既可以看作是一种新的神经网络计算模型,又可视为是对模拟退火的重大改进.该文把具有相邻约束的多层通孔最小化问题转换为更具广泛意义的k-着色问题,并提出了k-着色问题的均场退火求解算法.算法在线段相交图模型的基础上,提出了相邻矩阵和交叠矩阵等概念,并利用换位矩阵,将问题映射为相应的神经网络,再构造了该问题的能量函数.能量函数中的目标项、违背交叠约束的惩罚项、违背相邻约束的惩罚项和神经元归一化处理保证了网络能够求解到一个合法解.实验结果表明,这是一个有效的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何志均	浙江大学计算机科学与工程学系	27	407	11.0	19.0
2	胡卫明	北京大学计算机科学技术研究所文字信息处理技术国家重点实验室	9	106	4.0	9.0
3	徐俊华	北京大学计算机科学技术研究所文字信息处理技术国家重点实验室	3	8	2.0	2.0