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.
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.
.PNG)
No comments:
Post a Comment