algorithm: A* search and IDA* search

The post discusses some search methods.

problem

  • Given: a graph, a source node, and a destination node
  • Objective: find a minimum cost path from source to destination.
  • greedy search

    • bfs style
    • cost function = h(x): estimated cost of path to destination

    A search

    • bfs style
    • cost function = f(x) = h(x) + g(x). g(x): cost of path from source

    A* search

    • bfs style
    • cost function = f(x) = h(x) + g(x)
    • h(x) is admissive, i.e., h(x) <= h*(x). It never overestimates the cost to the destination.
    • the solution is optimal

    IDDFS: iterative deepening dfs

    • dfs style
    • cost function = g(x): length of the path from source
    • the search has many iterations of dfs
    • in each iteration, the dfs stops while path length is above threshold
    • the stop threshold is increased by one in each iteration

    IDA*: iterative deepening dfs

    • dfs style
    • cost function = f(x) = h(x) + g(x)
    • h(x) is admissive, i.e., h(x) <= h*(x). It never overestimates the cost to the destination.
    • the stop threshold is increased by one in each iteration
    • the search has many iterations of dfs
    • in each iteration, the dfs stops while path length is above threshold
    • the stop threshold’s default value is h(source)
    • if destination is not found in last iteration, the stop threshold is updated as the minimum f(x) above threshold in last iteration
    • the solution is optimal

    conclusion
    IDA* search improves the space usage of A* search. This could improve performance since all operations are executed in stack directly which is already created by kernel(main thread) or pthread library(other threads). However, since stack size is fixed, if the problem size is large, than A* search might be the better option.

    Advertisements

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s


    %d bloggers like this: