How can the A* algorithm be optimized?
Any references that shows the optimization of A* algorithm are also appreciated.
Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.Sign up to join this community
Check below reference url for A* algorithms ... https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/ https://en.wikipedia.org/wiki/Heap_%28data_structure%29
The first step of optimisation is to measure where inside the implementation most time is spent -- you don't actually optimise the algorithm itself, but a specific implementation of it. This step should give you an overview of where you can make improvements. Speculative changes usually don't do much.
There are several aspects of A* which would be candidates. You are keeping a list of paths currently under investigation. If it is very long, processing might take more time. You could try and prune this list (though it might mean that you won't actually find the best path anymore). Or you could investigate efficient ways of storing it.
Each step you need to compute the 'cost' of each path. This could be cached to stop you from repeating calculations. The heuristic function could be slow -- again something to investigate.
Let me stress again that you need to measure the performance first. There is no point in randomly trying to make things faster; you could waste a lot of time for very little gain. And typically with optimisation, readability of the code suffers, and it becomes harder to maintain. You might find that other parts of your system take a lot longer than the actual path finding, so your time might better be spent on those.