Heuristic Functions in Artificial Intelligence

Data Science, AI and ML
#1

Heuristic Functions in AI: As we have already seen that an informed search make use of heuristic functions in order to reach the goal node in a more prominent way. Therefore, there are several pathways in a search tree to reach the goal node from the current node. The selection of a good heuristic function matters certainly. A good heuristic function is determined by its efficiency. More is the information about the problem, more is the processing time.
Consider the following 8-puzzle problem where we have a start state and a goal state. Our task is to slide the tiles of the current/start state and place it in an order followed in the goal state. There can be four moves either left, right, up, or down. There can be several ways to convert the current/start state to the goal state, but, we can use a heuristic function h(n) to solve the problem more efficiently.

Properties of a Heuristic search Algorithm

Use of heuristic function in a heuristic search algorithm leads to following properties of a heuristic search algorithm:

  • Admissible Condition: An algorithm is said to be admissible, if it returns an optimal solution.
  • Completeness: An algorithm is said to be complete, if it terminates with a solution (if the solution exists).
  • Dominance Property: If there are two admissible heuristic algorithms A1 and A2 having h1 and h2 heuristic functions, then A1 is said to dominate A2 if h1 is better than h2 for all the values of node n.
  • Optimality Property: If an algorithm is complete, admissible, and dominating other algorithms, it will be the best one and will definitely give an optimal solution