超图划分问题的元胞自动机模型及算法研究

摘要：

对超图划分问题运用元胞自动机理论进行分析建模,提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法.在该模型中,元胞对应于赋权超图中的结点,邻接元胞对应于邻接超边所包含的结点,元胞的状态对应于所在的划分子集.引入二维辅助数组存储每条超边在划分子集中的结点个数,给出快速的元胞收益值和划分割切值的计算方法,从而避免遍历超边中的结点.实验结果表明,与赋权图划分算法和迁移方法相比,该算法可以取得更优的划分,且时间复杂度和空间复杂度较低.

关键词：赋权超图、划分算法、元胞自动机、时间复杂度、空间复杂度

所属期刊栏目：38

分类号：N945.12(系统科学)

资助基金：国家自然科学基金资助项目61063007,61163062,61106030;江西省自然科学基金资助项目2009GQS0060;江西省教育厅科学技术研究基金资助项目GJJ12474,GJJ10201,GJJ09590,赣教技字[2007]320号

在线出版日期：2012-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：23-27