求解Ramsey数下界的模拟退火算法

doi:10.3778/j.issn.1002-8331.2009.07.022

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (7): 70-71.DOI: 10.3778/j.issn.1002-8331.2009.07.022

求解Ramsey数下界的模拟退火算法

邵泽辉¹,王子成¹,肖建华²

1.华中科技大学控制科学与工程系，武汉 430074
2.南开大学现代物流研究中心，天津 300071

收稿日期:2008-12-02 修回日期:2009-01-19 出版日期:2009-03-01 发布日期:2009-03-01
通讯作者: 邵泽辉

Lower bounds for Ramsey numbers based on simulated annealing algorithm

SHAO Ze-hui¹,WANG Zi-cheng¹,XIAO Jian-hua²

1.Department of Control Science and Engineering，Huazhong University of Science and Technology，Wuhan 430074，China
2.Research Center of Logistics，Nankai University，Tianjin 300071，China

Received:2008-12-02 Revised:2009-01-19 Online:2009-03-01 Published:2009-03-01
Contact: SHAO Ze-hui

摘要/Abstract

摘要： 对于图G₁、G₂，2色广义Ramsey数R（G₁，G₂）是指最小正整数p，使得每一个p阶的图G，或者G包含G₁，或者G的补图包含G₂。用改进的模拟退火算法求解得到了R（W_m，K_n），R（B_m，K_n），R（F_m，K_n），类型的一些Ramsey数的下界。

关键词: Ramsey数, 模拟退火, 边着色, 循环图

Abstract: For given graphs G₁，G₂，the 2-color Ramsey number R（G₁、G₂） is defined to be the least positive integer p such that every 2-coloring of the edges of complete graph K_p contains a monochromatic copy of G_i colored with i，for 1≤i≤2.With the help of simulated annealing algorithm，some lower bounds of Ramsey numbers for the families R（W_m，K_n），R（B_m，K_n），R（F_m，K_n） is obtained.

Key words: Ramsey number, simulated annealing, edge coloring, cyclic graph

邵泽辉¹,王子成¹,肖建华². 求解Ramsey数下界的模拟退火算法[J]. 计算机工程与应用, 2009, 45(7): 70-71.

SHAO Ze-hui¹,WANG Zi-cheng¹,XIAO Jian-hua². Lower bounds for Ramsey numbers based on simulated annealing algorithm[J]. Computer Engineering and Applications, 2009, 45(7): 70-71.

[1]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[2]	童文林，陈德旺，黄允浒，吕宜生. 结合模拟退火与规则约简的模糊系统优化方法[J]. 计算机工程与应用, 2021, 57(16): 142-150.
[3]	张凯，靳鹏，崔勇. 带时间窗的多车型需求可拆分揽收配送问题[J]. 计算机工程与应用, 2021, 57(14): 281-288.
[4]	禹忠，顾仁彬，范九伦. 基于LBT-SA的LoRaWAN信道接入方法研究[J]. 计算机工程与应用, 2020, 56(24): 95-101.
[5]	陈桂兰，奚宝华，杨兰英. 改进混合粒子群算法的立体车库存取调度[J]. 计算机工程与应用, 2019, 55(19): 263-270.
[6]	孙波，姜平，周根荣，卢易天. 改进遗传算法在移动机器人路径规划中的应用[J]. 计算机工程与应用, 2019, 55(17): 162-168.
[7]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[8]	俞武扬，周洋. 改进柔性隔间结构的不等形面积设施布局研究[J]. 计算机工程与应用, 2019, 55(14): 221-227.
[9]	刘兰芬，杨信丰. 基于混合遗传算法的有效路径求解[J]. 计算机工程与应用, 2019, 55(11): 244-249.
[10]	毛丽丽，张则强，朱立夏. 混合模拟退火及分散搜索优化过道布置问题[J]. 计算机工程与应用, 2018, 54(3): 243-249.
[11]	夏以冲，陈秋莲，宋仁坤. 基于自适应遗传模拟退火算法的矩形件排样[J]. 计算机工程与应用, 2018, 54(22): 229-232.
[12]	汪开普，张则强，邹宾森，毛丽丽. 模糊作业时间的拆卸线平衡Pareto多目标优化[J]. 计算机工程与应用, 2018, 54(1): 256-263.
[13]	邹积涛1，徐兰2，曾祥春1，王友正1，王超1. 考虑多专业协同的装配线平衡问题研究[J]. 计算机工程与应用, 2017, 53(7): 263-270.
[14]	李腾宇，易晓梅，陈石. 基于RSSI加权质心和GASA优化的WSN定位算法[J]. 计算机工程与应用, 2017, 53(6): 118-121.
[15]	张荣光，胡晓辉，宗永胜. 基于改进离散粒子群优化的连续属性离散化[J]. 计算机工程与应用, 2017, 53(18): 108-114.

求解Ramsey数下界的模拟退火算法

Lower bounds for Ramsey numbers based on simulated annealing algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics