## Search

**A* algorithm** is a best-first search algorithm in which the cost associated with a node is-
f(n) = g(n) + h(n)
where g(n) is the cost of the path from the initial state to node n and h(n) is the heuristic estimate or the cost or a path from node n to a goal.

Thus, f(n) estimates the lowest total cost of any solution path going through node n. At each point a node with lowest f value is chosen for expansion.

Ties among nodes of equal f value should be broken in favor of nodes with lower h values.The algorithm terminates when a goal is chosen for expansion.

A* (A star) is the most widely known in AI
- It evaluates nodes by combining g(n) and h(n)
- f(n) = g(n) + h(n)
- Where
g(n) = cost so far to reach n
h(n) = estimated cost to goal from n
f(n) = estimated total cost of path through n

When h(n) = actual cost to goal
- Only nodes in the correct path are expanded
- Optimal solution is found

When h(n) < actual cost to goal
- Additional nodes are expanded
- Optimal solution is found

When h(n) > actual cost to goal
- Optimal solution can be overlooked

A* expands nodes in increasing f value
- Gradually adds f-contours of nodes (like breadth-first search adding layers)
- Contour i has all nodes f = fi where fi<fi+1
**Complete **
- Yes, unless there infinitely many nodes with f<= f(G)
**Time**
- Exponential in [relative error of h x length of solution]
- The better the heuristic, the better the time
* Best case h is perfect, O(d)
* Worst case h = 0, O(bd) same as BFS
**Space**
- Keeps all nodes in memory and save in case of repetition
- This is O(bd) or worse
- A* usually runs out of space before it runs out of time
**Optimal**
- Yes, cannot expand f i+1 unless fi is finished

**Robot Navigation**

f(N) = g(N) + h(N), with h(N) = Manhattan distance to goal

**Complexity Of Finding Optimal Solutions**

***** The time complexity of a heuristic search algorithm depends on the accuracy of the heuristic function.

***** For example, if the heuristic evaluation function is an exact estimator, then A* search algorithm runs in linear time, expanding only those nodes on an optimal solution path.

***** Conversely, with a heuristic that returns zero everywhere, A* algorithm becomes uniform-cost search, which has exponential complexity.

## No comments:

## Post a comment