title: A-star: heuristic for multiple goals
body: <p>Let's consider a simple grid, where any point is connected with at most 4 other points (North-East-West-South neighborhood).</p>
  
  <p>I have to write program, that computes minimal route from selected initial point to <strong>any</strong> of goal points, which are connected (there is route consisting of goal points between any two goals). Of course there can be obstacles on grid.  </p>
  
  <p>My solution is quite simple: I'm using A* algorithm with variable heuristic function h(x) - manhattan distance from x to nearest goal point. To find nearest goal point I have to do linear search (in O(n), where n - number of goal points). Here is my question: is there any more efficient solution (heuristic function) to dynamically find nearest goal point (where time &lt; O(n))?</p>
  
  <p>Or maybe A* is not good way to solve that problem?</p>