Acta Mathematicae Applicatae Sinica (English Series) is a quarterly journal established by the Chinese Mathematical Society. The journal publishes high quality research papers from all branches of applied mathematics, including partial differential equations, computational mathematics, applied probability, mathematical finance, statistics, dynamical systems, and optimization and management science.
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.
An international journal sponsored by the Chinese Mathematical Society
Publishes high quality research papers reflecting latest development and trend from all branches of applied mathematics
Accelerates fundamental mathematical new findings applied to various disciplines
Acta Mathematicae Applicatae Sinica (English Series) is a quarterly journal established by the Chinese Mathematical Society. The journal publishes high quality research papers from all branches of applied mathematics, including partial differential equations, computational mathematics, applied probability, mathematical finance, statistics, dynamical systems, and optimization and management science.
