计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
9期
26-30,37
,共6页
回溯算法%约束优化%全局最优
迴溯算法%約束優化%全跼最優
회소산법%약속우화%전국최우
backtracking algorithm%constrained optimization%global optimization
研究的是常出现在求解NP难问题的Davis-Putnam型指数时间回溯算法中的一类多变量递归问题.首先引入适当的赋权函数,把多变量递归函数转化为单变量递归函数;然后提出有效的优化模型,把求解单变量递归函数问题转化为一般的带约束条件的函数优化问题.传统的算法计算精度较差,并且求得的结果多为局部最优解.所以,引进新颖的遗传算法求解优化模型以改进求解精度和速度,并应用此算法求解了set packing问题,计算结果具有很高的精度.
研究的是常齣現在求解NP難問題的Davis-Putnam型指數時間迴溯算法中的一類多變量遞歸問題.首先引入適噹的賦權函數,把多變量遞歸函數轉化為單變量遞歸函數;然後提齣有效的優化模型,把求解單變量遞歸函數問題轉化為一般的帶約束條件的函數優化問題.傳統的算法計算精度較差,併且求得的結果多為跼部最優解.所以,引進新穎的遺傳算法求解優化模型以改進求解精度和速度,併應用此算法求解瞭set packing問題,計算結果具有很高的精度.
연구적시상출현재구해NP난문제적Davis-Putnam형지수시간회소산법중적일류다변량체귀문제.수선인입괄당적부권함수,파다변량체귀함수전화위단변량체귀함수;연후제출유효적우화모형,파구해단변량체귀함수문제전화위일반적대약속조건적함수우화문제.전통적산법계산정도교차,병차구득적결과다위국부최우해.소이,인진신영적유전산법구해우화모형이개진구해정도화속도,병응용차산법구해료set packing문제,계산결과구유흔고적정도.
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.