Best First Search.pptx

PPT on BFS(Best First Search)

1. Government College of Engineering & Textile Technology, Serampore NAME-MUKTARUL HOQUE STREAM-INFORMATION TECHNOLOGY ROLL-11000220015 SUBJECT- ARTIFICIAL INTELLIGENCE

2. Best First Search Algorithm Guided By Mr. Biplab Mahapatra (State Aided College Teacher,IT Depaerment ) Defination : Best first search is a traversal technique that decides which node is to be visited next by checking which node is the most promising one and then check it. For this it uses an evaluation function to decide the traversal. This best first search technique of tree traversal comes under the category of heuristic search or informed search technique. The cost of nodes is stored in a priority queue. This makes implementation of best-first search is same as that of breadth First search. We will use the priorityqueue just like we use a queue for BFS

3. Process We have studied two uninformed search algorithms such as   Breadth First search (BFS)  and  Depth First search(DFS)   Algorithm. DFS is good because it allows a solution to be found without all competing branches having to be expanded BFS is good because it does not get branches on dead-end paths One way of combining the two is to follow a single path at a time, but switch paths whenever some competing path looks more promising than the current one does.

4. At each step of the BFS search process, we select the most promising of the nodes we have generated so far . This is done by applying an appropriate heuristic function to each of them . We then expand the chosen node by using the rules to generate its successors It proceeds in steps, expanding one node at each step until it generates a node that corresponds to a goal state.

5. At each step, it picks the most promising of the nodes that have so far been generated but not expanded . It generates the successors of the chosen node, applies the heuristic function to them, and adds them to the list of open nodes, after checking to see if any of them have been generated before.

6. Algorithm: Best-First Search 1. Start with OPEN containing just the initial state 2. Until a goal is found or there are no nodes left on OPEN do: a) Pick them best node on OPEN. b) Generate its successors. c) For each successor do: i ) if it has not been generated before, evaluate it, add it to OPEN, and record its parent. ii) If it has been generated before, change the parent if this new path is better than the previous one. In that case, update the cost of getting to this node and to any successors that this node may already have.

7. Example: Best-First Search Q.Here   C  is the initial or source node and  L  and  Z  are goal nodes . Open: C Closed: —

8. Now, C is added to Closed, and B, T, O, E and P are added to Open . Open: T, O, E, B, P Closed: C

9. Now, T has the least distance hence, T is added to Closed. Open : O, E, B, P Closed: C, T

10. As T does not have any successors, the next node from open that is O is removed from Open and added to closed . Open: E, B, P Closed: C, T, O

11. The successors of node O that is node I and N are added to Open. Open : I, E, B, P, N Closed: C, T, O

12. Now, node I is removed from Open and added to closed. Open : E, B, P, N Closed: C, T, O, I

13. The successor of I that is Z is added to Open . Open: Z, E, B, P, N Closed: C, T, O, I

14. Now, node Z is removed from Open and added to closed. Open: E, B, P, N Closed: C, T, O, I, Z The Goal is found. The final path is C – O – I – Z.

15. conclusion 1 . Can switch between BFS and DFS, thus gaining the advantages of both. 2. More efficient when compared to DFS.

16. References https://www.tutorialspoint.com/best-first-search-informed-search https://www.geeksforgeeks.org/best-first-search-informed-search/ https://www.javatpoint.com/ai-informed-search-algorithms

17. THANK YOU