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

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