A method of estimating computational complexity based on input conditions for N-vehicle problem |
| |
Authors: | Xi Xia Jin-chuan Cui |
| |
Affiliation: | Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China |
| |
Abstract: | 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. |
| |
Keywords: | Complexity of computation combinatorial optimization N-vehicle problem permutations inverse order |
本文献已被 维普 SpringerLink 等数据库收录! |