Depth-First Search Basics

Play an AI-generated podcast conversation about this lesson

Depth-first search always expands the deepest node in the current frontier.

True (A)

A heuristic h(n) is admissible if it only overestimates the cost to reach the goal in a few cases.

False (B)

Consider depth-limited search on a uniform search tree with branching factor 𝑏, maximum depth 𝑙 (for the limit of depth-limited search as well as the search tree) and assume that the only node with a goal state is at depth 𝑑. The time complexity of depth-limited search is 𝑂(𝑏𝑑).

False (B)

Consider a route finding problem like the ones discussed in class. A colleague suggests to use half the line of sight distance from a state to the goal as a heuristic. This is an admissible heuristic.

True (A) Signup and view all the answers

Assume a finite state space and that all step costs are positive. Greedy best-first search is optimal if we use the true minimal path cost from a node to the goal as the heuristic.

False (B) Signup and view all the answers

Uniform cost-search always expands the node from the frontier with the lowest path cost 𝑔(𝑛).

True (A) Signup and view all the answers

Which statement(s) are true for A* search?

The evaluation function of a node n is the sum of the path costs from the start node to node n and estimated costs from node n to the goal. (A) Signup and view all the answers

Perform A* search for the problem shown below (start location: Sibiu; destination location: Bucharest). The table shows the heuristic to be used. What is the cost of the found solution?

278 Signup and view all the answers

Consider the route-finding problem shown below with goal state Bucharest. We want to specify an admissible heuristic ℎ(𝑛). How large can ℎ(In(Fagaras)) be at most?

211 Signup and view all the answers

Perform the greedy best-first search for the problem shown below (start location: Sibiu; destination location: Bucharest). The table shows the heuristic to be used. What is the cost of the found solution?

310 Signup and view all the answers

Depth-first search

Depth-first search always expands the deepest node in the current frontier.

Admissible heuristic

A heuristic h(n) is admissible if it only overestimates the cost to reach the goal in at least one case, not just a few.

Depth-limited search complexity

The time complexity of depth-limited search is 𝑂(𝑏𝑙), not 𝑂(𝑏𝑑), when we consider a uniform search tree with branching factor 𝑏, maximum depth 𝑙, and a goal at depth 𝑑.

Line of sight heuristic

If half the line of sight distance from a state to the goal is used as a heuristic, it's admissible because this distance is always less than or equal to the true distance.