WHAT IS HEURISTIC FUNCTION IN ARTIFICIAL INTELLIGENCE?

DATE :- 10/02/2020

When heuristics are added, we will be in a position to compare alternatives based on heuristic values and choose one path over another to make a proper decision. If the heuristic is really good, the path chosen is usually better than others and we can reach to a solution much faster.

Heuristic function

We begin with a notion of a heuristic function. This function takes the problem state as the input and

generates a value between some extremes. Usually, it is between -10 to 10. The value -10 indicates that it is impossible to reach to a solution (a goal state) from this given state while the value 10 indicates that the state is a goal state.

There are two questions commonly arise when such argument is presented. The first question is how to write such a function. We may, for the time being, assume that such a function is defined and available. The second question, if such a function is available, how to put it to use.

some examples are given to explain above question

Hill climbing

One of the simplest search strategies while using heuristic is known as hill climbing.

It works like this

1. Pick up the start state and consider it a current node.

2. If the current node is the goal state, quit.

3. Generate a new state by applying the next applicable rule, if no rules left report failure and

return.

4. Apply a heuristic function to the new node.

5. If this value is more than the parent node’s heuristic value, make the new node a current node

and go to 2.

6. If not go to 3.

This search strategy is called Hill Climbing as we are making sure the next move is on the higher side

every time. If heuristic function output is height, we are climbing, hence the name.

Best first search

The best first search, as the name suggests, picks up the best node based on heuristic value irrespective of where the node is. It has three types of nodes, first are the nodes which are yet to be explored. Second are which already explored and third, the best node(s) currently.

As the name suggests, the best first algorithm explores the best node from the list, that means explores the node with the highest heuristic value.

Let us see how the best first search principally works.

1. Pick up the start state and consider it a current node

2. If current node refers to the goal state, quit.

3. Generate all new child states by applying all applicable rules to the current state, if no rules left

report failure.

4. All child nodes which are already part of explored node list are removed.

5. Apply a heuristic function to each remaining node.

6. All nodes are inserted in an array sorted in descending order of their heuristic value. This array

may contain other unexplored nodes from the previous exploration.

7. Find out the best node (with best heuristic value may be lesser than the parent) from the array.

As it is sorted, the top entry is to be picked up.

8. If the array is empty, report failure.

9. Move the current node to list of explored nodes, make the best node as a current node and go

to 2