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

Recent Post

Search

Sunday, 8 July 2018

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