05-02-2013, 12:59 PM
The A Star Algorithm
The A Star.ppt (Size: 133 KB / Downloads: 164)
Djikstra Algorithm
Greedy algorithm: from the candidate nodes select the one that has a path with minimum cost from the starting node
Djikstra Algorithm
Djikstra’s algorithm pick the edge v in Fringe(T) that has minimum distance to the starting node
g(v) is minimum
Better Solution: Make a ‘hunch”!
Use heuristics to guide the search
Heuristic: estimation or “hunch” of how to search for a solution
We define a heuristic function:
h(n) = “estimate of the cost of the cheapest path from the starting node to the goal node”
Example: Admissible Heuristics in 8-Puzzle Game
Heuristic: a tile A can be moved to any tile B
H1(n) = “number of misplaced tiles in board n”
Heuristic: a tile A can be moved to a tile B if B is adjacent to A
H2(n) = “sum of distances of misplaced tiles to goal positions in board n”
Some experimental results reported in Russell & Norvig (2002):
A* with h2 performs up to 10 times better than A* with h1
A* with h2 performs up to 36,000 times better than a classical uninformed search algorithm (iterative deepening)
A* in Games
Path finding (duh!)
We will have several presentations on the topic
We will see that sometimes even A* speed improvements are not sufficient
Additional improvements are required
A* can be used for planning moves computer-controlled player (e.g., chess)
F.E.A.R. uses A* to plan its search