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

Question

I have some troubles 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 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" comes from? As I see, IDDFS is not iterative at all, it's still recursiive, 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* on 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!

---

EDIT: Here some nice articles, but they are too theoretical. No examples, no any specific things. But still very useful. I'd recommend them (=

Barbra

what sort of problem are you trying to approach? the questions you asked took my university AI class about 5 weeks to cover, so it's a bit much to answer. – Janayjanaya

This question is kinda related to THIS one, but just a little. I need to understand deeply these algorithms first. Any lectures or articles would be helpful. Thanks (: – Barbra

This would be better asked as more than one question. I explained IDDFS below, and you really need to understand that before trying IDA*. How are you on A*? You should be comfortable with both A* and IDDFS before trying to learn IDA*. – Pinard

@David - I perfectly understand A*. Or, at least, I think so. – Barbra

You need to get yourself a book, sit down, read. Russel & Norvig "AI - A Modern Approach" might be appropriate. – Curdle

AI Stack Exchange is still in beta, so we can't move questions there. It's fine if you want to leave it here and repeat it on AI. If you do, please provide links between the two questions so people can see the answers you get from both communities. – Brigadier

Answer 1

Let's start with iterative deepening depth-first search.

The idea is that depth-first search is efficient, but won't necessarily hit the right answer any time soon. So, do 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, or decide to give up. 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 to implement 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.

Learn iterative deepening DFS first, then apply that to IDA*. I read an early Korf paper on these searches over fifteen years ago, and don't remember how IDA* works very well, but your main problem is that you don't understand iterative deepening in the first place.

Pinard

Yep, you're right, I can't understand how IDDFS is different from BFS, as the idea looks just the same :? – Barbra

@Kiril: You hit the same nodes as BFS. You don't have to keep a queue and check nodes for uniqueness. The idea is to combine the space and much of the performance advantage of DFS with the guaranteed shortest-path finding of BFS. – Pinard

it is not the same. the space tradeoff is key. the wiki page explains the benefit pretty well: en.wikipedia.org/wiki/Iterative_deepening_depth-first_search – Janayjanaya