Week 2/3 - Search

What is breadth-first search (BFS)?

BFS is a search strategy that expands the shallowest unexpanded node first. It explores nodes level by level.

What is the time and space complexity of BFS?

Both time and space complexity are O(b^d), where b is the branching factor and d is the depth of the shallowest solution.

Is BFS complete and optimal?

BFS is complete if b is finite. It is optimal if all step costs are equal, but not optimal in general.

What is uniform-cost search?

Uniform-cost search expands the node with the lowest path cost first, using a priority queue ordered by path cost.

What is the time and space complexity of uniform-cost search?

Both are proportional to the number of nodes with path cost less than or equal to the optimal solution cost, i.e., O(b^C/ε), where C is the cost of the optimal solution and ε is the minimum action cost.

Is uniform-cost search complete and optimal?

Yes, it is complete if step costs are greater than zero and is always optimal.

What is depth-first search (DFS)?

DFS is a search strategy that expands the deepest unexpanded node first, using a LIFO stack structure.

What is the time and space complexity of DFS?

Time complexity is O(b^m), where m is the maximum depth of the search tree. Space complexity is O(bm).

Is DFS complete and optimal?

DFS is not complete in infinite-depth spaces or with loops. It is not optimal.

What is depth-limited search (DLS)?

DLS is a variant of DFS with a depth limit l, preventing the search from going deeper than l levels.

What are the completeness and optimality properties of DLS?

DLS is complete if the solution is within the depth limit. It is not optimal.

What is iterative deepening search (IDS)?

IDS performs a series of depth-limited searches, increasing the depth limit with each iteration until a solution is found.

What is the time and space complexity of IDS?

Time complexity is O(b^d), and space complexity is O(bd), combining DFS’s space efficiency with BFS’s completeness.

Is IDS complete and optimal?

Yes, IDS is complete and optimal if step cost = 1. It can be modified for uniform-cost problems.

What is bidirectional search?

Bidirectional search runs two simultaneous searches—from start and from goal—hoping to meet in the middle.

What is the time and space complexity of bidirectional search?

Both time and space complexity are O(b^(d/2)), significantly better than unidirectional strategies.

Is bidirectional search complete and optimal?

It is complete and optimal if BFS is used in both directions. Requires reversible actions and efficient overlap detection.

What are the four components of a single-state problem formulation?

1. Initial state 2. Actions (successor function) 3. Goal test 4. Path cost

What is the purpose of the goal test in a search problem?

To determine whether a given state satisfies the goal condition.

What is a path cost?

A numeric value that represents the cost of a sequence of actions, typically summed over each step.

What is a state in AI search?

A configuration of the world that the agent can be in.

What is a node in AI search?

A data structure used in search trees that contains a state, a parent node, the action taken to reach it, path cost, and depth.

How do states differ from nodes?

States represent physical configurations, while nodes include metadata like parent, depth, and path cost for tree traversal.

What are the four criteria used to evaluate search algorithms?

1. Completeness 2. Time complexity 3. Space complexity 4. Optimality

What does it mean for a search algorithm to be complete?

It is guaranteed to find a solution if one exists.

What does optimality mean in the context of search algorithms?

The algorithm finds the least-cost solution among all possible solutions.

What is best-first search?

A search strategy that expands the most promising node according to a given evaluation function f(n).

How does best-first search differ from uninformed search methods?

Best-first search uses a heuristic to evaluate nodes, whereas uninformed methods like BFS or DFS do not use domain knowledge.

What is greedy best-first search?

Best-first search using only the heuristic function: f(n) = h(n). Chooses the node that appears closest to the goal.

What are the properties of greedy best-first search?

Not complete in infinite spaces, not optimal, time and space complexity is O(b^m) in the worst case.

What is A* search?

Best-first search using f(n) = g(n) + h(n), combining actual path cost and heuristic estimate to the goal.

What are the properties of A* search?

Complete and optimal if h(n) is admissible; time and space complexity can be exponential.

What does it mean for a heuristic to be admissible?

It never overestimates the true cost to reach the goal: h(n) ≤ h*(n) for all n.

What does it mean for a heuristic to be consistent (monotonic)?

h(n) ≤ cost(n, n') + h(n') for every successor n' of n. Ensures f-values are non-decreasing.

Why is consistency stronger than admissibility?

Every consistent heuristic is admissible, but not all admissible heuristics are consistent.

What is a heuristic function?

A function h(n) that estimates the cost to reach the goal from node n.

How can you design heuristics for search problems?

Heuristics can be derived by simplifying the problem (relaxed problem) or using domain-specific strategies such as MST for TSP.

What are common heuristics for the 8-puzzle problem?

1. Number of misplaced tiles, 2. Total Manhattan distance.

What is the effect of a better (more accurate) heuristic?

Leads to faster search by reducing the number of expanded nodes.

What does it mean for one heuristic to dominate another?

Heuristic h2 dominates h1 if h2(n) ≥ h1(n) for all n and both are admissible. It results in fewer node expansions.

What is hill-climbing search?

An iterative algorithm that moves in the direction of increasing value (higher h or lower cost), choosing the best neighbor.

What are drawbacks of hill-climbing?

Can get stuck in local maxima, plateaus, or ridges. Not complete or optimal.

What is a local maximum in hill-climbing?

A state that is better than its neighbors but worse than the global optimum.

What is a plateau in hill-climbing?

A flat region where many neighboring states have the same value, making progress difficult.

What is a ridge in hill-climbing?

A region with a sharp peak that requires successive sideways moves to ascend.

What is iterative improvement in search?

A class of local search methods that improve a complete candidate solution by iteratively making small changes.

What is the n-queens problem, and how is it solved via iterative improvement?

The n-queens problem involves placing n queens on an n×n board with no conflicts. Iterative improvement moves queens to reduce conflicts until a solution is found.

What is the min-conflicts heuristic used in iterative improvement?

At each step, choose a variable that’s in conflict and assign it a value that minimizes the number of conflicts.

How does hill-climbing relate to iterative improvement?

Hill-climbing is a specific type of iterative improvement that always chooses the best local move.

What is stochastic hill-climbing?

A variation of hill-climbing where a randomly selected uphill move is chosen rather than the steepest ascent.

What is random-restart hill-climbing?

An approach that repeatedly performs hill-climbing from random initial states to escape local maxima.

How is the TSP problem solved using a minimum spanning tree heuristic?

Use a spanning tree to approximate the shortest path covering all cities, then perform a traversal to build a feasible tour.

How is the TSP problem solved using a minimum spanning tree heuristic?

Use a spanning tree to approximate the shortest path covering all cities, then perform a traversal to build a feasible tour.