How can the A* algorithm be optimized?
Any references that shows the optimization of A* algorithm are also appreciated.
$\begingroup$$\endgroup$
4
- $\begingroup$What do you mean by "optimization of A star algorithm"? Do you mean optimized implementations?$\endgroup$– nbroCommentedApr 16, 2019 at 13:19
- $\begingroup$@nbro how can we optimize A* algorithm? what does this mean?$\endgroup$– LexiCommentedApr 16, 2019 at 13:27
- $\begingroup$Are you asking the meaning of the sentence "how can we optimize A* algorithm?"? It likely means how you can change the standard A* algorithm to make it more efficient (either in terms of time or space complexity or in terms of practical time required to find the solution).$\endgroup$– nbroCommentedApr 16, 2019 at 14:12
- $\begingroup$@nbro yes.. can you answer that?$\endgroup$– LexiCommentedApr 16, 2019 at 14:23
Add a comment |
2 Answers
$\begingroup$$\endgroup$
1Check 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
- 2$\begingroup$Hey, welcome to the site. Posts just linking to reference material are better suited as comments.$\endgroup$CommentedApr 16, 2019 at 16:08
$\begingroup$$\endgroup$
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.
