Heuristic Functions in Artificial Intelligence
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.
Some toy problems, such as 8-puzzle, 8-queen, tic-tac-toe, etc., can be solved more efficiently with the help of a heuristic function. Let’s see how:
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.
h(n)=Number of tiles out of position.
So, there is total of three tiles out of position i.e., 6,5 and 4. Do not count the empty tile present in the goal state). i.e. h(n)=3. Now, we require to minimize the value of h(n) =0.
We can construct a state-space tree to minimize the h(n) value to 0, as shown below:
It is seen from the above state space tree that the goal state is minimized from h(n)=3 to h(n)=0. However, we can create and use several heuristic functions as per the reqirement. It is also clear from the above example that a heuristic function h(n) can be defined as the information required to solve a given problem more efficiently. The information can be related to the nature of the state, cost of transforming from one state to another, goal node characterstics, etc., which is expressed as a heuristic function.
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.