Heuristics

Checks a heuristic on a graph problem: h(n) against the true cost h*(n), every edge for consistency, dominance and the maximum of two heuristics, and the paths A* tree search, A* graph search, and weighted A* return with it.

Lecture reference: Informed Search · slides 25–30
Lecture reference: Informed Search · slides 35–38

Problem 20 states · 23 edges

Start

Goal

h(n): Straight-line distance to Bucharest
C*: 418 · Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest

Romania: straight-line distance. Arad to Bucharest with the straight-line distance to Bucharest as h. A straight line is never longer than the road, so h never overestimates; it is also consistent. A* tree and graph search both return Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest (418).

Informed Search · slide 6

Edit graph

Admissibility and consistency

Admissible

Yes

h(n) ≤ h*(n) at all 20 states.

An admissible heuristic never overestimates the cost to reach the goal: h(n) ≤ h*(n) for every node n, where h*(n) is the true cost to reach the goal state from n. Theorem: if h(n) is admissible, A* is optimal.
Lecture reference: Informed Search · slide 25

Proof sketch

Consistent

Yes

h(n) ≤ c(n, n') + h(n') on all 46 edge directions.

cost(A to C) + h(C) ≥ h(A) for every edge, i.e. cost(A to C) ≥ h(A) − h(C): the real cost is at least the cost implied by the heuristic. Consistency is stronger than admissibility. Consequences: the f value along a path never decreases, and A* graph search is optimal.
Lecture reference: Informed Search · slide 28

Optimality of A*
A*	Optimal if h is	This h	Returned
Tree search no repeated-state detection	Optimal if h is admissible (and non-negative)	This h: yes	Returned 418 = C*
Graph search repeated-state detection	Optimal if h is consistent	This h: yes	Returned 418 = C*

Consistency implies admissibility. In general, most natural admissible heuristics tend to be consistent, especially if they come from relaxed problems. Lecture reference: Informed Search · slide 29

h(n) and h*(n) one row per state

h(n), the true cost h*(n), and their difference for every state
State	h(n)	h*(n)	h*(n) − h(n)
start	h(Arad)	418 h(n) ≤ h*(n): 52	h(n) ≤ h*(n): 52
goal	h(Bucharest)	0 h(n) ≤ h*(n): 0	h(n) ≤ h*(n): 0
	h(Craiova)	239 h(n) ≤ h*(n): 79	h(n) ≤ h*(n): 79
	h(Dobreta)	359 h(n) ≤ h*(n): 117	h(n) ≤ h*(n): 117
	h(Eforie)	269 h(n) ≤ h*(n): 108	h(n) ≤ h*(n): 108
	h(Fagaras)	211 h(n) ≤ h*(n): 35	h(n) ≤ h*(n): 35
	h(Giurgiu)	90 h(n) ≤ h*(n): 13	h(n) ≤ h*(n): 13
	h(Hirsova)	183 h(n) ≤ h*(n): 32	h(n) ≤ h*(n): 32
	h(Iasi)	319 h(n) ≤ h*(n): 93	h(n) ≤ h*(n): 93
	h(Lugoj)	504 h(n) ≤ h*(n): 260	h(n) ≤ h*(n): 260
	h(Mehadia)	434 h(n) ≤ h*(n): 193	h(n) ≤ h*(n): 193
	h(Neamt)	406 h(n) ≤ h*(n): 172	h(n) ≤ h*(n): 172
	h(Oradea)	429 h(n) ≤ h*(n): 49	h(n) ≤ h*(n): 49
	h(Pitesti)	101 h(n) ≤ h*(n): 1	h(n) ≤ h*(n): 1
	h(Rimnicu Vilcea)	198 h(n) ≤ h*(n): 5	h(n) ≤ h*(n): 5
	h(Sibiu)	278 h(n) ≤ h*(n): 25	h(n) ≤ h*(n): 25
	h(Timisoara)	536 h(n) ≤ h*(n): 207	h(n) ≤ h*(n): 207
	h(Urziceni)	85 h(n) ≤ h*(n): 5	h(n) ≤ h*(n): 5
	h(Vaslui)	227 h(n) ≤ h*(n): 28	h(n) ≤ h*(n): 28
	h(Zerind)	493 h(n) ≤ h*(n): 119	h(n) ≤ h*(n): 119

Admissible yes
Consistent yes
A* tree 418 = C*
A* graph 418 = C*

State space with h(n)

Goal state
Cheapest path (C* = 418)
h(n)

Click a state to select its row.

Consistency h(n) ≤ c(n, n') + h(n') on every edge direction

All 46 Failed 0 Selected state

Consistency check per edge direction, failed checks first
n → n'	c(n, n')	h(n)	h(n')	h(n) − h(n')	c ≥ h(n) − h(n')
→	75	366	374	−8	holds
→	75	374	366	8	holds
→	140	366	253	113	holds
→	140	253	366	−113	holds
→	118	366	329	37	holds
→	118	329	366	−37	holds
→	71	374	380	−6	holds
→	71	380	374	6	holds
→	151	380	253	127	holds
→	151	253	380	−127	holds
→	111	329	244	85	holds
→	111	244	329	−85	holds
→	70	244	241	3	holds
→	70	241	244	−3	holds
→	75	241	242	−1	holds
→	75	242	241	1	holds
→	120	242	160	82	holds
→	120	160	242	−82	holds
→	99	253	176	77	holds
→	99	176	253	−77	holds
→	80	253	193	60	holds
→	80	193	253	−60	holds
→	97	193	100	93	holds
→	97	100	193	−93	holds
→	146	193	160	33	holds
→	146	160	193	−33	holds
→	138	160	100	60	holds
→	138	100	160	−60	holds
→	211	176	0	176	holds
→	211	0	176	−176	holds
→	101	100	0	100	holds
→	101	0	100	−100	holds
→	90	0	77	−77	holds
→	90	77	0	77	holds
→	85	0	80	−80	holds
→	85	80	0	80	holds
→	98	80	151	−71	holds
→	98	151	80	71	holds
→	86	151	161	−10	holds
→	86	161	151	10	holds
→	142	80	199	−119	holds
→	142	199	80	119	holds
→	92	199	226	−27	holds
→	92	226	199	27	holds
→	87	226	234	−8	holds
→	87	234	226	8	holds

A* with this h

Tree search

no repeated-state detection

Cost 418 Optimal

Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest

Expanded: 5
Generated: 16

Step through it in the search tool

Graph search

explored set and frontier check

Cost 418 Optimal

Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest

Expanded: 5
Generated: 16

Step through it in the search tool

Nodes taken off the frontier by A* tree search, by f(n) = g(n) + h(n)

f(n) < C* 5: Arad 366 (g = 0, h = 366)
Sibiu 393 (g = 140, h = 253)
Rimnicu Vilcea 413 (g = 220, h = 193)
Fagaras 415 (g = 239, h = 176)
Pitesti 417 (g = 317, h = 100)
f(n) = C* 1: Bucharest 418 (g = 418, h = 0)
f(n) > C* 0: none

A* is optimally efficient: no other tree-based algorithm that uses the same heuristic can expand fewer nodes and still be guaranteed to find the optimal solution. A* expands all nodes for which f(n) ≤ C*.
Lecture reference: Informed Search · slide 30

A* gone wrong?

Informed Search · slide 27

Show answer

Dominance and combining

h1(n) ≥ h2(n) for all n and both are admissible: h1 dominates h2.

h1 admissible
h2 admissible
max admissible

A* tree search with each heuristic
Heuristic	Expanded	Cost
h1 Straight-line distance to Bucharest	5	418
h2 h = 0	52	418
max{h1, h2} the larger value at each state	5	418

h1, h2 and max{h1, h2} for every state
State	h1(n)	h1 against h2	max
Arad	366 (larger)	>	366
Bucharest	0	=	0
Craiova	160 (larger)	>	160
Dobreta	242 (larger)	>	242
Eforie	161 (larger)	>	161
Fagaras	176 (larger)	>	176
Giurgiu	77 (larger)	>	77
Hirsova	151 (larger)	>	151
Iasi	226 (larger)	>	226
Lugoj	244 (larger)	>	244
Mehadia	241 (larger)	>	241
Neamt	234 (larger)	>	234
Oradea	380 (larger)	>	380
Pitesti	100 (larger)	>	100
Rimnicu Vilcea	193 (larger)	>	193
Sibiu	253 (larger)	>	253
Timisoara	329 (larger)	>	329
Urziceni	80 (larger)	>	80
Vaslui	199 (larger)	>	199
Zerind	374 (larger)	>	374

If h1 and h2 are both admissible and h2(n) ≥ h1(n) for all n, then h2 dominates h1. A* search expands every node with f(n) < C*, or h(n) < C* − g(n); therefore A* search with h1 will expand more nodes.
Lecture reference: Informed Search · slide 35

With a collection of admissible heuristics h1(n), …, hm(n), none of which dominates the others: h(n) = max{h1(n), …, hm(n)}.
Lecture reference: Informed Search · slide 37

The 8-puzzle’s h1 (misplaced tiles) and h2 (Manhattan distance) are compared in the 8-puzzle tool. Open the slide 32 board

Weighted A*

f(n) = g(n) + 2·h(n)

Weighted A*	Cost	Expanded	A* expanded
Tree search	450	3	5
Graph search	450	3	5

C* = 418, α · C* = 2 × 418 = 836. Tree: within α · C*Graph: within α · C*

h is admissible and consistent, so the slide’s bound applies to both searches: the solution costs at most α · C*.

Take an admissible heuristic, “inflate” it by a multiple α > 1, and then perform A* search as usual. Fewer nodes tend to get expanded, but the resulting solution may be suboptimal (its cost will be at most α times the cost of the optimal solution).
Lecture reference: Informed Search · slide 38