CSE 4355 · W3 C1 · UCS, DLS and IDS

01 Cold open 0–4 min

60 km of wasted diesel

Last week's BFS sent us Dhaka → Chandpur → Feni → Chattogram → Cox's Bazar: 465 km. Via Cumilla it is 405 km.

Same number of hops, so BFS could not tell them apart. An ambulance, a Pathao rider or a cargo truck pays for kilometres (or minutes, or taka), not for hops.

Today's question: if roads have different costs, which city should a search look at next?

02 Concept 4–9 min

Uniform-cost search: cheapest first

function UNIFORM-COST-SEARCH(problem)
  frontier ← priority queue ordered by g, holding s₀ (g = 0)
  explored ← ∅
  loop
    if frontier is empty: return failure
    node ← POP-LOWEST-g(frontier)
    if IS-GOAL(node.state): return SOLUTION(node)   # test on POP
    add node.state to explored
    for each child of node:
      if child.state not in explored or frontier: insert child
      else if it is in frontier with a higher g: replace that entry

g(n) = cost of the path from the start to n. Adapted from Russell & Norvig's uniform-cost search.

Two changes from BFS

1. The FIFO queue becomes a priority queue on g(n).

2. The goal test moves to when a node is popped, not when it is generated.

(Plus: if a cheaper path to a frontier state turns up, keep the cheaper one.)

Pop culture

Edsger Dijkstra designed his shortest-path algorithm in about twenty minutes, sitting at a café in Amsterdam in 1956, without pencil and paper. UCS is Dijkstra's algorithm that stops as soon as the goal is popped.

03 Live lab 9–14 min

Live lab: UCS on the road to Cox's Bazar

UCS vs BFS: Dhaka → Cox's Bazar The frontier is now sorted by g (km so far). Watch Cox's Bazar sit on the frontier at 405 km while cheaper cities are popped first.

frontierexploredbeing expandedparent linksolution

Frontier

priority queue: pop lowest g

DHK0

Explored set

never expand these again

empty

initStart: frontier = [Dhaka]

Expanded0

Max frontier1

Cost—

Hops—

04 Worked example 14–20 min

Worked example: UCS by hand

Given

Last week's map (km approximate). Start Dhaka, goal Cox's Bazar. Graph search, ties broken alphabetically.

Find

The expansion order, the frontier after each expansion, and the route returned.

Method: uniform-cost graph search (Russell & Norvig)

Solution

Predict the answer first. Then reveal one step at a time.

05 Concept 20–24 min

Why cheapest-first is optimal

With step costs ≥ 0, UCS pops nodes in non-decreasing order of g. Popping never goes back to something cheaper.
When the goal is popped with cost C, every node still on the frontier has g ≥ C.
Any other path to the goal must pass through one of those frontier nodes, so it costs at least C. Nothing cheaper exists: C is optimal.

Gotcha

Test the goal when it is generated and step 2 breaks: you stop with an upper bound, not the minimum. In the next problem that mistake returns a 12-unit path when a 7-unit one exists.

Exam line

"UCS is optimal because it expands nodes in order of increasing path cost, so the first time it selects a goal node for expansion, that node's path is the cheapest."

Pro tip

If every step costs the same, ordering by g is ordering by depth: UCS behaves exactly like BFS.

06 Concept 24–27 min

UCS: complete, optimal, and what it costs

Question	Uniform-cost search
Complete?	Yes, if b is finite and every step costs at least some ε > 0
Optimal?	Yes, for any step costs ≥ 0 (with ε > 0 for completeness)
Time and space	$O\!\left(b^{\,1+\lfloor C^*/\varepsilon\rfloor}\right)$

C* = cost of the optimal solution, ε = the smallest step cost. C*/ε is the deepest the optimal path could be, if every step were as cheap as possible.

Gotcha

Why ε > 0? With zero-cost steps (a free U-turn, a NoOp action) tree-search UCS can loop forever on a path whose cost never grows.

Pro tip

When all steps cost the same, C*/ε = d, and the bound becomes b^d+1: BFS with the goal test on pop.

07 Your turn 27–31 min

Your turn · 1: UCS, and the road that lies

04:00

1 Exam CQ

Run UCS graph search from S to G. Show the sorted frontier after each expansion and the path returned.

Then: what would you return if you tested for the goal as soon as it was generated?

Work it out first.
Press Solve when the class has an answer.

08 Think deeper 31–34 min

Critical thinking · when cheapest-first lies

Think deeper

A map app adds a negative cost for roads that pass a sponsor's shop (−10 'reward'). Does UCS still return the cheapest route?

Argue it in pairs for two minutes. There may be more than one defensible answer.

Think deeper

The hospital-robot problem has a free action Wait (cost 0). What can go wrong for UCS, and how do you fix it?

Argue it in pairs for two minutes. There may be more than one defensible answer.

09 Concept 34–38 min

Depth-limited search: DFS on a leash

function DLS(node, ℓ)
  if IS-GOAL(node.state): return SOLUTION(node)
  if ℓ = 0: return cutoff              # the leash
  cut ← false
  for each child of node:
    result ← DLS(child, ℓ − 1)
    if result = cutoff: cut ← true
    else if result ≠ failure: return result
  return cut ? cutoff : failure

DFS that treats nodes at depth ℓ as if they had no children. Infinite paths and endless loops are no longer a problem.

Two kinds of "no"

failure: searched everything, there is no solution.

cutoff: no solution within ℓ; one may exist deeper.

Pro tip

Choosing ℓ: use what you know. Every city on our map reaches every other in at most 5 roads (Sylhet to Bandarban is the longest), so ℓ = 5 can never miss a route. That number is the map's diameter.

10 Live lab 38–45 min

Live lab: DLS and IDS on a tree

Depth-limited and iterative deepening search Click any node to make it the goal (or pick “none”). Step through and watch the stack: it never holds more than one path.

Stack (current path)

root on the left, top on the right

Roundℓ = 0

Visits so far1

Max stack1

BFS needs13 visits

Result…

ℓ=0Round ℓ = 0: visit A (depth 0): at the limit, children not expanded (cutoff).

11 Worked example 45–49 min

Worked example: IDS round by round

Given

The tree below, goal G. Children are visited left to right; goal test when a node is visited.

Find

The visit order in each round of IDS, the path found, and the total visits compared with BFS.

Method: iterative deepening = DLS with ℓ = 0, 1, 2, … (Russell & Norvig)

Solution

Predict the answer first. Then reveal one step at a time.

12 Concept 49–53 min

Isn't repeating everything wasteful?

Level i is regenerated once for every round from i to d, so d − i + 1 times. Counting generated nodes (root excluded):

N_{\text{IDS}} = d\,b + (d-1)\,b^2 + \cdots + 2\,b^{d-1} + 1\cdot b^{d}

b = 10, d = 5	Nodes generated
BFS: 10 + 100 + 1,000 + 10,000 + 100,000	111,110
IDS: 50 + 400 + 3,000 + 20,000 + 100,000	123,450 (+11 %)

Why so little?

Most of a tree is its bottom level. With b = 10 the last level is 90 % of all nodes, and IDS generates it only once. For large d the ratio tends to b/(b − 1).

b	IDS extra work
2	≈ 100 %
3	≈ 50 %
10	≈ 11 %

Pro tip

Memory: one path plus its siblings, O(bd). For b = 10, d = 5: about 50 nodes instead of 100,000.

13 Your turn 53–57 min

Your turn · 2: count the cost of deepening

03:00

2 Exam CQ

A uniform tree has branching factor b = 3, and the only goal is the right-most node at depth d = 4 (worst case for both).

(a) How many nodes do BFS and IDS generate (do not count the root)? (b) What is the extra work as a percentage? (c) Compare the largest number of nodes each must keep in memory.

Work it out first.
Press Solve when the class has an answer.

14 Concept 57–60 min

Bidirectional search: dig from both ends

Run one search forward from the start and one backward from the goal; stop when the two frontiers meet.

b^{d/2} + b^{d/2} \ll b^{d}\qquad b=10,\ d=6:\ \ 2{,}000\ \text{vs}\ 1{,}000{,}000

Needs the goal as an explicit state (not just a test) and actions you can run backwards.
Memory O(b^d/2): one of the frontiers must be stored to check the meeting.

Pop culture

"Six degrees of separation": LinkedIn finds how you are connected to someone by expanding your contacts and theirs at the same time, and looking for the overlap.

Gotcha

Checkmate in chess is a test (millions of positions pass it), not one state. Searching backward from "all checkmates" is not practical.

15 Concept 60–64 min

The whole uninformed family, one table

Criterion	BFS	UCS	DFS	DLS	IDS	Bidirectional
Complete?	Yes^a	Yes^a,b	No	No	Yes^a	Yes^a,d
Optimal?	Yes^c	Yes	No	No	Yes^c	Yes^c,d
Time	O(b^d)	O(b^{1+⌊C*/ε⌋})	O(b^m)	O(b^ℓ)	O(b^d)	O(b^d/2)
Space	O(b^d)	O(b^{1+⌊C*/ε⌋})	O(bm)	O(bℓ)	O(bd)	O(b^d/2)

^a if b is finite · ^b if every step cost ≥ ε > 0 · ^c if all step costs are equal · ^d if both directions use BFS. b = branching factor, d = depth of the shallowest solution, m = maximum depth, ℓ = depth limit, C* = optimal cost.

Pro tip

Read the IDS column: BFS's guarantees with DFS's memory. That is why it is the default uninformed search when the solution depth is unknown.

16 Think deeper 64–67 min

Critical thinking · which search fits in your phone?

★ Critical thinking

A route planner on a phone has 4 GB free memory. The problem has b = 10 and the solution is at depth d = 12. Each node takes 1 KB; the phone generates 10⁶ nodes per second.

Can BFS do it? Can IDS? What would you tell the app's developer?

Work it out first.
Press Solve when the class has an answer.

17 Real world 67–71 min

Real world: deepening in chess, cheapest-first in networks

Chess engines

Engines such as Stockfish search iteratively deeper: depth 1, 2, 3, … until the clock runs out. Each finished round gives a best move, so the engine always has an answer ready. That is the "anytime" property, and why IDS beats a single deep DFS under time pressure.

The internet

Routers running OSPF use Dijkstra's algorithm (UCS without an early stop) to compute the cheapest path to every other router, with link costs set by bandwidth. Your packet to a server in Singapore followed it.

Think deeper

An ambulance dispatcher in Dhaka uses UCS with travel time as cost. At 5 PM the costs change every minute. What goes wrong, and what would you do?

Argue it in pairs for two minutes. There may be more than one defensible answer.

18 Pop quiz 71–76 min

Pop quiz

Score 0

Question 1 / 5

Uniform-cost search always expands the frontier node with the lowest…

19 Recap 76–80 min

Three things to remember

UCS pops the lowest g(n) and tests the goal on pop. Optimal for costs ≥ 0; complete if every step ≥ ε > 0.

DLS is DFS with a depth limit ℓ: cutoff (maybe deeper) ≠ failure (none at all). Complete only if ℓ ≥ d.

IDS runs DLS for ℓ = 0, 1, 2, …: complete and optimal like BFS (equal costs), O(bd) memory like DFS, ≈ 11 % extra work for b = 10.

HW Before next class

Use the lab's binary tree (A at the root, H–O the leaves, children left to right) with goal K. Write the IDS visit order for every round, count the total visits and compare with BFS. Check yourself with the sim.

Class Test 1 is tomorrow, last 20 minutes: problem formulation, BFS, DFS, UCS, DLS, IDS (traces and the comparison table) and the basics of local search. Bring a pen and a calculator.

Work it out first.
Press Solve when the class has an answer.