**Heuristic
Functions **

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.

#### A heuristic function for the 8-puzzle problem is defined below:

**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.

## 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.