Institutional Repository
| GPP问题的骨架分析与启发式算法设计 | |
| Alternative Title | backbone analysis and heuristic design for the graph partitioning problem |
| 江贺; 邱铁 | |
| 2009 | |
| Source | 计算机学报
 |
| ISSN | 0254-4164 |
| Volume | 32Issue:8Pages:1662-1667 |
| English Abstract | 图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值. |
| Indexed Type | 其他 |
| Keyword | 图的划分问题 |
| Department | 大连理工大学软件学院,大连,辽宁,116621;中国科学院软件研究所计算机科学国家重点实验室,北京,100190;大连理工大学软件学院,大连,辽宁,116621 |
| Language | 中文 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8002 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | 江贺,邱铁. GPP问题的骨架分析与启发式算法设计[J]. 计算机学报,2009,32(8):1662-1667. |
| APA | 江贺,&邱铁.(2009).GPP问题的骨架分析与启发式算法设计.计算机学报,32(8),1662-1667. |
| MLA | 江贺,et al."GPP问题的骨架分析与启发式算法设计".计算机学报 32.8(2009):1662-1667. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| GPP问题的骨架分析与启发式算法设计.p（493KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment