Comparison of Various Heuristic Search Techniques for Finding Shortest Path
Girish P Potdar, Ravindra C. Thool · International Journal of Artificial Intelligence & Applications · 2014
Couple of decades back, there was a tremendous development in the field of algorithms, which were aimed at finding efficient solutions for widespread applications.The benefits of these algorithms were observed in their optimality and simplicity with speed.Many of the algorithms were readdressed to solve the problem of finding shortest path.Heuristic search techniques make use of problem specific knowledge to find efficient solutions.Most of these techniques determine the next best possible state leading towards the goal state by using evaluation function.This paper shows the practical performance of the following algorithms, to find the shortest path:Hill Climbing, Steepest-ascent, and Best-First and A*.While implementing these algorithms, we used the data structures which were indicated in the original papers.In this paper we present an alternative data structure multi-level link list and apply the heuristic technique to solve shortest path problem.This was tested for class of heuristic search family--A* and Best First Search approaches.The results indicate that use of this type of data structure helps in improving the performance of algorithms drastically.