3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so what is the question? $\endgroup$ – seteropere Apr 5 '13 at 23:38
  • $\begingroup$ Could you refer some online articles or tutorials that compare variations of A*? This is my question :) $\endgroup$ – Martin H. L. Apr 6 '13 at 0:03
  • $\begingroup$ What do you mean by variations of A*? Are you talking about different heuristics, data structure or something else? $\endgroup$ – Pål GD Apr 6 '13 at 16:52
  • $\begingroup$ 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. $\endgroup$ – Martin H. L. Apr 6 '13 at 22:16
  • $\begingroup$ @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.) $\endgroup$ – Pål GD Apr 7 '13 at 22:08
3
$\begingroup$

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,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.