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

摘要：

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

关键词：回溯算法、约束优化、全局最优

所属期刊栏目：46

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金the Natiohal Narural Science Foundation of China under Grant 60773047;湖南省教育厅重点科研项目06A074

在线出版日期：2010-05-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：26-30,37