title: Some questions with pacman path finding
body: <p>I have learned about A*, BFS, DFS and can implement them pretty well. However, some problems arise when I try to do that in solving pacman path finding problem. Let's assuming there're only two types of mazes: one has full items, as in no blank square, everything is either pacman or item-to-collect or wall; and one only has a few items (4 or less).</p>
  
  <ol>
  <li><p>How exactly are BFS and DFS implemented if there're more than one item to collect? In such case, do they still produce optimal result?</p></li>
  <li><p>What's the best algorithm/heuristic for the full-item map? What I've come up with so far is something like greedy heuristic, but it's pretty random due to the map having too many items to collect and hence, not a good idea to solve such maze.</p></li>
  <li><p>Using A*, in the few-item map, is there any good way to determine which item should be taken first? I thought of trying using Mahattan distance as a rough estimate, but that doesn't sound right especially in some tricky situations.</p></li>
  </ol>