Search code examples
algorithmsearchartificial-intelligencebelongs-to

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

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 (=

Solution

  • 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.