A method of estimating computational complexity based on input conditions for N-vehicle problem
2010
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:
- Polynomial-time reduction
- Mathematical optimization
- Computational problem
- Simon's problem
- Complete
- Dynamic problem
- Mathematical analysis
- Parameterized complexity
- Function problem
- Asymptotic computational complexity
- Mathematics
- Algorithm
- Average-case complexity
- Time complexity
- P versus NP problem
- Computational complexity theory
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
6
References
7
Citations
NaN
KQI