# New Technology

Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

## Sunday, 8 July 2018

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
- Optimal solution is found

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

A* expands nodes in increasing f  value
- 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

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.