How many nodes are expanded by Breadth-first Search in the worst case

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Question 1. How many nodes are in the search tree generated by Breadth-first Search in the worst case if the branching factor is 3 everywhere and the depth of the shallowest goal state is 6?

Question 2. How many nodes are expanded by Breadth-first Search in the worst case if the branching factor is 4 everywhere and the depth of the shallowest goal state is 5?

Question 3. How many nodes are generated by Iterative Deepening Search in the worst case if the maximum depth limit used by it is 3 and the branching factor is 2 everywhere? Count all nodes generated with all depth limits tried before reporting your answer.

Question 4. B(h) denotes the minimum walking distance from house h to bank closest for walkers.  P(h) denotes the minimum walking distance from house h to  post office closest for walkers. L(h) denotes the minimum walking distance from house h to library closest for walkers. Y(h) denotes the minimum walking distance from house h to gymnasium closest for walkers. G(h) denotes the minimum walking distance from house h to grocery store closest for walkers. R(h) denotes the minimum walking distance from house h to restaurant closest for walkers.  Suggest a way to find the utility of a house using these six values, for a retired person who does not have a car and likes to walk, such that a house with higher utility is more desirable. 

Question 5.  If all operators have equal cost and path cost is same as the number of operators on the path, then is UCS (Uniform Cost Search) better than BFS (Breadth-first Search)? Briefly explain your answer.

Question 6. Consider a hybrid search. In this search, Breadth-first Search occurs until all nodes at depth d are generated. If solution is not found, then a node at depth d, denoted by n' is randomly chosen, and Iterative Deepening Search occurs with n' as the root. All nodes in the search tree generated by BFS except those on the path from the root node to n' are deleted. Under what conditions will this search be complete?

Question 7. Is it a good idea to use Iterative Deepening Search to solve an instance of N-queens? Briefly explain your answer.

Question 8. On what kind of combination of instance and state space is bidirectional BFS likely to be more useful? Briefly explain your answer.

Question 9. On what kind of combination of instance and state space is bidirectional BFS likely to be less useful? Briefly explain your answer.

Question 10. is it a good idea to use bidirectional BFS to solve an instance of N-queens? Briefly explain your answer.

Question 11. How many nodes will be generated by Breadth-first Search in the worst case if the depth of shallowest goal state is d2 and the branching factor is b1 at all nodes at depth d1 - 1 and less and is b2 at all nodes at depth d1 and greater, and d2 is greater than d1?

Question 12. Consider BFS, DFS, DLS, UCS, IDS and BBFS (Bidirectional BFS) and 4 types of agents (reflex agents, agents that keep track of their world, goal-based agents, and utility-based agents). Are any of these searches unsuitable for any of these agents? If so, which combinations aren't meaningful?

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of