计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (9): 26-30.DOI: 10.3778/j.issn.1002-8331.2010.09.009

• 研究、探讨 • 上一篇    下一篇

用进化算法和函数优化模型分析回溯算法上界

姚雄武,郑金华,潘文俊   

  1. 湘潭大学 信息工程学院,湖南 湘潭 411105
  • 收稿日期:2009-03-19 修回日期:2009-05-22 出版日期:2010-03-21 发布日期:2010-03-21
  • 通讯作者: 姚雄武

Using evolutionary algorithm and function optimization model to analyze backtracking algorithm’s upper bound

YAO Xiong-wu,ZHENG Jin-hua,PAN Wen-jun   

  1. School of Information Engineering,Xiangtan University,Xiangtan,Hunan 411105,China
  • Received:2009-03-19 Revised:2009-05-22 Online:2010-03-21 Published:2010-03-21
  • Contact: YAO Xiong-wu

摘要: 研究的是常出现在求解NP难问题的Davis-Putnam型指数时间回溯算法中的一类多变量递归问题。首先引入适当的赋权函数,把多变量递归函数转化为单变量递归函数;然后提出有效的优化模型,把求解单变量递归函数问题转化为一般的带约束条件的函数优化问题。传统的算法计算精度较差,并且求得的结果多为局部最优解。所以,引进新颖的遗传算法求解优化模型以改进求解精度和速度,并应用此算法求解了set packing问题,计算结果具有很高的精度。

关键词: 回溯算法, 约束优化, 全局最优

Abstract: The problem of a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems is researched.First a technique for proving asymptotic upper bounds on these recurrences is described,by applying a suitable weight function to reduce the problem to that of solving univariate linear recurrences.Then an efficient optimization model converting the univariate linear recurrences to general constrained optimization problems is proposed.The accounting result of traditional algorithm is worse.The result also is the local minimum.So,a novel genetic algorithm to solve the optimization model yielding the smallest upper bound,and solve the set-packing problem is presented.The result of accounting is very good.

Key words: backtracking algorithm, constrained optimization, global optimization

中图分类号: