UnInformed Search Strategy

UnInformed search strategy further includes two techniques. These are:

Breadth First Search.

Depth First Search.

Breadth 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.

For Example :
Depth First Search

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 nodes.

For Example :
Informed Search Strategy

Informed search strategy further includes two searching techniques. These are:

A* Search Technique.

AO* Search Technique.

A* Search Technique

A* search technique is an informal search strategy but can be called as a form of best first search.

It is a search technique which the most optimistic node is expanded by expanding a graph.

The node of the graph can be evaluated by using two functions i.e. g(n) and h(n).
Here,
g(n) = Cost/Distance to reach node “n”.
h(n) = Cost/Distance to reach from node “n” to the goal node.

For evaluating 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”.
A* Technique : Working

In the first step, two sets are maintained:

OPEN SET:: It contains the set of nodes that needs to be visited/Examined.

CLOSED SET:: It contains the set of nodes that have already been visited or examined.


Every individual 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

AO* algorithm is the modified version of A* algorithm in order to cover up the limitations of A* algorithm.

The AO* uses a single structure i.e. “G”, unlike two sets OPEN and CLOSE that was used in A* algorithm.

The structure “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 stored.

Through this, AO* is always able to find solutions with minimum cost.