A Method of Estimating Computational Complexity Based on Input Conditions for N-vehicle Problem  

作　　者：Xi Xia Jin-chuan Cui 

机构地区：[1]Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

出　　处：《Acta Mathematicae Applicatae Sinica》2010年第1期1-12,共12页应用数学学报（英文版）

基　　金：supported by the State 973 Program(2006CB701306) and Key Laboratory of Management,Decision and Information Systems,CAS

摘　　要：This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.

关 键 词：Complexity of computation combinatorial optimization N-vehicle problem PERMUTATIONS inverse order 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构] U270.7[自动化与计算机技术—计算机科学与技术]