Fringe Search vs A* algorithm in AI

Question

I've been searching on the internet about Fringe search in terms of space and time complexity, but with no success. Can any-one tell me the same and a few points why should we prefer to use fringe search over A* algorithm in artificial intelligence.

Answer 1

I hadn't explored the fringe search algorithm until seeing this post, so take this with a grain of salt. According to Wikipedia, Fringe Search is based off IDA*, which in turn is based off A*.

pros/cons of IDA* over A*:

• IDA* was designed to decrease memory use at the cost of some performance.
• IDA* will check tiles more than once, whereas A* will not
• A* keeps track of all tiles instead of just a small subset, like IDA*

So you would choose IDA* over A* if you're more worried about memory consumption than raw speed in returning a path.

Fringe Search vs IDA*/A*:

• Fringe Search is designed to fix some of the worst problems with IDA*, putting it halfway between the two algorithms in terms of performance vs memory usage.
• Should perform faster than IDA*, but perform slower than A*
• More memory usage than IDA*, but less than A*

So, it would seem Fringe Search would be a good choice if you're working with limited memory, but still want more performance than IDA* would provide. In general I would recommend just using A* to start, and if you find you're having any specific issues, finding a substitute algorithm down the road.