Thread: A good description of IDA* search

  1. #1
    Registered User
    Join Date
    Jan 2013

    A good description of IDA* search

    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.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Long Beach, CA
    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
        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.
    Last edited by anduril462; 02-02-2014 at 10:04 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scene Description Language in C
    By shameerkm in forum C Programming
    Replies: 1
    Last Post: 01-12-2010, 01:16 AM
  2. Good File Search Program?
    By SMurf in forum Tech Board
    Replies: 3
    Last Post: 07-16-2007, 11:28 AM
  3. Can anyone give me a good description of an array?
    By Sephiroth in forum C Programming
    Replies: 5
    Last Post: 09-22-2005, 04:33 AM
  4. Error Description
    By mcorn in forum C++ Programming
    Replies: 5
    Last Post: 12-14-2002, 10:29 PM
  5. prescription: description...
    By doubleanti in forum A Brief History of
    Replies: 55
    Last Post: 10-14-2001, 08:35 AM