Skip to main content

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
Labels:

Comments

Post a Comment

Popular posts from this blog

Rinku privacy policy

Privacy Policy krg built the Rinku app as a Free app. This SERVICE is provided by krg at no cost and is intended for use as is. This page is used to inform visitors regarding my policies with the collection, use, and disclosure of Personal Information if anyone decided to use my Service. If you choose to use my Service, then you agree to the collection and use of information in relation to this policy. The Personal Information that I collect is used for providing and improving the Service. I will not use or share your information with anyone except as described in this Privacy Policy. The terms used in this Privacy Policy have the same meanings as in our Terms and Conditions, which are accessible at Rinku unless otherwise defined in this Privacy Policy. Information Collection and Use For a better experience, while using our Service, I may require you to provide us with certain personally identifiable information. The information that I request will be retained on your device and is not...
Post a Comment
Read more

MISSIONARY CANNIBAL PROBLEM SOLUTION IN AI | BLOG |

DATE :- 09/02/2020 Both problems we have seen in the previous module were comparatively simple as there was the little prerequisite for applying rules. To emphasize that important part, let us take two more problems which rely heavily on the prerequisites for applying a rule. A missionary cannibal problem Let us take our next example to reiterate our understanding of state space, the start state, the end state, the rules and using those rules to solve the problem, especially the preconditions under which a rule is to be applied.  The problem is called a missionary and cannibal problem. Three missionaries and three cannibals found themselves on one side of a river. All of them have to move to the other side. The only boat available for communication can carry maximum two of them at a time. Minimum one of the travelers must come back to get the boat on the side where others are waiting. Another condition is, at no point in time, the missionaries should be less than the nu...
Post a Comment
Read more

first blog

date : 08/02/2020 I created my first blog today. I completed 1st module of artificial intelligence and started module 2. In module 1 introduction to AI is given. AI has many definitions associated with it. The AI  is a way of solving difficult problems. Difficult problems which are done by humans, like brushing teeth, brushing is very complicated process to be done by robot. If power is low or high it can not do work . It is the first time I think how chess game in android works. there are infinite numbers of moves to play. But with help of AI it is actually working . Old chess games at high difficulty level were taking so much time to play one move but now it takes only few seconds.           Humans are able to guess and work. but a program can not do that easily. Programs works  stepwise.    
1 comment
Read more