Answers.Body: <p>Check below reference url for A* algorithms ...
  <a href="https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/" rel="nofollow noreferrer">https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/</a>
  <a href="https://en.wikipedia.org/wiki/Heap_%28data_structure%29" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Heap_%28data_structure%29</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-16T16:08:06.783Z
Answers.Text: Hey, welcome to the site. Posts just linking to reference material are better suited as comments.
Answers.UserDisplayName: Philip Raeisghasem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-16T15:24:47.187Z
Answers.LastActivityDate: 2019-04-16T15:24:47.187Z
Answers.UserDisplayName: Mohammad Aslam
Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-16T14:45:43.790Z
Answers.LastActivityDate: 2019-04-16T14:45:43.790Z
Answers.UserDisplayName: Oliver Mason
Body: <p>How can the A* algorithm be optimized?</p>
  
  <p>Any references that shows the optimization of A* algorithm are also appreciated.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-16T13:19:23.607Z
Comments.Text: What do you mean by "optimization of A star algorithm"? Do you mean optimized implementations?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-16T13:27:16.963Z
Comments.Text: @nbro how can we optimize A* algorithm? what does this mean?
Comments.UserDisplayName: Lexi
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-16T14:12:17.503Z
Comments.Text: 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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-16T14:23:00.297Z
Comments.Text: @nbro yes.. can you answer that?
Comments.UserDisplayName: Lexi
Tags: <algorithm><optimization><search><a-star>
Title: How can the A* algorithm be optimized?
UserDisplayName: Lexi
ThreadText: # How can the A* algorithm be optimized?
  
  (Asked by: username_0 on 2019-04-16)
  
  How can the A\* algorithm be optimized?
  
  Any references that shows the optimization of A\* algorithm are also appreciated.
  
  **Tags:** algorithm, optimization, search, a-star
  
  > **Comments:**
  > **username_1**: What do you mean by "optimization of A star algorithm"? Do you mean optimized implementations?  
  > **username_0**: @username_1 how can we optimize A* algorithm? what does this mean?  
  > **username_1**: 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).  
  > **username_0**: @username_1 yes.. can you answer that?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-04-16. Score: 1 | Accepted answer
  
  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>
  
  > **Comments:**
  > **username_3**: Hey, welcome to the site. Posts just linking to reference material are better suited as comments.  
  
  ---
  
  ### Answer by username_4 on 2019-04-16. Score: 1
  
  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.
  
  
  ---
  
  