论文部分内容阅读
无向赋权图剖分优化问题作为图论中的一个典型组合优化问题，在大规模集成电路设计、并行计算、数据挖掘、任务调度、知识发现、图像分割等领域有着广泛的应用。本文给出了无向图剖分优化问题的相关概念；从寻优策略的角度，将无向图剖分优化问题的求解算法分为构造性算法和迭代改进算法；分析了求解无向图剖分优化问题的迁移方法、几何方法、组合方法、谱方法、元胞自动机方法；重点讨论了多水平方法的粗化阶段、初始剖分阶段和优化阶段相应的匹配算法、初始剖分算法和迁移优化算法；介绍了无向图剖分优化问题的典型应用领域并指出了该问题今后的研究