WorksheetsLecture 2b: Solving Search Problems - Parte1
Total questions: 23
Worksheet time: 12mins
What is the methodology to carry out the Solution search?
Execute the goal test
Stop the search after 3 iterations
Start with the final state
Choose a random state to expand
How do we decide which node from the frontier to expand next in Best-First Search?
Choose a node with minimum value of h(n)
Choose a node with maximum value of g(n)
Choose a node with minimum value of f(n)
Choose a node with maximum value of f(n)
What are the components of a Tree Node in the search data structures?
State, Child, Operator, Path length, Depth
State, Parent, Operator, Path cost, Depth
State, Parent, Action, Path cost, Height
State, Sibling, Operator, Path cost, Depth
Which search strategy expands nodes at the lowest depth first?
Uniform Cost Search
Depth-First Search
Breadth-First Search
Iterative Deepening Search
What is the time complexity of Breadth-First Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b/d)
O(b+d)
O(b*d)
O(b^d)
What is the strategy of Dijkstra’s algorithm/Uniform Cost Search?
Expand the node with the highest cost
Expand the node with the highest depth
Expand the node with the lowest cost
Expand the node with the lowest depth
What is the time complexity of Depth-First Search in terms of the maximum branching factor (b) and maximum depth of the state space (m)?
O(b*m)
O(b+m)
O(b-m)
O(b^m)
What is the strategy of Iterative Deepening Search?
Perform unlimited depth search, iteratively, always decreasing the depth limit
Perform unlimited depth search, iteratively, always increasing the depth limit
Perform limited depth search, iteratively, always increasing the depth limit
Perform limited depth search, iteratively, always decreasing the depth limit
Which search strategy is good for problems with lots of solutions and very little memory required?
Iterative Deepening Search
Breadth-First Search
Depth-First Search
Uniform Cost Search
What is the space complexity of Breadth-First Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b^d)
O(b*d)
O(b+d)
O(b/d)
What is the complexity in time and space of Iterative Deepening Search?
O(bd) and O(bd)
O(b+d) and O(b-m)
O(b*d) and O(bm)
O(b^d) and O(bd)
What is the strategy of Breadth-First Search?
Expand nodes at lowest depth first
Expand the node with the highest depth
Expand the node with the lowest cost
Expand the node with the highest cost
What is the strategy of Depth-First Search?
Expand the node with the lowest cost
Expand the node with the highest cost
Expand the node with the highest depth
Always expand one of the deepest nodes in the tree
What is the strategy of Uniform Cost Search?
Expand the node with the lowest cost
Expand the node with the highest cost
Expand the node with the highest depth
Always expand the border node with the lowest cost
What is the strategy of A* Search?
Expand the node with the lowest cost
Expand the node with the highest cost
Expand the node with the lowest depth
Expand the node with the highest depth
What is the time complexity of A* Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b/d)
O(b+d)
O(b*d)
O(b^d)
What is the space complexity of A* Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b^d)
O(b*d)
O(b+d)
O(b/d)
What is the time complexity of Greedy Best-First Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b/d)
O(b+d)
O(b*d)
O(b^d)
What is the space complexity of Depth-Limited Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b^d)
O(b*d)
O(b+d)
O(b/d)
What is the strategy of Hill Climbing Search?
Always move to the neighbor with the highest value
Always move to the neighbor with the lowest value
Move to a random neighbor
Move to the neighbor with the lowest value only if it improves the current state
What is the time complexity of Depth-Limited Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b^d)
O(b*d)
O(b+d)
O(b/d)
What is the space complexity of Depth-Limited Search in terms of the maximum branching factor (b) and depth of the least-cost solution (d)?
O(b^d)
O(b*d)
O(b+d)
O(b/d)
What is the strategy of Uniform Cost Search?
Expand the node with the lowest cost
Expand the node with the highest cost
Expand the node with the highest depth
Always expand the border node with the lowest cost
