Ch 3 - Show concepts for A* search

[redblobgames]

The current diagram shows the mechanics of A* search (g value, h value, f value, etc.) but not some of the concepts in the book:

• Admissible/consistent heuristic. Is it useful to show an inadmissible heuristic so that we would see a non-shortest path computed? I don't know.
• Choice of heuristics. The book mentions absolute and relative error of the heuristic. The smaller the error, the better the time complexity of A*. This could be a diagram that offers the choice of several heuristics, and displays how much of the graph is searched for each choice.
• Contours. When the heuristic is admissible, the f values never decrease, and this creates contours in the graph. The current graph makes it hard to see those contours makes it hard to see but a denser graph could be used to make the contours visible. For example in a 1000-node graph, you could color the nodes with f values between 50 and 60, another color between 60 and 70, another color between 70 and 80, etc. Or maybe lines between those nodes would look better.

These might each be a separate diagram.

[Dragneel7]

@redblobgames I think the example of 8 puzzle game as shown in the book to depict the above can be useful in the visualization. The first 2 points have been properly elaborated using that example but I am not sure about the 3rd one.

[redblobgames]

For choice of heuristics, I think we would want to show a graph of all the states, the larger the better. For example the bidirectional search visualization here is large enough that you'll be able to see the difference a heuristic makes. Here's an example with A* search over a maze — light blue is using one heuristic and dark blue is using a better heuristic:

This kind of visualization can also show contours, by plotting the f value at each position and then drawing contour lines on that.

I think 8 puzzle can work but I don't know how large the graph is.

[Dragneel7]

The 8 puzzle problem graph isn't very large and the difference in heuristics is displayed by showing the no. of states visited and the branching ratio. It was used in the book for the same but I don't know if it will meet our requirements here.