HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Comparing variations of A*

Submitted by: @import:stackexchange-cs··
0
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.

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,

Context

StackExchange Computer Science Q#11067, answer score: 3

Revisions (0)

No revisions yet.