Monday, 12 September 2016

Search Process in Artificial Intelligence

Search process in artificial intelligence is very important concept in concept :-

  1. Brute Force Search
  2. Heuristics Search
Brute Force Search -

  • DFS - Depth First Search
  • BFS - Breadth First Search
Heuristics Search : -

  • Hill Climbing
  • Best First Search
  • Constraint Satisfaction
  • Mean - End Analysis
  • A* Algorithm 
  • AO* Algorithm
Brute Force Search  :- Brute force search is un-unformed or blind search. It is used for searching small instances. It is direct approach to solve the problem accoding to given problem statement and defination of concept involved. It is very simple and easy process to solve the small size problem. It requires n-1 multiplications.

DFS (Depth First Search) :- DFS is the search used for searching graphs and trees in data structure. The search starts with the root node and search continous to the ending of the graph or tree according to our requirement.It also explores the branches and their nodes as well. Here the data structure to store the nodes is STACK

Algorithm: -

  • GOTO the un-visited adjecent node and mark it as visited and push into stack
  • If the visited node having no child node the pop it out of the stack
  • If the visited node having child nodes the GOTO the child nodes.
  • Repeat this step untill the graph ot tree become empty
  • Remember the top of the stack will changing while we are traversaling the tree or graph
BFS (Breadth first search) :- BFS is the search used for searching graphs and trees in data structure. The only difference between DFS and BFS is that in DFS we will visit all child nodes (left and right) then we will move to the next, but in BFS we will goto the depth of the visited node (i.e if it visit the left node it will complete traversal left side of the tree and the it comes to the right node, vice versa)
Here the data structure to store the nodes is QUEUE.

Algorithm :-

  • Here there is the concept of CURRENTLY WORKING NODE
  • GOTO the root node and mark it as the currently working node 
  • Then visit the child nodes and queue it into queue data structure one by one
  • Then update the currently working node as any one of the child and de-queue it from queue data structure one by one
  • Then traversal to he childs of the currently working node and repeat the same process until the tree or graph gets finish.  

No comments:

Post a Comment