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.
Comments
Post a Comment