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.

### Like this:

Like Loading...

This entry was posted on August 8, 2017 at 7:27 pm and is filed under algorithm. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply