Perfect Code问题的加权分治算法

• 作者: 宁爱兵 支志兵 杨晓芳 王英磊
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 加权分治技术 Perfect Code问题 分支降阶技术 算法复杂性
• 年，卷（期）: 2014,（3）
• 所属期刊栏目: 人工智能与算法
• 页码范围: 594-596
• 页数: 3页
• 分类号: TP301
• 字数: 3093字
• 语种: 中文

摘要

加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂度更好的精确算法.Perfect Code问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂度为O(1.3248np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂度低于采用传统方法得到的时间复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵	上海理工大学管理学院	59	341	11.0	15.0
2	王英磊	上海理工大学管理学院	4	11	2.0	3.0
3	杨晓芳	上海理工大学管理学院	62	311	10.0	14.0
4	支志兵	上海理工大学管理学院	8	14	2.0	3.0