Need some help for understanding search algorithms (A*, IDA*, DFS, BFS, IDDFS, etc. )

Question

I have some trouble understanding some of the algorithms for searching, used in AI (artificial intelligence).

• What is the exact difference between A* and IDA* (Iterative Deeping A Star)? Is it just the heuristic function? If so, I still just can't imagine how IDA* works.. :/

• Is IDA* the same as BFS (Breadth-First search) (when the depth of expanding is just 1 level, I mean - moving just one by one level "down", is there any difference between IDA* and BFS)

• Is IDDFS (Iterative-Deeping Depth-First Search) the same as IDA*, except the heuristic function (which is equivalent to 0 in IDDFS)

• What exactly is IDDFS - moving down just one level, then using DFS (Depth-First Search)? If so, this way lots of the states are calculated (expanded) much more than ones... Or it's like this - use DFS with particular depth, then store the "leaves" (the last expanded nodes), and iterate through them to use DFS again (which, actually, is BFS?)

• Where "iterative" come from? As I see, IDDFS is not iterative at all, it's still recursive, just mixes BFS and DFS? Or I'm wrong? Or this "iterative" has nothing to do with the opposite of recursion?

• What is "iterative" for IDA *?

Could you, please, provide some examples? I read all day about these algorithms, I know their advantages and disadvantages, the complexity, etc., but I just couldn't find any good examples (except for A*; I know BFS and DFS, the others bother me). I found some pseudo-code for IDA* in different places, but they were all completely different.

Examples would be the best way to understand algorithms..but I can't find. Even in TopCoder, I didn't find anything about IDA*.

I've read the wiki articles and I'm looking for something new (:

Thanks a lot!

Answer 1

For the simple pathfinding problems that games often deal with A* is good enough. In these problems, the search space is often in the form of an explicit graph so memory isn't an issue. If you can fit the graph in memory, it probably isn't a big deal to allocate a few values per node for performing searching. In this case, A* is likely faster because it doesn't require the iterative deepening loop. The memory savings of IDA* come at the cost of having to repeat large parts of the search several times.

A* has the priority queue while IDA* has the iterations expanding the search space repeatedly.

Iterative deepening and the associated memory savings are really only important for searching truly large search spaces, and indeed for things like board games the usual strategy is iterative deepening.

A* is optimal, so as long as you have space, why not use it?

Now come to the iterative deepening depth-first search.

The idea is that the depth-first search is efficient, but won't necessarily hit the right answer any time soon. So, perform a DFS to a depth of 1. If you haven't found the answer, do it to a depth of 2. Repeat until you find the answer. This automatically gives you the shortest path on the search tree, since you never search for a path of length N + 1 if there is one of length N.

What you need to do is to change a depth-first search so it will go N nodes deep (i.e., don't generate new nodes if you're N deep), and call it with increasing N. You don't store anything more than the value of N and whatever you'd do for DFS.

The iteration comes with iteratively increasing the depth of search. The performance can be surprisingly good, given a branching factor greater than two, as in that case, most of the cost of a depth-bounded DFS is at the lowest level reached.

If you wish to know about Uninformed Search Algorithms and types of Uniformed Search Algorithms ( Breadth-first search, depth-first search, depth limited search, iterative deepening depth-first search, uniform cost search, bidirectional search ) then visit this Artificial Intelligence Course.