My Blog.

A* Algorithm

A* Algorithm

Definition

A* (A-star) is a heuristic search algorithm used in artificial intelligence for finding the shortest path from a start node to a goal node. It combines the features of uniform-cost search and pure heuristic search to efficiently traverse the search space.

Key Concepts

  • Evaluation Function (f(n)): A function used to determine the order of node expansion, defined as ( f(n) = g(n) + h(n) ).
    • ( g(n) ): The cost of the path from the start node to node ( n ).
    • ( h(n) ): The heuristic estimate of the cost from node ( n ) to the goal.
  • Heuristic Function (h(n)): An admissible heuristic function that never overestimates the cost to reach the goal.
  • Open List: A priority queue of nodes to be evaluated, sorted by their ( f(n) ) values.
  • Closed List: A set of nodes that have already been evaluated.
  • Admissibility: A heuristic is admissible if it never overestimates the true cost to reach the goal.
  • Consistency (Monotonicity): A heuristic is consistent if ( h(n) \leq c(n, n') + h(n') ) for every node ( n ) and its successor ( n' ), where ( c(n, n') ) is the cost of reaching ( n' ) from ( n ).

Detailed Explanation

  • Procedure:
    1. Initialize the open list with the start node and the closed list as empty.
    2. While the open list is not empty:
      • Remove the node ( n ) with the lowest ( f(n) ) from the open list.
      • If ( n ) is the goal node, return the path from the start node to ( n ).
      • Generate all successors of ( n ) and calculate their ( f ) values.
      • For each successor:
        • If the successor is not in the open list or the closed list, add it to the open list.
        • If it is already in the open list but has a higher ( f ) value, update its ( f ) value and parent pointer.
      • Move ( n ) to the closed list.
  • Optimality: A* is guaranteed to find the shortest path to the goal if the heuristic function ( h(n) ) is admissible and consistent.
  • Efficiency: The performance of A* heavily depends on the quality of the heuristic function. A good heuristic can significantly reduce the number of nodes evaluated.

Diagrams

  • A Search Algorithm Process*: A* Search Algorithm Process
  • Evaluation Function f(n): Evaluation Function f(n)

Links to Resources

Notes and Annotations

  • Summary of key points:

    • A* uses the evaluation function ( f(n) = g(n) + h(n) ) to balance the cost from the start and the estimated cost to the goal.
    • The algorithm is both complete and optimal if ( h(n) ) is admissible and consistent.
    • The open list and closed list help manage explored and unexplored nodes efficiently.

  • Personal annotations and insights:

    • A* is widely used in pathfinding and graph traversal applications, such as in video games and robotics.
    • The choice of heuristic ( h(n) ) significantly affects the performance; domain-specific heuristics can greatly enhance efficiency.
    • Understanding A* provides a solid foundation for studying more advanced search algorithms and optimization techniques.

Backlinks