# 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? Apr 5 '13 at 23:38
• Could you refer some online articles or tutorials that compare variations of A*? This is my question :) 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? 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. 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.) 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

Let me know, please, whether this helps or not,

• I believe you're an expert on this field, could you help me understand why non-recursive IDA* is correct when it's implemented by DFS?
– Ning
Dec 30 '20 at 21:48
• Do you mean DFS = depth-first search? I'm not sure I properly understood your question as the usual choice for implementing Depth-First search is to use a stack and recursive implementations provide one automatically. Thus, if you want to make a non-recursive implementation of Depth-First search all you need is to keep control of your own stack. IDA*, on the other hand, is a depth-first search variant so .. Sorry if I did not understood this question ... Jan 1 at 14:11
• Yes, I meant depth-first search, sorry for unclearness. Yes I know IDA* is a depth-first search variant, but my problem is that I want to prove the correctness of IDA*, and I have tried deduction from A*, but since A* is an extension of Dijkstra shortest path first algorithm, which is a BFS idea, I stuck.
– Ning
Jan 1 at 14:37
• Sorry for my bad English, which is not my mother tongue. But I think my problem is well stated and if you have time please take a look: cs.stackexchange.com/q/133840/65033, this problem is important for me and I'm willing to provide bounty for this question.
– Ning
Jan 1 at 14:41