BFS,DFS,Depth bound,Beam search,Iterative.pptx

BFS,DFS,Depth bound,Beam search,Iterative.pptx

1. Uninformed Search Strategies Uninformed strategies use only the information available in the problem definition. All they can do is generate successors and distinguish a goal state from a non-goal state. All search strategies are distinguished by the order in which nodes are expanded. Uninformed (blind) Search Strategies are: Breadth-first Search Uniform-cost Search Depth-first Search Depth-limited Search Iterative Deepening Search

2. Breadth-First Search Breadth-first search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. All nodes are expanded at a given depth in search tree before any nodes at next level are expanded. Breadth-first search uses a FIFO queue for the frontier

3. Breadth-First Search

4. Breadth-First Search: Example F r o ntier A E x plo r ed empty

5. Breadth-First Search: Example F r o ntier B C E x plo r ed A

6. Breadth-First Search: Example F r o ntier C D E E x plo r ed A, B

7. Breadth-First Search: Example F r o ntier D E F G E x plo r ed A, B, C

8. Uniform-Cost Search When all step costs are equal, breadth-first search is optimal because it always expands the shallowest unexpanded node. In general, it is not optimal when step costs are different. By a simple extension, we can find an algorithm that is optimal with any step-cost function . Uniform-cost search expands node n with the lowest path cost g(n) . This is done by storing the frontier as a priority queue ordered by g. Uniform-cost search is equivalent to breadth-first if step costs are all equal Uniform-cost search is an uninformed search algorithm that uses the lowest cumulative cost to find a path from the source to the destination. Nodes are expanded, starting from the root, according to the minimum cumulative cost. The uniform-cost search is then implemented using a Priority Queue.

9. Algorithm for uniform cost search: I nsert the root node into the priority queue Remove the element with the highest priority. If the removed node is the destination, print total cost and stop the algorithm Else if, Check if the node is in the visited list Else Enqueue all the children of the current node to the priority queue, with their cumulative cost from the root as priority and the current not to the visited list.

10. Example First, we just have the source node in the queue: Then, we add its children to the priority queue with their cumulative distance as priority and add the source to the visited list:

11. Now, A has the minimum distance (i.e., maximum priority), so it is extracted from the list. Since A is not the destination, its children are added to the priority que and A is added to the visited list. B has the maximum priority and also not in the visited list so its children are added to the priority que:

12. Up next, G has the maximum priority but its not the Dest nor it has any children its a dead end G will be added to the visited list C has the maximum priority , so we will enqueue the children of C and add it to visited list:

13. Next the E has the maximum priority we add it children to the que and add E to the visited list. The next minimum distance is that of E, so enqueue its children and add it to visited list. Now we have two maximum values. The priority queue serves the F first as it was added before then Dest and added it to the visited list:

14. Finally, We added the Dest node to the visited list, check that it is our target, and stop the algorithm here. The minimum distance between the source and destination nodes (i.e., 8) has been found.

15. Depth-First Search Depth-first search always expands deepest unexpanded node in frontier of search tree. As nodes are expanded, they are dropped from frontier, so then search “backs up” to next deepest node that still has unexplored successors. Depth-first search uses a LIFO queue (STACK). A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent.

16. Depth-First Search Depth-first search on a binary tree. Explored nodes with no descendants in the frontier are removed from memory. Nodes at depth 3 have no successors and M is the only goal node.

17. Depth-First Search

18. Depth-First Search

19. Depth-First Search

20. Depth-First Search

21. Depth-First Search

22. Depth-First Search

23. Depth-First Search

24. Depth-First Search

25. Depth-First Search

26. Depth-First Search

27. Depth-First Search Goal (M) is found

28. Depth-Limited Search The failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth limit ℓ. Nodes at depth ℓ are treated as if they have no successors. This approach is called depth-limited search . The depth limit solves the infinite-path problem. Unfortunately, it also introduces an additional source of incompleteness if we choose ℓ < d, that is, the shallowest goal is beyond the depth limit. Depth-limited search will also be non-optimal if we choose ℓ > d. Its time complexity is O(b ℓ ) and its space complexity is O(bℓ). Depth-first search can be viewed as a special case of depth-limited search with ℓ=∞.

29. Depth-Limited Search Recursive implementation

30. Iterative Deepening Depth-First Search

31. Iterative deepening search l =

32. Iterative deepening search l = 1

33. Iterative deepening search l = 2

34. Iterative deepening search l = 3

35. Depth bounded DFS (DBDFS) Depth bound DFS is a combination of DFS and BFS. Both depth first and breadth first advantages can be achieved with carefully designing the DDFS. The problem with DFS is that if the search paths are very long and solution lies somewhere in the right branch than it takes a huge time. Depth bound (or sometimes mentioned as Depth Limited) search assumes a typical length as final and start like a normal DFS. When it reaches a typical boundary, it assumes dead end and try alternate paths .