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$
7
  • $\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$ 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$ 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$
4
  • $\begingroup$ 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? $\endgroup$
    – Ning
    Dec 30 '20 at 21:48
  • 1
    $\begingroup$ 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 ... $\endgroup$ Jan 1 at 14:11
  • $\begingroup$ 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. $\endgroup$
    – Ning
    Jan 1 at 14:37
  • $\begingroup$ 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. $\endgroup$
    – Ning
    Jan 1 at 14:41

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.