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

Idle Solar Defence Policy

  Privacy Policy This privacy policy applies to the Idle Solar Defence app (hereby referred to as "Application") for mobile devices that was created by krg (hereby referred to as "Service Provider") as a Free service. This service is intended for use "AS IS". Information Collection and Use The Application collects information when you download and use it. This information may include information such as Your device's Internet Protocol address (e.g. IP address) The pages of the Application that you visit, the time and date of your visit, the time spent on those pages The time spent on the Application The operating system you use on your mobile device The Application does not gather precise information about the location of your mobile device. The Service Provider may use the information you provided to contact you from time to time to provide you with important information, required notices and marketing promotions. For a better experience, while using ...
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