基于分治策略和蚁群算法的最大团问题的研究

On Maximum Clique Problem Based on Divide and Conquer and Ant Colony Optimization

最大团问题是经典的NP-hard问题,对该问题求解方法的研究在理论上、实践上都具有一定的意义.蚁群算法已成功地求解出许多组合优化难题.通过使用分治法,将图分解成子图,对各子图应用蚁群算法求解,提出一种求解最大团问题的蚁群算法.它减小了问题的求解规模,使求解变得容易,且实验取得了较好的结果.

Maximum clique problem（MCP） is a classic NP-hard problem.Making a study of method on the problem,whether in theory or in practice have a certain significance.Ant colony optimization（ACO） was applied successfully to hard combinational optimization problems.In this article,divide and conquer is used and graph is decomposed into sub-graph and then in these sub-graph ACO is used to solving MCP.Ant colony optimization of solving maximum clique problem（ACOMCP） is put forward.It reduces the size of the problem and makes problem solving easier.The simulation results show that the algorithm is more efficient.