Skip to main content

Heuristic search methods explained!!! | blog |

Domain Knowledge 

Knowledge about the problem domain which helps the designer to decide
the heuristic function and their values. For example looking at the chess
board position, a good heuristic function can state if this position is good or
bad and how much.

Heuristic function

 a function which takes the game position as an input and tells how good or
bad it for the player. Usually a quantified value between -10 and 10 are
returned. 10 indicates a win for the player, -10 indicates the defeat and any
other value describes the goodness of the position with respect to the
value returned. The value returned by hashing function indicates the merit
of that state.

Hill Climbing

 a heuristic search method which takes any next move which is better than the current based on the heuristic function’s value

Local Maxima

 when a heuristic search function returns lower values for all neighbours
and the current node is not a goal node, the situation is known as local
maxima.

Dead end

 when there are no successors of a given node, the situation is termed as a dead end.

Steepest Ascent Hill Climbing

 a variant of Hill Climbing where the best successor from all children is chosen.

Best First Search 

the search where the best node is chosen irrespective of parent node’s
values and also freed from the constraint to choose only from children of
the current node. In this case, the best of all unexplored nodes is chosen.

Explored nodes

 Nodes of the tree where the children are generated and heuristic values are applied to them

Unexplored nodes 

Nodes whose children are not generated

A* algorithm

 the search algorithm works on OR graphs and apply best first search on them

Branching factor 

average number of children a parent has in a tree

Solution space

 a state space where each state is a potential solution to the problem.
When the search reaches to a solution, it does not need to find anything
else, for example, the path to a solution.


The constructive method

 the state space search where the node describes the
problem state which may be an initial, final or intermediate node. For
example missionary and cannibal problem, a node may be 3300 or 2211 or
0033, the first is the initial node, secondly is intermediary and last is a final
node.

Perturbation method 

the state space where each node represents the complete solution of the
problem. Thus every node is a final state. For example, we might have a
single node containing values like (3300,....0033), or (3300, ... 2211) or
(3300..1122), i.e. a complete sequence.
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