-
题名加权集合覆盖问题的加权分治算法
被引量:5
- 1
-
-
作者
胡琳琳
宁爱兵
黄飞
刘志民
张惠珍
-
机构
上海理工大学管理学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2016年第5期987-991,共5页
-
基金
国家自然科学基金项目(71401106)资助
上海市一流学科建设项目(S1201YLXK)资助
高等学校博士学科点专项科研基金联合课题(20123120120005)资助
-
文摘
加权分治技术是一种用于算法分析和设计的新方法,该技术通过对处理对象按不同重要程度而赋予不同的权值来更加精确的描述算法分支子问题规模的大小,从而降低算法的时间复杂度.分支降阶技术是广泛用于求解组合优化领域难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并用递归来求解这些子问题.加权集合覆盖问题是一个典型的NP难题,利用加权分治技术对集合覆盖问题进行研究,给出了一个精确算法,降低了算法的时间复杂度.在进行算法处理之前,将问题转换成二分图,并提出相应的降阶规则,将原问题的规模进行了缩小,在此基础上运用加权分治技术来分析其算法的复杂度.研究表明运用加权分治技术能够得到较传统算法更精确的时间复杂度.
-
关键词
加权集合覆盖问题
加权分治技术
分支降阶技术
时间复杂度
-
Keywords
weighted set covering problem
measure and conquer approach
branch and reduce
time complexity
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名Perfect Code问题的加权分治算法
被引量:2
- 2
-
-
作者
王英磊
宁爱兵
支志兵
杨晓芳
-
机构
上海理工大学管理学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第3期594-596,共3页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科建设项目(XTKX2012)资助
-
文摘
加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂度更好的精确算法.Perfect Code问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂度为O(1.3248np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂度低于采用传统方法得到的时间复杂度.
-
关键词
加权分治技术
PERFECT
Code问题
分支降阶技术
算法复杂性
-
Keywords
measure and conquer
perfect code problem
branch and reduce technology
algorithm complexity
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名最小顶点覆盖问题的加权分治算法
被引量:3
- 3
-
-
作者
陈吉珍
宁爱兵
支志兵
王永斐
张惠珍
-
机构
上海理工大学管理学院
-
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2015年第5期151-155,共5页
-
基金
国家自然科学基金(71401106)
上海市一流学科建设项目资助(S1201YLXK)
高等学校博士学科点专项科研基金联合资助课题(20123120120005)
-
文摘
最小顶点覆盖问题是组合优化中经典NP—Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255n),优于常规分析下的时间复杂度O(1.325n)。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。
-
关键词
图论
算法复杂性
加权分治技术
分支降阶技术
最小顶点覆盖
-
Keywords
graph theory
algorithm complexity
Measure and Conquer
Bbranch and Reduce
Minimum Vertex covey
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名删除顶点生成二分图问题的精确算法
- 4
-
-
作者
支志兵
宁爱兵
熊小华
王永斐
陈吉珍
杨晓芳
-
机构
上海理工大学管理学院
上海第二工业大学计算机与信息学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第9期2122-2125,共4页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科建设项目(XTKX2012)资助
-
文摘
分支降阶是目前广泛用于设计精确算法求解NP-Hard问题的技术之一,该技术主要通过快速降阶、分支及递归求解原问题及其子问题.为了降低分支降阶算法的时间复杂度,一方面可以增加降阶规则、改变算法的设计思想;另一方面可以运用更精确的时间复杂度分析方法分析算法.本文针对删除最少顶点生成二分图问题,首先运用常规枚举方法得到一个时间复杂度为O(3n)的算法;然后通过增加降阶规则、改善算法设计和运用加权分治技术分析算法等方法,最终得到一个时间复杂度为O(1.8157n)的精确算法.本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的.
-
关键词
删除顶点生成二分图
精确算法
分支降阶技术
加权分治技术
-
Keywords
odd cycle transversals
exact algorithm
branch and reduce
measure and conquer approach
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名加权最小顶点覆盖的加权分治算法
- 5
-
-
作者
王永斐
宁爱兵
陈吉珍
胡琳琳
杨晓芳
-
机构
上海理工大学管理学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2015年第5期1082-1084,共3页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科建设项目(XTKX2012)资助
-
文摘
加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂性为O(1.3482np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂性低于采用传统方法得到的时间复杂性.
-
关键词
加权分治技术
加权最小顶点覆盖问题
分支降阶技术
算法复杂性
-
Keywords
measure and conquer
minimum Weighted Vertex cover problem
branch and reduce technology
algorithm complexity
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-