title: Modifying A* to find a path to closest of multiple goals on a rectangular grid
body: <p>The problem: finding the path to the closest of multiple goals on a rectangular grid with obstacles. Only moving up/down/left/right is allowed (no diagonals). I did see <a href="https://stackoverflow.com/questions/18779090/how-to-design-the-heuristic-for-a-when-there-are-multiple-goals-in-the-grid-map">this question and answers</a>, <a href="https://stackoverflow.com/questions/8637827/a-star-heuristic-for-multiple-goals">and this</a>, <a href="https://stackoverflow.com/questions/9555813/need-an-idea-for-a-star-search-algorithm-with-multiple-goals">and that</a>, among others. I didn't see anyone use or suggest my particular approach. Do I have a major mistake in my approach?</p>
  
  <p>My most important constraint here is that it is very cheap for me to represent the path (or any list, for that matter) as a "stack", or a "singly-linked-list", if you want. That is, constant time access to the top element, O(n) for reversing.</p>
  
  <p>The obvious (to me) solution is to search the path from any of the goals to the starting point, using a manhattan distance heuristic. The first path from the goal to the starting point would be a shortest path to the closest goal (one of many, possibly), and I don't need to reverse the path before following it (it would be in the "correct" order, starting point on top and goal at the end).</p>
  
  <p>In pseudo-code:</p>
  
  <pre><code>A*(start, goals) :
      init_priority_queue(start, goals, p_queue)
      return path(start, p_queue)
  
  init_priority_queue(start, goals, q_queue) :
      for (g in goals) :
          h = manhattan_distance(start, g)
          insert(h, g, q_queue)
  
  path(start, p_queue) :
      h, path = extract_min(q_queue)
      if (top(path) == start) :
          return path
      else :
          expand(start, path, q_queue)
          return path(start, q_queue)
  
  expand(start, path, q_queue) :
      this = top(path)
      for (n in next(this)) :
          h = mahnattan_distance(start, n)
          new_path = push(n, path)
          insert(h, new_path, p_queue)
  </code></pre>
  
  <p>To me it seems only natural to reverse the search in this way. Is there a think-o in here?</p>
  
  <p>And another question: assuming that my priority queue is stable on elements with the same priority (if two elements have the same priority, the one inserted later will come out earlier). I have left my <code>next</code> above undefined on purpose: randomizing the order in which the possible next tiles on a rectangular grid are returned seems a very cheap way of finding an unpredictable, rather zig-zaggy path through a rectangular area free of obstacles, instead of going along two of the edges (a zig-zag path is just statistically more probable). Is that correct?</p>