**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