Introducing A* Search Algorithm

Question

I created a group lab where one student makes a random maze generator, one student makes a corresponding maze solver, and the last student calls the methods created by both students and creates an animated maze walker. Currently, the students are told to use Prim's algorithm for maze generation, though I am open to any of these other algorithms as well:

• Kruskal's
• Recursive Backtracker
• Aldous-Broder
• Growing Tree
• Hunt-and-Kill
• Wilson's
• Eller's
• Cellular Automaton
• Recursive Division
• Sidewinder
• Binary Tree

In practice, about 10% of students use other algorithms besides Prim's.

For the maze solver, I teach my students about breadth-first search, and for next year, I would like to expand this a bit and teach them about depth-first search as well. However, I would also like to give them a real shot at A*, since it is a much, much better algorithm.

What I am looking for is how to get them to see the difficult piece of A*: how a heuristic concretely fits within the algorithm and gets us to a solution. My target is for 25% of the students to choose to use A* next year. I don't care which heuristics we use, but I would like them to see something that they can understand quite concretely (as I believe firmly in engendering concrete understandings before abstract understandings) and I would like them to understand the difference between an admissible and an inadmissible heuristic.

For context, I do this all during my AP Computer Science class, so it is in Java, however the question is really about A*, so I am not adding those tags in.

Edit

Mike Zamansky posted a response to this question on his incredible blog and it knocked my socks off! I'm going to integrate a lot of his approach into my own next year. I would accept his answer, but it's not on this site, so the best I can do from here is link to it.

Answer 1

I usually teach Uniform Cost Search (UCS) before A*, since it is basicaly A* without the heuristic (and it reduces to BFS when all costs = 1, so it is pretty straightforward to explain). Then I teach A* and show them animated examples of the explored nodes in comparison to UCS (here you can find excellent interactive examples).

In this step, one analogy I like to use is about mazes: Imagine yourself inside a maze from which you must find the exit, but you have no idea where it is. This is UCS. Now imagine there is no ceiling in the maze (like the Harry Potter one), and there is a tower in the exit which can be seen from anywhere in the maze. Now you can make more informed decisions in your search, biasing choices in that direction. This is A*.

Answer 2

You could show them the results with a given heuristics function, that has a single parameter which impacts how the heuristic function affects the cost estimate.

As an example,

estimate = D * (horizontal_distance + vertical_distance)

where the distance is the one between the current node and the goal (quite straight forward in a maze, albeit not such a good choice for the heuristic)

Here, D is a parameter that will, in essence, decide how influential the heuristic is.

You can use this example with a number of different D values and show the student how the chosen path changes (if it finds it at all) as you change D. This will show the students how the heuristic changes the decision making.

Another heuristic you could use is one that counts the number of steps, in the direction of the goal, that can be taken before the solver hits a wall of the maze (the usefulness depends on how dense the maze is).