Uninformed search /Blind search in AI

here is my 5th ppt on state space search and problem solving techniques.
must my watch my videos on my youtube channel techiseasy

1. Uninformed/Blind Search Techniques ARTIFIC I AL INTELLIGENCE PART #5

2. Tree S earching A tree search starts at the root and explores nodes from there, looking for a goal node (a node that satisfies certain conditions, depending on the problem) For some problems, any goal node is acceptable ( N or J ); Here minimum-depth goal node, that is, a goal node nearest the root is only J . 2 L M N O P Q H I J K F G E D B C A Goal nodes

3. Searching Methods Breath First Search (BFS) Depth First Search (DFS) Bidirectional Search.

4. Breadth-First Search Breadth First Search (BFS) searches breadth-wise . Ea ch node is a state which may a be a potential candidate for solution. I mplemented by maintaining a queue of nodes . I nitially the queue contains just the root. In each iteration, node at the head of the queue is removed and then expanded. The generated child nodes are then added to the tail of the queue. H I J K F G E D B C A L M N O P Q For example, after searching A , then B , then C , the search proceeds with D , E , F , G Node are explored in the order A B C D E F G H I J K L M N O P Q

5. A lgorithm : BFS C rea t e a v ar i a b l e c a l l e d N O D E - L I ST a n d se t i t t o t h e initial state. L oo p u n t i l t h e g oa l s t at e i s f o und o r N O D E - LI ST i s empty. Rem o v e t he f i r s t e l e m e n t , sa y E, f ro m t he N O D E- LIST. If NODE-LIST was empty then quit. Fo r eac h w a y t h a t e a c h r u l e ca n m atc h t he sta t e described in E do: Apply the rule to generate a new state. If the new state is the goal state, quit and return this state. Otherwise add this state to the end of NODE-LIST

6. Advantages & Disadvantages : BFS Breadth first search will never get trapped exploring the useless path forever. If there is a solution, BFS will definitely find it out . If there is more than one solution then BFS can find the minimal one that requires less number of steps . The main drawback of BFS is its memory requirement . Therefore, the space complexity of BFS is O( b d ) . If the solution is farther away from the root , breath first search will consume lot of time .

7. D epth F irst S earch Depth First Search (DFS) searches deeper into the problem space. D FS always generates successor of the deepest unexpanded node. Depth First Search uses last-in first-out stack for keeping the unexpanded nodes. DFS is implemented recursively , with the recursion stack taking the place of an explicit node stack. For example, after searching A , then B , then D , the search backtracks and tries another path from B Node are explored in the order A B D E H L M N I O P C F G J K Q N will be found before J

8. A lgorithm : DFS If the initial state is a goal state, quit and return success. Otherwise, loop until success or failure is signalled. Generate a state, say E, and let it be the successor of the initial state. If there is no successor, signal failure. Call Depth-First Search with E as the initial state. If success is returned, signal success. Otherwise continue in this loop.

9. The advantage of DFS is that memory requirement is only linear with respect to the search graph. The time complexity of a depth-first Search to depth d is O( ) since it generates the same set of nodes as BFS. If depth-first search finds solution without exploring much in a path then the time and space it takes will be very less.   Advantages & Disadvantages : D FS Even a finite graph can generate an infinite tree . Depth-First Search is not guaranteed to find the solution. Th ere is no guarantee to find a minimal solution , if more than one solution exists.

10. Bidirectional Search The algorithms so far use forward reasoning, i.e. moving from the start node towards a goal node. some cases we could use backward reasoning, i.e. moving from the goal state to the start state. Forward and backward reasoning can be combined into a technique called bidirectional search. One starting from the initial state and searching forward One starting from the goal state and searching backward The search terminates when the two graphs intersect