欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.setpacking问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的setpacking问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O^＊（1.1686^n＋N）的精确算法,当N≤n/4时,比现有最佳的算法O^＊（1.2209^n）更加有效.
英文摘要：
The measure and conquer approach is a new technique for algorithm analysis. The approach is based on the choice of the measure of the subproblems recursively generated by the algorithm considered, so as to obtain the best running time in worst case. Set packing problem is a typical NP-hard problem, which is widely applied in the fields of scheduling,code optimization and bioinfomatics. In this paper, an iterative algorithm based on branching search is designed. The symbol set N is also considered in the algorithm. Then, the measure and conquer approach is used to analyze the algorithm, and prove that the running time of our algorithm is O^＊（1.1686^n＋N）, which is more efficient than the previous best algorithm O^＊（1.2209^n） when N≤n/4.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：