# Comparing variations of A*

I am running some experiments with a maze, and trying different variations of A*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better than IDA).

I am looking for online articles that have done similar experiments, comparing variations of A* with respect to expanded nodes, but have not come across anything concrete.

• so what is the question? – seteropere Apr 5 '13 at 23:38
• Could you refer some online articles or tutorials that compare variations of A*? This is my question :) – Martin H. L. Apr 6 '13 at 0:03
• What do you mean by variations of A*? Are you talking about different heuristics, data structure or something else? – Pål GD Apr 6 '13 at 16:52
• one variation is Iterative Deepening A* (IDA). Another is graph search A*. All are variations of the algorithm A*. All applied to the same problem, to be able to compare. – Martin H. L. Apr 6 '13 at 22:16
• @MartinH.L. In that case you don't want to compare A* and IDA* since A* always beats IDA* (when paths are at least two steps). IDA* is only sensible over A* if you care about memory. (Ps Computer Science Meta: If you use the @-symbol and name when you reply to a comment, the one with that name is informed about your reply.) – Pål GD Apr 7 '13 at 22:08

Well, there is a lot of bibliography on whether one algorithm is better than the other. In particular, the main insight is: "in the presence of duplicates (e.g. grids), A$^*$ should be preferred, whereas in other cases IDA$^*$ should be in general preferred". For example, heuristic planners usually prefer best-first search strategies such as A$^*$ instead of IDA$^*$ (just because duplicates occur in many domains). For example, to solve the $N$-Puzzle, the $N$-Pancake, or the TopSpin, IDA$^*$ is the current algorithm of choice. For other cases, such as Rubik's Cube or Towers of Hanoi, IDA$^*$ is still the algorithm of choice but be careful and try to implement a good strategy for handling symmetries. In the case of grids, A$^*$ is the right choice.
There is a wonderful paper about how to implement A$^*$ and makes a lot of considerations that, I think, fit your question: Ethan Andrew Burns, Matthew Hatem, Michael J. Leighton, Wheeler Ruml. Implementing Fast Heuristic Search Code