Admissible heuristic

An Admissible Heuristic in the context of search algorithms, particularly in artificial intelligence, refers to a heuristic function that never overestimates the cost to reach the goal from any node in the search space. It ensures the optimality of the search result when used with algorithms like A* (A-star), guaranteeing that the shortest path to the goal is found.

Admissible heuristic

Areas of application

  • Pathfinding: In applications like GPS navigation and robotics, to find the most efficient route between two points.
  • Puzzle Solving: In solving puzzles like the 8-puzzle or Rubik’s Cube, to find the minimum number of moves to reach the solved state.
  • Game AI: For strategy games where the AI must decide the most efficient moves to reach a winning position.
  • Planning Systems: In logistics and supply chain management, to optimize routes and schedules.

Example

In a pathfinding problem, such as navigating a map from point A to point B, an admissible heuristic might be the straight-line distance (Euclidean distance) between the current position and the goal. This distance never overestimates the actual driving distance, ensuring the heuristic is admissible.