启发式算法求解最大团问题研究.pdf

第28 卷 第18 期 计算机工程与设计 2007 年9 月 Vol . 28 N o. 18 Computer Engineering and Design Sept . 2007 启发式算法求解最大团问题研究 1 2 崚1,2,3 周旭东 ， 王丽爱 ， 陈 (1. 扬州大学信息工程学院计算机中心，江苏扬州225009 ；2. 扬州大学信息工程学院计算机系， 江苏扬州225009 ；3. 南京大学软件新技术国家重点实验室，江苏南京210093) ( ) 摘 要：最大团问题maximum clique problem ，MCP 是图论中的一个经典组合优化问题，也是一类NP 完全问题，在国际上已有 广泛地研究，国内研究刚刚起步。给出了最大团问题的基本定义和其数学描述；阐述了该问题的研究进展；分析和研究了求 解该问题的各种典型启发式算法，包括算法的介绍、算法求解最大团问题的基本思路、特点及性能；最后介绍了测试这些启 发式算法性能的测试基准图。 关键词：最大团问题; 启发式算法; 组合优化; 确定性算法; 图 中图法分类号：TP 18 文献标识码：A 文章编号：1000-7024 (2007) 18-4329-04 Research on using heuristic algorithms to solve MCP 1 2 1,2,3 ZHOU Xu-dong , WANG Li-ai , CHEN Ling (1. Computer Center, College of Information, Yangzhou University, Yangzhou 225009, China; 2. Department of Computer, College of Information, Yangzhou University, Yangzhou 225009, China; 3. National Key Lab of Novel Software Technology, Nanji ng University, Nanjing 210093, China) Abstract ：The maximum clique problem (MCP) is a classical problem of combinatorial optimization in graph theory, and is a kind of NP-Complete problem. MCP has been widely researched internationally, however, in china the research of it is just beginning. The definition of MCP is described; the development about using heuristic algorithms to solve MCP is expounded; a variety of typically heu- ristic algorithms solving MCP are analyzed and researched, including introducing about these algorithms, their basic ideas and charac- teristics and performances