A good description of IDA* search

[Tamim Ad Dari]

What is IDA* search ? and How do I implement it? The A* search is an iterative search . But How do i iteratively deppen in A* ? cause its already deepening by 1 layer. like bfs.

[anduril462]

The Wikipedia entry doesn't have a too much on IDA*, but it has nice pseudo code, and mentions that it is based on iterative-deepining DFS, which has good info on how iterative deepening works.

I think you are misunderstand iterative deepening. The first time you search at most one layer down. Then you restart the search from the beginning, looking at most two layers down. Then three layers, etc.

Imagine you put a depth limit on the A* algorithm. That depth limit (call it D) means you can only travel at most D nodes from the start, when looking for the solution. If you don't find it within D nodes, then you give up. IDA* performs A* starting with D == 1, if not found, increase D to 2, 3, etc. Each time it restarts the search from the beginning. Something like

A-star(start node, goal node, max depth)
    // perform A*, going no more than D nodes from start node
    return path if found, or nil

D = 1
do
    path = A-star(start node, goal node, D)
    D = D + 1
while path is not nil

Note, this iterative deepening method is analogous to how the traceroute utility works, repeatedly increasing the TTL. So reading up on that may give you some insight as well.

I hope that clears things up a bit.