title: A* search with multiple-goals (Python)
body: <p>I am trying to write a function that completes an A* search with multiple goals. Basically it is searching a grid like structure of the form:</p>
  
  <pre><code>%%%%%%%%%%%%%%%%%%%%
  %.           ...P .%
  %.%%.%%.%%.%%.%% %.%
  % %% %.....      %.%
  %%%%%%%%%%%%%%%%%%%%
  </code></pre>
  
  <p>for a path from P that goes through all the dots (basically Pacman).</p>
  
  <p>However I have run into a problem with my algorithm (which I attempted to adapt from my A* search for a single goal) as the path it returns does not go through all the dots. This is the path it returns for the above maze:</p>
  
  <p>Path = [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1, 13), (1, 14), (1, 15), (1, 16)]</p>
  
  <p>while a print statement shows that the visited variable has a value at return of:</p>
  
  <p>[(1, 16), (1, 15), (2, 16), (1, 17), (1, 14), (3, 16), (1, 18), (1, 13), (3, 15), (2, 18), (1, 12), (2, 13), (3, 18), (3, 14), (1, 11), (3, 13), (3, 12), (1, 10), (1, 9), (3, 11), (2, 10), (1, 8), (3, 10), (1, 7), (3, 9), (1, 6), (3, 8), (2, 7), (1, 5), (3, 7), (1, 4), (3, 6), (2, 4), (1, 3), (3, 4), (1, 2), (1, 1), (2, 1)]</p>
  
  <p>I think that that problem is how I am storing the current path (where each node stores its parent node, and then I return the end node and go backwards recursively to get the path). Does anyone have any advice for what I should change? I attached my current code below. Thanks!</p>