控制理论与应用

作者：吴征天,高庆

单位：苏州科技大学,北京航空航天大学

关键词：图分割问题; 屏障因子; 近似算法; 确定性退火控制算法

图分割问题是一种典型的NP-hard 问题, 如何对其进行高效求解一直都是学界和工业界的一个难题. 本文构建了一种新型的确定性退火控制算法, 提供了图分割问题的一种高质量近似解法. 算法主要由两部分构成: 全局收敛的迭代过程以及屏障函数最小点组成的收敛路径. 我们证明了，当屏障因子从足够大的实数降为0, 沿着一系列由屏障问题最小点组成的收敛路径可以得到图分割问题的一种高质量的近似解. 仿真计算结果表明本文所构建算法相比已有方法的优越性

来源：2019年第11期

《控制理论与应用》期刊编辑部

查看控制理论与应用杂志2019年第11期