Please enter your username below and press the send button.A password reset link will be sent to you.
If you are unable to access the email address originally associated with your Delicious account, we recommend creating a new account.
Recently Saved by qosys on March 08, 2013
First saved by mgilbir on October 09, 2007
tells A* an estimate of the minimum cost from any vertex
to the goal. It’s important to choose a good heuristic function.
The heuristic can be used to control A*’s behavior.
At one extreme, if
is 0, then only
plays a role, and A* turns into Dijkstra’s algorithm, which is guaranteed to find a shortest path.
is always lower than (or equal to) the cost of moving from to the goal, then A* is guaranteed to find a shortest path. The lower
is, the more node A* expands, making it slower.
is exactly equal to the cost of moving from to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you can’t make this happen in all cases, you can make it exact in some special cases. It’s nice to know that given perfect information, A* will behave perfectly.
is sometimes greater than the cost of moving from to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.
At the other extreme, if
is very high relative to
, then only
plays a role, and A* turns into Best-First-Search.
Technically, the A* algorithm should be called simply A if the heuristic is an underestimate of the actual cost. However, I will continue to call it A* because the implementation is the same and the game programming community does not distinguish A from A*.
So we have an interesting situation in that we can decide what we want to get out of A*. At exactly the right point, we’ll get shortest paths really quickly. If we’re too low, then we’ll continue to get shortest paths, but it’ll slow down. If we’re too high, then we give up shortest paths, but A* will run faster.
In a game, this property of A* can be very useful.