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

The graph partitioning problem is a typical NP - hard problem, and how to solve it efficiently has always been a difficult problem in academia and industry. This paper constructs a new deterministic annealing control algorithm and provides a high - quality approximate solution to the graph partitioning problem. The algorithm mainly consists of two parts: a globally convergent iterative process and a convergence path composed of the minimum points of the barrier function. This paper proves that when the barrier factor decreases from a sufficiently large real number to 0, a high - quality approximate solution to the graph partitioning problem can be obtained along a series of convergence paths composed of the minimum points of the barrier problem. The simulation calculation results show the superiority of the algorithm constructed in this paper compared with the existing methods.

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