Archive for August, 2017

algorithm: A* search and IDA* search

August 8, 2017

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

    %d bloggers like this: