patternMinor
Comparing variations of A*
Viewed 0 times
variationscomparingstackoverflow
Problem
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.
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.
Solution
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,
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,
Context
StackExchange Computer Science Q#11067, answer score: 3
Revisions (0)
No revisions yet.