面向图分割问题的确定性退火控制算法

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.