Comparing search strategies

Lists the completeness, optimality, and time and space complexity of each search strategy as on the slides, runs BFS, DFS, IDS, UCS, greedy best-first, A*, and weighted A* on one problem side by side, and computes node counts for given b, d, and m.

Lecture reference: Uninformed Search · slides 30–45
Lecture reference: Informed Search · slide 36
Lecture reference: Informed Search · slides 42–43

All search strategies

Algorithm	Complete?	Optimal?	Time complexity	Space complexity
	Yes	If all step costs are equal	O(bᵈ)	O(bᵈ)
Complete if the branching factor b is finite. Optimal if cost = 1 per step. Space is the bigger problem (more than time). Lecture reference: Uninformed Search · slide 31 Lecture reference: Uninformed Search · slide 45
	No	No	O(bᵐ)	O(bm)
Fails in infinite-depth spaces and spaces with loops; avoiding repeated states along the path makes it complete in finite spaces. Returns the first solution it finds. Terrible if m is much larger than d, but may be much faster than BFS when there are many solutions. Linear space. Lecture reference: Uninformed Search · slide 32 Lecture reference: Uninformed Search · slide 45
	Yes	If all step costs are equal	O(bᵈ)	O(bd)
Nodes generated: (d+1)b⁰ + d b¹ + (d−1)b² + … + bᵈ = O(bᵈ). Lecture reference: Uninformed Search · slide 38 Lecture reference: Uninformed Search · slide 45
	Yes	Yes	Number of nodes with g(n) ≤ C*
Complete if every step cost is greater than some positive constant ε. Nodes are expanded in increasing order of path cost. O(b^(C*/ε)), which can be greater than O(bᵈ): the search can explore long paths of small steps before shorter paths of larger steps. Lecture reference: Uninformed Search · slide 44 Lecture reference: Uninformed Search · slide 45
	No	No	Worst case: O(bᵐ)Best case: O(bd)
Can get stuck in loops. Can be much better with a good heuristic. Lecture reference: Informed Search · slide 14 Lecture reference: Informed Search · slide 42
	Yes	Yes (if heuristic is admissible)	Number of nodes with g(n) + h(n) ≤ C*
Complete unless there are infinitely many nodes with f(n) ≤ C*. Tree search is optimal with an admissible heuristic; graph search needs a consistent one. Optimally efficient: no other tree-based algorithm with the same heuristic expands fewer nodes and is still guaranteed to find the optimal solution. Lecture reference: Informed Search · slide 29 Lecture reference: Informed Search · slide 30 Lecture reference: Informed Search · slide 31 Lecture reference: Informed Search · slide 42

b: maximum branching factor of the search tree
d: depth of the optimal solution
m: maximum length of any path in the state space (may be infinite)
C*: cost of the optimal solution
g(n): cost of the path from the start state to node n

Lecture reference: Uninformed Search · slide 45 Lecture reference: Informed Search · slide 42

Problem Romania: Arad to Bucharest

Tree search from Arad to Bucharest with the straight-line distance. DFS goes Arad, Sibiu, Arad, Sibiu, … until the limit stops it. UCS and A* return the route through Rimnicu Vilcea and Pitesti (418); BFS, IDS, greedy, and weighted A* the route through Fagaras (450).

Informed Search · slides 8–22

Start: Arad
Goal: Bucharest
h(n): Straight-line distance to Bucharest
b: 4 (most successors of any state)
Cheapest: Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest (cost 418, d = 4)

Highlight

Graph text

Edit the graph in the search tool

Settings

Repeated states

Tree search Path check Graph search

Every child goes on the frontier; states can repeat. Lecture reference: Solving Problems by Searching · slide 28

Weighted A* α

Expansion limit

A run stops after taking 1,000 nodes off the frontier or generating 50,000 nodes. IDS tries depth limits 0 to 50. Successors in name order; the goal test runs when a node is taken off the frontier.

Nodes generated

Generated Expanded Max frontier

BFS 40
DFS 3,501 stopped at the limit
IDS 30
UCS 132
Greedy 10
A* 16
Weighted A* 10

Outlined bars: no solution returned. Bars are scaled to the runs that found a solution; a gap near the end marks a bar cut short.

Results tree search · Romania: Arad to Bucharest

Strategy	Path	Cost	Cheapest?	Taken off the frontier	Expanded	Generated	Max frontier	Outcome
BFS Step throughBFS in the search tool	Arad → Sibiu → Fagaras → Bucharest	450	No, +32	16	15	40	25	Found Returned a solution.
Expansion orderof BFS Arad, Sibiu, Timisoara, Zerind, Arad, Fagaras, Oradea, Rimnicu Vilcea, Arad, Lugoj, Arad, Oradea, Sibiu, Timisoara, Zerind, Bucharest
DFS Step throughDFS in the search tool	–	–	–	1,000	1,000	3,501	2,501	Stopped at the limit Stopped after taking 1,000 nodes off the frontier.
Expansion orderof DFS Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu, Arad, Sibiu
IDS Step throughIDS in the search tool	Arad → Sibiu → Fagaras → Bucharest	450	No, +32	25	9	30	8	Found Returned a solution.
Expansion orderof IDS Arad \| Arad, Sibiu, Timisoara, Zerind \| Arad, Sibiu, Arad, Fagaras, Oradea, Rimnicu Vilcea, Timisoara, Arad, Lugoj, Zerind, Arad, Oradea \| Arad, Sibiu, Arad
UCS Step throughUCS in the search tool	Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest	418 lowest	Yes	53	52	132	80	Found Returned a solution.
Expansion orderof UCS Arad, Zerind, Timisoara, Sibiu, Oradea, Arad, Zerind, Rimnicu Vilcea, Zerind, Lugoj, Arad, Fagaras, Timisoara, Arad, Oradea, Sibiu, Oradea, Arad, Oradea, Sibiu
Greedy Step throughGreedy in the search tool	Arad → Sibiu → Fagaras → Bucharest	450	No, +32	4	3 fewest	10	7	Found Returned a solution.
Expansion orderof Greedy Arad, Sibiu, Fagaras, Bucharest
A* Step throughA* in the search tool	Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest	418 lowest	Yes	6	5	16	11	Found Returned a solution.
Expansion orderof A* Arad, Sibiu, Rimnicu Vilcea, Fagaras, Pitesti, Bucharest
Weighted A* α = 2 Step throughWeighted A* in the search tool	Arad → Sibiu → Fagaras → Bucharest	450	No, +32	4	3 fewest	10	7	Found Returned a solution.
Expansion orderof Weighted A* Arad, Sibiu, Fagaras, Bucharest

Cheapest? compares each path with the cheapest path in the graph. Generated counts the root and children that were not added; max frontier is the largest frontier size.

Node counts

Branching factor b

Solution depth d

Longest path m

Optimal cost C*

Least step cost ε

Time nodes generated

BFS O(bᵈ)

Nodes in a b-ary tree of depth d Lecture reference: Uninformed Search · slide 31

1 + b + b² + … + bᵈ

= 1 + 10 + 10² + 10³ + 10⁴ + 10⁵

= 1 + 10 + 100 + 1,000 + 10,000 + 100,000

= 111,111

IDS O(bᵈ)

Level i is generated again in each of the d + 1 − i iterations that reach it Lecture reference: Uninformed Search · slide 38

(d+1)b⁰ + d b¹ + (d−1)b² + … + bᵈ

= 6·10⁰ + 5·10¹ + 4·10² + 3·10³ + 2·10⁴ + 10⁵

= 6 + 50 + 400 + 3,000 + 20,000 + 100,000

= 123,456

IDS / BFS = 1.11: 11% more nodes than BFS.

DFS O(bᵐ)

A solution at the maximum depth m: every node of a b-ary tree of depth m Lecture reference: Uninformed Search · slide 32

1 + b + b² + … + bᵐ

= 1 + 10 + 10² + … + 10⁹ + 10¹⁰

= 1 + 10 + 100 + … + 1,000,000,000 + 10,000,000,000

= 11,111,111,111

UCS O(b^C*/ε)

Nodes with g(n) ≤ C* lie at depth k = ⌊C*/ε⌋ = 10 or less. Lecture reference: Uninformed Search · slide 44

1 + b + b² + … + bᵏ

= 1 + 10 + 10² + … + 10⁹ + 10¹⁰

= 1 + 10 + 100 + … + 1,000,000,000 + 10,000,000,000

= 11,111,111,111

k = 10 > d = 5: up to 100,000 times the BFS count.

Space nodes in memory

Algorithm	Space	Nodes
BFS	O(bᵈ) bᵈ	100,000
IDS	O(bd) b·d + 1	51
DFS	O(bm) b·m + 1	101
UCS	O(b^C*/ε) bᵏ	10,000,000,000

BFS keeps the whole last level on the frontier; DFS keeps the unexpanded siblings of each node on its path (b per level) plus the root; IDS is DFS with depth limit d.

A note on the complexity of search

The worst-case complexity of search is exponential in the length of the solution path, and the length of the solution path can be exponential in the number of “objects” in the problem. Example: towers of Hanoi. Lecture reference: Informed Search · slide 43

Disks n

Moves in the shortest solution: 2ⁿ − 1 = 2⁵ − 1 = 31
Search cost at that depth: O(bᵈ) with b = 3, d = 31: 3³¹ = 617,673,396,283,947 (15 digits)

b = 3: in any state the smallest disk can move to either other peg, and one move is possible between the two remaining pegs.

Typical search costs for the 8-puzzle

Average number of nodes expanded for different solution depths.

Algorithm	d = 12	d = 24
IDS	3,644,035	≈ 54,000,000,000
A*(h1)	227	39,135
A*(h2)	73	1,641