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.