Advances in State Space Trees for Computational Efficiency

Abstract State space tree is a foundational concept for optimizing the algorithms in order to to solve combinatorial problems. It is also applied in Artificial Intelligence, Data Science as well in operations research. This paper presents comprehensive knowledge of the State Space Tree with construction, traversal strategies and practical use of it. The important algorithms such as backtracking, branch n bounding etc have been analyzed in context of the framework of state space tree for the purpose of proving efficiency in large solution spaces. To illustrate, the State Space Tree is applied for classical problems such as N-Queens puzzle, Traveling Salesman Problem and Sudoku solving. The proposed work introduces the optimization techniques where unnecessary branches or solutions are pruned to lowest the computational overhead with ensuring correctness and completeness of desired results. The experimental results show the effectiveness of state space trees for solving the problem of complex as well high-dimensional search spaces. This research shows not only the versatility of state space tree but also provides the roadmap in solving computational challenges relating to data science, machine learning and artificial intelligence