Searching is a process to find
the solution for a given set of problems. This in artificial intelligence can be done by
using either uninformed searching strategies of either informed searching
Un-Informed Search Strategy
Un-Informed search strategy further includes two techniques.
Depth First Search.
In Breadth First
Search(BFS), the root node of the graph is expanded first, then all the
successor nodes are expanded and then their successor and so on i.e. the nodes
are expanded level wise starting at root level.
Searching Strategies : Breadth
In Depth First
Search(DFS), the deepest node is expanded in the current unexplored node of the
search tree. The search goes into depth until there is no more successor
Searching Strategies : Depth
Informed search strategy further includes two searching
techniques. These are:
AO* Search Technique.
technique is an informal search strategy but can be called as a form of best
It is a search
technique which the most optimistic node is expanded by expanding a
The node of the graph can be evaluated by using two functions
i.e. g(n) and
Here, g(n) = Cost/Distance to reach
node “n”. h(n) = Cost/Distance to reach from node “n” to the goal node.
any node, function f(n) is generated and used as:
f(n) = g(n) + h(n). where, f(n) = Estimated cost/distance
of solution through node “n”.
In the first
step, two sets are maintained:
OPEN SET:: It contains the set of nodes that needs to
CLOSED SET:: It contains the set of nodes that have
already been visited or examined.
node “n” maintains the function g(n), h(n) and f(n).
Each node also maintains link pointer to its parent node s that
the best solution can be retrieved, if found.
AO* algorithm is
the modified version of A* algorithm in order to cover up the limitations of A*
The AO* uses a
single structure i.e. “G”, unlike two sets
OPEN and CLOSE that was used in A*
“G” represents the part of the graph that
has been generated so far.
Each node of the
structure “G” is always connected either to
its immediate successor or predecessor.
The nodes of the
structure “G” also contains their
respective distance/cost from each other.
The cost between
the starting node to current node “n” of
structure “G” is not
Through this, AO* is always able to find solutions with minimum