Quiz 2 - Search

The N-Queen problem is solved using a state space where each state represents a partial arrangement of queens, and the goal is to place _ queens on an _*_ chessboard so that no two queens attack each other.

In a search tree, a_ is a data structure representing a state in the problem space, while the _ represents the path from the initial state to the goal state.

The time complexity of Breadth-First Search (BFS) in terms of branching factor b and depth d isO(_) , while its space complexity is _.

• b^d_, b^d

• d^{b _,} b^d

• bd, bd

• b^d _, d^b

In the Water-Jug problem, the state space consists of:

• All possible sequences of pouring water

• All possible configurations of water levels in the jugs

• Only the goal state and initial state

• Only the transitions between states

The N-Queen problem is solved using which of the following techniques?

• a) Backtracking

• b) Hill Climbing

• c) Both a and b

• d) None of the above

In a search tree, a node that has not yet been expanded is placed in the:

• Open List

• Closed List

• Goal List

• None of the above

Breadth-First Search (BFS) is guaranteed to find:

• Any solution

• The shallowest solution

• The least-cost solution

• The fastest solution

Which of the following search strategies is uninformed?

• A* Search

• Greedy Best-First Search

• Iterative Deepening Depth-First Search (IDDFS)

• Hill Climbing

Uniform Cost Search selects the node with:

• The highest heuristic value

• The lowest cost from the initial state

• The deepest depth in the search tree

• The most promising heuristic estimate

The Greedy Best-First Search algorithm uses which function for evaluation?

• f(n)=g(n)+h(n)

• f(n)=h(n)

• f(n)=g(n)

• f(n)=h(n)−g(n)