Determine order that breadth first search will expand nodes

Assignment Help Software Engineering

Reference no: EM1366936

Consider the following graph representing the state space and operators of a navigation problem:

• S is the start state and G is the goal state.
• When placing expanded child nodes on a queue, assume that the child nodes are placed in alphabetical order (i.e. if node S is expanded the queue will be: A B).
• Assume that we never generate child nodes that appear as ancestors of the current node in the search tree

1. What is the order that breadth first search will expand the nodes? S,A,B,D,C,E,G
2. What is the order that depth first search will expand the nodes? S,B,E,F,D,G
3.What is the order that iterative deepening search will expand the nodes?
4. Describe a search space where iterative deepening performs much worse than depth first search.
5. Construct a search tree where it is possible that DFS will use more memory than BFS.
6. Suppose we have a problem space where there is a uniform branching factor b and there is a single goal node at depth m. What is the minimum number of nodes expanded and the storage needed for BFS and DFS? (Hint: this question asks about the best case performance of BFS and DFS).

Reference no: EM1366936

Questions Cloud

Write the start-up steps in windows nt : Write the start-up steps in Windows NT. Provide estimate for the capital investment needed in computer forensics for a 2,000,000 population.

Show how can religion affect a multicultural workplace : How might management ensure sensitivity to each person's religious beliefs in a multicultural workplace?

Concepts of compassion fatigue : Recognize the warning signs for at least five concepts of compassion fatigue. Present the nature of the problems and their causes.

Improve listening skills and understanding body language : Explain how can we as managers/leaders use body language to communicate leadership

Determine order that breadth first search will expand nodes : Determine the order that breadth first search will expand the nodes? S,A,B,D,C,E,G. What is the order that depth first search will expand nodes? S,B,E,F,D,G

Determining determinants of demand : Suppose your product is Wendy's hamburgers. First "draw" the demand and suppy curve and see how the equilibrium price and quantity is determeined.

Calculating break-even and operating leverage : Dime a Dozen Diamonds creates synthetic diamonds through treating carbon. every diamond can be sold for $100. The materials cost for a standard diamond is $30.

Mobilizing community partnerships : Mobilize Community Partnerships to recognize and Solve Health Problems, please help me explain in detail, the strengths of this standard in addition to one potential improvement as a result of this standard.

Explain ethics of developing type of system : Number of citizens and their actions. Clearly this has privacy, implications. Explain the ethics of developing this type of system.

User Account

All Pages