a_star in Artificial intelligence new.pdf

AI

1. The A* Search Algorithm
Siyang Chen

2. Introduction
A* (pronounced `A-star') is a search algorithm that nds the
shortest path between some nodesSandTin a graph.

3. Heuristic Functions
ISuppose we want to get to nodeT, and we are currently at
nodev. Informally, aheuristic function h(v) is a function that
`estimates' howvis away fromT.
IExample: Suppose I am driving from Durham to Raleigh. A
heuristic function would tell me approximately how much
longer I have to drive.

4. Heuristic Functions
ISuppose we want to get to nodeT, and we are currently at
nodev. Informally, aheuristic function h(v) is a function that
`estimates' howvis away fromT.
IExample: Suppose I am driving from Durham to Raleigh. A
heuristic function would tell me approximately how much
longer I have to drive.

5. Admissible Heuristics
IA heuristic function isadmissibleif it never overestimates the
distance to the goal.
IExample:h(v) = 0 is an admissible heuristic.ILess trivial example: If our nodes are points on the plane,
then the straight-line distance
h(v) =
p
(vxTx)
2
+ (vyTy)
2
is an admissible heuristic.

6. Admissible Heuristics
IA heuristic function isadmissibleif it never overestimates the
distance to the goal.
IExample:h(v) = 0 is an admissible heuristic.ILess trivial example: If our nodes are points on the plane,
then the straight-line distance
h(v) =
p
(vxTx)
2
+ (vyTy)
2
is an admissible heuristic.

7. Admissible Heuristics
IA heuristic function isadmissibleif it never overestimates the
distance to the goal.
IExample:h(v) = 0 is an admissible heuristic.ILess trivial example: If our nodes are points on the plane,
then the straight-line distance
h(v) =
p
(vxTx)
2
+ (vyTy)
2
is an admissible heuristic.

8. Consistent Heuristics
ISuppose two nodesuandvare connected by an edge. A
heuristic functionhisconsistentormonotoneif it satises
the following:
h(u)e(u;v) +h(v)
wheree(u;v) is the edge distance fromutov.
IReasoning: If I want to reachTfromu, then I can rst go
throughv, then go toTfrom there. (This is very similar to
the triangle inequality.)
IExample:h(v) = 0 is a consistent heuristic.ILess trivial example, again: If our nodes are points on the
plane,h(v) =
p
(vxTx)
2
+ (vyTy)
2
is a consistent
heuristic.
IAll consistent heuristics are admissible. (Proof left to the
reader.)

9. Consistent Heuristics
ISuppose two nodesuandvare connected by an edge. A
heuristic functionhisconsistentormonotoneif it satises
the following:
h(u)e(u;v) +h(v)
wheree(u;v) is the edge distance fromutov.
IReasoning: If I want to reachTfromu, then I can rst go
throughv, then go toTfrom there. (This is very similar to
the triangle inequality.)
IExample:h(v) = 0 is a consistent heuristic.ILess trivial example, again: If our nodes are points on the
plane,h(v) =
p
(vxTx)
2
+ (vyTy)
2
is a consistent
heuristic.
IAll consistent heuristics are admissible. (Proof left to the
reader.)

10. Consistent Heuristics
ISuppose two nodesuandvare connected by an edge. A
heuristic functionhisconsistentormonotoneif it satises
the following:
h(u)e(u;v) +h(v)
wheree(u;v) is the edge distance fromutov.
IReasoning: If I want to reachTfromu, then I can rst go
throughv, then go toTfrom there. (This is very similar to
the triangle inequality.)
IExample:h(v) = 0 is a consistent heuristic.ILess trivial example, again: If our nodes are points on the
plane,h(v) =
p
(vxTx)
2
+ (vyTy)
2
is a consistent
heuristic.
IAll consistent heuristics are admissible. (Proof left to the
reader.)

11. Consistent Heuristics
ISuppose two nodesuandvare connected by an edge. A
heuristic functionhisconsistentormonotoneif it satises
the following:
h(u)e(u;v) +h(v)
wheree(u;v) is the edge distance fromutov.
IReasoning: If I want to reachTfromu, then I can rst go
throughv, then go toTfrom there. (This is very similar to
the triangle inequality.)
IExample:h(v) = 0 is a consistent heuristic.ILess trivial example, again: If our nodes are points on the
plane,h(v) =
p
(vxTx)
2
+ (vyTy)
2
is a consistent
heuristic.
IAll consistent heuristics are admissible. (Proof left to the
reader.)

12. Consistent Heuristics
ISuppose two nodesuandvare connected by an edge. A
heuristic functionhisconsistentormonotoneif it satises
the following:
h(u)e(u;v) +h(v)
wheree(u;v) is the edge distance fromutov.
IReasoning: If I want to reachTfromu, then I can rst go
throughv, then go toTfrom there. (This is very similar to
the triangle inequality.)
IExample:h(v) = 0 is a consistent heuristic.ILess trivial example, again: If our nodes are points on the
plane,h(v) =
p
(vxTx)
2
+ (vyTy)
2
is a consistent
heuristic.
IAll consistent heuristics are admissible. (Proof left to the
reader.)

13. Description of A*
We are now ready to dene the A* algorithm. Suppose we are
given the following inputs:
IA graphG= (V;E), with nonnegative edge distancese(u;v)IA start nodeSand an end nodeTIAn admissible heuristich
Letd(v) store the best path distance fromStovthat we have
seen so far. Then we can think ofd(v) +h(v) as the estimate of
the distance fromStov, then fromvtoT. LetQbe a queue of
nodes, sorted byd(v) +h(v).

14. Pseudocode for A*
d(v)
(
1ifv6=S
0 ifv=S
Q:= the set of nodes inV, sorted byd(v) +h(v)whileQnot emptydov Q:pop()for allneighboursuofvdoifd(v) +e(v;u)d(u)thend(u) d(v) +e(v;u)end ifend forend while

15. Comparison to Dijkstra's Algorithm
Observation: A* is very similar to Dijkstra's algorithm:
d(v)
(
1ifv6=S
0 ifv=S
Q:= the set of nodes inV, sorted byd(v)whileQnot emptydov Q:pop()for allneighboursuofvdoifd(v) +e(v;u)d(u)thend(u) d(v) +e(v;u)end ifend forend while
In fact, Dijkstra's algorithm is a special case of A*, when we set
h(v) = 0 for allv.

16. Comparison to Dijkstra's Algorithm
Observation: A* is very similar to Dijkstra's algorithm:
d(v)
(
1ifv6=S
0 ifv=S
Q:= the set of nodes inV, sorted byd(v)whileQnot emptydov Q:pop()for allneighboursuofvdoifd(v) +e(v;u)d(u)thend(u) d(v) +e(v;u)end ifend forend while
In fact, Dijkstra's algorithm is a special case of A*, when we set
h(v) = 0 for allv.

17. Performance
How good is A*?
IIf we use an admissible heuristic, then A* returns the optimal
path distance. Furthermore, any other algorithm using the
same heuristic will expand at least as many nodes as A*.
IIn practice, if we have a consistent heuristic, then A* can be
muchfaster than Dijkstra's algorithm.
IExample: Consider cities (points on the plane), with roads
(edges) connecting them. Then the straight-line distance is a
consistent heuristic.
(Proofs may be found in most introductory textbooks on articial
intelligence.)

18. Performance
How good is A*?
IIf we use an admissible heuristic, then A* returns the optimal
path distance. Furthermore, any other algorithm using the
same heuristic will expand at least as many nodes as A*.
IIn practice, if we have a consistent heuristic, then A* can be
muchfaster than Dijkstra's algorithm.
IExample: Consider cities (points on the plane), with roads
(edges) connecting them. Then the straight-line distance is a
consistent heuristic.
(Proofs may be found in most introductory textbooks on articial
intelligence.)

19. Performance
How good is A*?
IIf we use an admissible heuristic, then A* returns the optimal
path distance. Furthermore, any other algorithm using the
same heuristic will expand at least as many nodes as A*.
IIn practice, if we have a consistent heuristic, then A* can be
muchfaster than Dijkstra's algorithm.
IExample: Consider cities (points on the plane), with roads
(edges) connecting them. Then the straight-line distance is a
consistent heuristic.
(Proofs may be found in most introductory textbooks on articial
intelligence.)

20. Performance
How good is A*?
IIf we use an admissible heuristic, then A* returns the optimal
path distance. Furthermore, any other algorithm using the
same heuristic will expand at least as many nodes as A*.
IIn practice, if we have a consistent heuristic, then A* can be
muchfaster than Dijkstra's algorithm.
IExample: Consider cities (points on the plane), with roads
(edges) connecting them. Then the straight-line distance is a
consistent heuristic.
(Proofs may be found in most introductory textbooks on articial
intelligence.)

21. Performance
How good is A*?
IIf we use an admissible heuristic, then A* returns the optimal
path distance. Furthermore, any other algorithm using the
same heuristic will expand at least as many nodes as A*.
IIn practice, if we have a consistent heuristic, then A* can be
muchfaster than Dijkstra's algorithm.
IExample: Consider cities (points on the plane), with roads
(edges) connecting them. Then the straight-line distance is a
consistent heuristic.
(Proofs may be found in most introductory textbooks on articial
intelligence.)