| 引用本文: | 吴征天,高庆.面向图分割问题的确定性退火控制算法[J].控制理论与应用,2019,36(11):1936~1941.[点击复制] |
| Wu Zheng-tian,Gao Qing.A deterministic annealing control algorithm for a general graph partitioning problem[J].Control Theory and Technology,2019,36(11):1936~1941.[点击复制] |
|
| 面向图分割问题的确定性退火控制算法 |
| A deterministic annealing control algorithm for a general graph partitioning problem |
| 摘要点击 1960 全文点击 727 投稿时间：2019-07-01 修订日期：2019-09-23 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2019.90508 |
| 2019,36(11):1936-1941 |
| 中文关键词 图分割问题 屏障因子 近似算法 确定性退火控制算法 |
| 英文关键词 graph partitioning problem barrier parameter approximated algorithm deterministic annealing control algorithm |
| 基金项目 |
|
| 中文摘要 |
| 图分割问题是一种典型的NP-hard 问题, 如何对其进行高效求解一直都是学界和工业界的一个难题. 本文构建了一种新型的确定性退火控制算法, 提供了图分割问题的一种高质量近似解法. 算法主要由两部分构成: 全局收敛的迭代过程以及屏障函数最小点组成的收敛路径. 我们证明了，当屏障因子从足够大的实数降为0, 沿着一系列由屏障问题最小点组成的收敛路径可以得到图分割问题的一种高质量的近似解. 仿真计算结果表明本文所构建算法相比已有方法的优越性 |
| 英文摘要 |
| The graph partitioning problem is well known to be NP-hard and it is still a challenge to solve this problem effectively. In this paper, a new deterministic annealing control algorithm is developed, with which an approximation solution to a general graph partitioning problem is obtained. This algorithm can be decomposed into a globally convergent iterative procedure and a path of minimum points of a barrier problem. In the algorithm, a high-quality solution is obtained along a path of a series of barrier problems’ minimum points when the barrier parameter decreases to 0. Simulation results show the advantages of the proposed algorithm over the existing approach. |