Page 54 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes its successors. In this method if a better node is located this path can be propagated down to the
successors. This method of using an OR graph needs 2 lists of nodes
OPEN is a precedence queue of nodes that have been evaluated by the heuristic function but
which have not yet been extended into successors. The most capable nodes are at the front.
CLOSED are nodes that have already been produced and these nodes must be amassed since a
graph is being used in partiality to a tree.
Heuristics so as to discover the most promising nodes a heuristic function is required known as
f’ where f’ is an rough calculation to find is made up of two parts g and h’ where g is the cost of
going from the first state to the current node; g is considered merely in this context to be the
number of arcs navigated each of which is considered as being of unit weight. h’ is an estimate
of the initial cost of obtaining from the current node to the goal state. The function f’ is the
estimated value or estimate of obtaining from the initial state to the objective state. Both g and
h’ are positive valued variables. Best First The Best First algorithm is an easy form of the
A* algorithm. From A* we note down that f’ = g+h’ where g is assess of the time taken to go from
the initial node to the current node and h’ is an estimate of the time taken to solution from the
current node. Therefore f’ is an estimate of how long it takes to go from the original node to the
solution.

Did u know? As a support we take the time to go from one node to the subsequent one to
be a constant at 1.

Example: Here is an example for best-first search in the figure given below. Visualize
trying to arrive at a state that is shown below the spiral tube. If the initial state begins inside of
the opening at the top of the tube, the search will move in the region of the spiral rather than
leaving the tube and looking directly for the goal.

x S

x G

48 LOVELY PROFESSIONAL UNIVERSITY