%0 Journal Article
%A YAO Xiong-wu
%A ZHENG Jin-hua
%A PAN Wen-jun
%T Using evolutionary algorithm and function optimization model to analyze backtracking algorithm’s upper bound
%D 2010
%R 10.3778/j.issn.1002-8331.2010.09.009
%J Computer Engineering and Applications
%P 26-30
%V 46
%N 9
%X 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.
%U http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2010.09.009