Consider the following table, which summarizes important properties of uninforme
ID: 3585839 • Letter: C
Question
Consider the following table, which summarizes important properties of uninformed tree search techniques under specific assumptions (as shown in Fig. 3.21, p. 91): 1. Criterion Breadth- Uniform Depth- Depth- Iterative First Cost First Limited Deepening Complete? Yes Time O(ba Space O(b) Optimal Yes Yes O(bd) O(bd) Yes Yes Obeece O(bm) No No o(b) o(bec O(bm) O(bl) Yes No No Consider a finite search space with branching factor b containing a single optimal solution whose depth d equals the maximum depth of the search space, m. If all step costs are equal and the depth limit / for depth-limited search equals d, rank a) the five search techniques from smallest (best) to greatest (worst) expected execution time, clearly identifying when two or more techniques have the same time complexity according to CO Now consider a search space for which the branching factor b is finite, the single optimal solution exists at finite depth d, and the maximum depth m is finite, but there may be different finite positive step costs between adjacent nodes. For each of the five search techniques, state whether or not that technique is complete and b) whether or not it is optimal c) Is there a search space for which uniform-cost search is not optimal? Explain your answer.Explanation / Answer
a)
Since the depth of the solution d is equal to the search space max depth m, the time complexity of depth-first = time complexity of breadth first.
Since the depth limit l = d, time complexity of depth limited = time complexity of breadth-first
The best case time complexity is Uniform-cost. Followed by Breadth-first, depth-first and depth-limited and Iterative-deepening, which are of same complexity.
b)
Breadth-first - Complete & Optimal
Uniform-cost - Complete and not optimal
Depth-first - Not complete and not optimal
Depth limited - Not complete and not optimal
Iterative-deepening - Complete & Optimal
c)
Uniform-cost search is not optimal when the cost between adjacent nodes is not uniform.