Breadth first search and bidirectional search strategies question: The bidirecti

Question

Breadth first search and bidirectional search strategies question:

The bidirectional search starts at both the goal and initial states, working out until their paths merge. This effectively reduces the space and time complexity to 0(b^d/2) versus O(b^d) for breadth first search (BFS), which is substantial (for example, with b = 4 and d = 20, that is a reduction from tilde 1 times 10^12 (tilede 1,000,000,000,000) to tilde 1 times 10^6 (tilde 1,000,000)). Assume the branching factor is finite and the step size is constant. Then if both search directions use BFS, the search is complete and the solution will be optimal. Assume an oracle gives you a state in the exact middle of the optimal solution path-halfway from the Start to the Goal in the diagram above. Under the same assumptions as above, if you search outward from each of these three nodes (Start, Center, and Goal) using BFS, what would the values be for: Completeness Time complexity Space complexity Optimality

Explanation / Answer

1. Completeness : Is the algorithm guaranteed to find a solution when there is one.Hence its value is Yesa, where,a complete if b is finite.

2. Time Complexity: O(bd)

3. Space Complexity : O(bd)

4. Optimality : Yesc, where, c optimal if step costs are all identical

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---