Informed Search: Exercises and Homework - Artificial Intelligence

Midterm preparation for Informed Search, Local Search & Genetic Algorithms.

Part A: Concept Check (True / False)¶

State whether each claim is true or false and justify it in one sentence.

A* with an admissible heuristic always returns an optimal solution when it terminates by selecting the goal for expansion.
Greedy best-first search is optimal whenever $h$ is admissible.
With $h(n)=0$ for all $n$ , A* behaves exactly like Uniform-Cost Search.
Every consistent heuristic is admissible, and every admissible heuristic is consistent.
A* may stop as soon as the goal is generated (added to the frontier) and still be optimal.
If $h_1$ and $h_2$ are both admissible, then $h_1 + h_2$ is admissible.
If $h_1$ and $h_2$ are admissible and $h_2(n)\ge h_1(n)$ for all $n$ , A* with $h_2$ never expands more nodes than with $h_1$ (ignoring ties).
Hill climbing is complete: it always finds the global optimum if one exists.
Simulated annealing with a very high temperature behaves like a random walk; with $T\to 0$ it behaves like hill climbing.
Tabu search can accept a move that makes the current solution worse.
Single-point crossover is a valid operator for permutation chromosomes.
Larger tournament size $k$ means higher selection pressure.
Mutation is the GA’s main exploitation operator.
Roulette-wheel selection can be applied directly to fitness values that may be negative.

Solution

True. Admissibility guarantees that no cheaper path remains on the frontier when the goal is selected. (For graph search without re-opening nodes, consistency is needed.)
False. Greedy ignores $g(n)$ , so it can follow a cheap-looking but expensive path.
True. $f(n)=g(n)$ .
False. Consistent $\Rightarrow$ admissible, but not the converse.
False. A cheaper path to the goal may still be on the frontier. Stop only when the goal is selected for expansion.
False. The sum can overestimate. Example: if $h^*(n)=5$ and $h_1(n)=h_2(n)=4$ , then $h_1+h_2=8>5$ . $\max(h_1,h_2)$ is admissible.
True. $h_2$ dominates $h_1$ and is therefore at least as informed.
False. It gets stuck on local optima, plateaus and ridges.
True. At high $T$ , $e^{-\Delta L/T}\to 1$ so almost every move is accepted. At $T\to0$ , worse moves are never accepted.
True. It moves to the best non-tabu neighbour even if it is worse than the current state.
False. Swapping tails produces duplicated or missing symbols, which is an invalid permutation. Use OX1, PMX or CX.
True. The best individual wins more of the tournaments.
False. Crossover exploits existing building blocks. Mutation is the exploration operator.
False. Probabilities $f_i/\sum f$ would be negative or meaningless. Shift or scale the fitness, or use rank-based selection.

Part B: Tracing Greedy, UCS and A*¶

Exercise B1¶

Consider the directed graph below. Start node is S, goal node is G. The edge labels are step costs and the heuristic value $h$ is written in each node.

Compute the true cost-to-goal $h^*(n)$ for every node. Is $h$ admissible? Is it consistent?
Run Greedy Best-First Search. Give the order of expansion, the path found and its cost.
Run Uniform-Cost Search. Give the order of expansion, the path found and its cost.
Run A*. Give the order of expansion (with the $f$ value of each expanded node), the path found and its cost.
Which algorithm expanded the fewest nodes? Which returned a non-optimal path? Explain why.

Solution

1. True costs. $h^*(G)=0,\ h^*(D)=3,\ h^*(C)=8,\ h^*(B)=\min(1+3,\,9)=4,\ h^*(A)=\min(2+8,\,5+3)=8,\ h^*(S)=\min(1+8,\,4+4)=8$ .

Node	S	A	B	C	D	G
$h$	7	6	4	7	3	0
$h^*$	8	8	4	8	3	0

$h\le h^*$ everywhere, so $h$ is admissible. Consistency, $h(n)\le c(n,n')+h(n')$ : S→A: $7\le 1+6$ ; S→B: $7\le 4+4$ ; A→C: $6\le 2+7$ ; A→D: $6\le 5+3$ ; B→D: $4\le 1+3$ ; B→G: $4\le 9$ ; C→G: $7\le 8$ ; D→G: $3\le 3$ . All hold, so $h$ is consistent.

2. Greedy (order by $h$ ). Expand S (A:6, B:4) → B (D:3, G:0) → G (h=0). Order: S, B, G. Path S→B→G, cost $4+9=\mathbf{13}$ (not optimal).

3. UCS (order by $g$ ). S(0) → A(1) → C(3) → B(4) → D(5, via B) → G(8, via D). Order: S, A, C, B, D, G (6 nodes). Path S→B→D→G, cost 8.

4. A* ( $f=g+h$ ).

Step	Expanded	$g$	$f$	Frontier after expansion
1	S	0	7	A(1+6=7), B(4+4=8)
2	A	1	7	B(8), D(6+3=9), C(3+7=10)
3	B	4	8	D(5+3=8, replaces 9), C(10), G(13)
4	D	5	8	G(8+0=8, replaces 13), C(10)
5	G	8	8	goal selected, stop

Order: S, A, B, D, G (5 nodes). Path S→B→D→G, cost 8 (optimal).

5. Greedy expanded the fewest nodes (3) but returned cost 13 because it ignores the cost already paid ( $g$ ). UCS and A* are optimal, and A* used 5 expansions versus 6 for UCS because $h$ pruned node C.

Exercise B2¶

Use the same graph as in B1 but with this different heuristic: $h(S)=7,\ h(A)=6,\ h(B)=1,\ h(C)=7,\ h(D)=3,\ h(G)=0$ .

Is the new heuristic admissible? Is it consistent?
Run A*. What path does it return and what is its cost? Explain what changed compared to B1.

Solution

$h(B)=1\le h^*(B)=4$ and the others are unchanged, so it is admissible. It is not consistent: S→B requires $7\le 4+1=5$ , which fails.
$f$ : S=7. Expand S: A(1+6=7), B(4+1=5). Expand B(5): D(5+3=8), G(13). Expand A(7): C(10), D(6+3=9, not better than 8). Expand D(8): G(8). Expand G. Path S→B→D→G, cost 8, still optimal because the heuristic is admissible. The difference: B is now expanded before A, and the $f$ values along the path are no longer non-decreasing (S: 7, B: 5, D: 8), which is the signature of an inconsistent heuristic.

Part C: Heuristics¶

Exercise C1: Admissible or consistent?¶

Directed graph with start S and goal G:

For each heuristic below, decide whether it is admissible, consistent, both, or neither. Justify with the relevant inequality.

Node	S	A	B	C	G
$h_a$	5	4	3	2	0
$h_b$	6	5	1	3	0
$h_c$	6	7	4	3	0
$h_d$	0	0	0	0	0
$h_e$	6	5	4	3	1

Solution

True costs: $h^*(G)=0,\ h^*(C)=3,\ h^*(B)=\min(1+3,6)=4,\ h^*(A)=2+3=5,\ h^*(S)=\min(1+5,\,2+4)=6$ .

$h_a$ : admissible ( $5\le6,\ 4\le5,\ 3\le4,\ 2\le3$ ). Consistent: S→A $5\le1+4$ , S→B $5\le2+3$ , A→C $4\le2+2$ , B→C $3\le1+2$ , B→G $3\le6$ , C→G $2\le3$ . Both.
$h_b$ : admissible ( $6\le6,\ 5\le5,\ 1\le4,\ 3\le3$ ). S→B: $6\le 2+1=3$ fails. Admissible, not consistent.
$h_c$ : $h_c(A)=7>h^*(A)=5$ . Not admissible (hence not consistent either).
$h_d$ : always $0\le h^*$ and $0\le c+0$ . Both (this is UCS).
$h_e$ : $h_e(G)=1>0=h^*(G)$ . Not admissible. A heuristic must be 0 at the goal.

Exercise C2: Combining heuristics¶

$h_1$ and $h_2$ are admissible. For each of the following, state whether it is always admissible (give a proof) or not necessarily (give a counter-example).

$\max(h_1,h_2)$
$\min(h_1,h_2)$
$\tfrac12(h_1+h_2)$
$h_1+h_2$
$2\,h_1$

Solution

Admissible. $\max(h_1,h_2)\le h^*$ because both are $\le h^*$ . It is also at least as informed as each of them.
Admissible. $\min(h_1,h_2)\le h_1\le h^*$ .
Admissible. The average of two values $\le h^*$ is $\le h^*$ .
Not necessarily. If $h^*(n)=5$ and $h_1(n)=h_2(n)=4$ , then $h_1+h_2=8>5$ .
Not necessarily. Same counter-example: $2\cdot4=8>5$ .

Exercise C3: 8-Puzzle heuristics¶

Initial state (left) and goal (right); _ is the blank.

Initial:        Goal:
2 8 3           1 2 3
1 6 4           8 _ 4
7 _ 5           7 6 5

Compute $h_1$ (number of misplaced tiles, blank excluded) and $h_2$ (sum of Manhattan distances) for the initial state.
The blank can move up, left or right. For each of the three successors compute $g$ , $h_2$ and $f=g+h_2$ . Which one does A* expand next?
Which relaxation of the puzzle rules yields $h_1$ ? Which yields $h_2$ ?
Does $h_2$ dominate $h_1$ ? What does it imply for the number of nodes expanded?

Solution

1. Misplaced: tiles 2, 8, 1, 6, so $h_1=4$ . Manhattan: tile 2 → 1, tile 8 → 2, tile 1 → 1, tile 6 → 1, so $h_2=5$ .

Move blank	Resulting state (rows)	$g$	$h_2$	$f$
up	`2 8 3 / 1 _ 4 / 7 6 5`	1	4 (2:1, 8:2, 1:1)	5
left	`2 8 3 / 1 6 4 / _ 7 5`	1	6	7
right	`2 8 3 / 1 6 4 / 7 5 _`	1	6	7

A* expands the blank-up successor (lowest $f=5$ ).

3. Rule: “a tile can move from A to B if A is adjacent to B and B is blank.”

Drop B is blank (tiles may move to any adjacent square): $h_2$ (Manhattan).
Drop both conditions (tiles jump anywhere): $h_1$ (misplaced tiles).

4. Yes: every tile contributes at least 1 to $h_2$ whenever it contributes 1 to $h_1$ , so $h_2(n)\ge h_1(n)$ and both are admissible. A* with $h_2$ never expands more nodes than with $h_1$ (ignoring ties).

Exercise C4: Grid path planning¶

A robot moves in four directions (up/down/left/right), each move costs 1. # is a wall. Start S = (r0,c0), goal G = (r3,c4).

     c0 c1 c2 c3 c4
r0 :  S  .  .  #  .
r1 :  .  #  .  .  .
r2 :  .  #  #  .  #
r3 :  .  .  .  .  G

Compute $h(S)$ using the Manhattan distance to G.
Is Manhattan distance admissible and consistent on this grid? Why?
What is the true shortest path length? How many shortest paths exist?
Using $g$ = true shortest distance from S, which free cells have $f=g+h>7$ ? What does that tell you about A*?

Solution

$h(S)=|3-0|+|4-0|=7$ .
Both. Each move changes the Manhattan distance by exactly 1 and costs 1, so $h(n)\le 1+h(n')$ . Walls can only make the real cost larger.
The shortest length is 7. There are 2 shortest paths: down the left column then right along row 3 (S, r1c0, r2c0, r3c0, r3c1, r3c2, r3c3, G), or right along row 0 to c2, down to (r1,c2), right to (r1,c3), down through (r2,c3) and (r3,c3), then right to G.
Only (r0,c4) has $f>7$ : $g=6$ (via (r1,c4) with $g=5$ ), $h=3$ , so $f=9$ . Every other free cell has $f=7$ . A* never needs to expand cells with $f>C^*=7$ , so (r0,c4) is never expanded. Because the heuristic is perfect along the shortest paths, the cells expanded all have $f=C^*=7$ .

Exercise C5: Effective branching factor¶

A* solves a problem at depth $d=5$ and generates $N=52$ nodes. The effective branching factor $b^*$ is the branching factor of a uniform tree of depth $d$ that contains $N+1$ nodes:

N+1 = 1 + b^* + (b^*)^2 + \dots + (b^*)^d

(1)

Estimate $b^*$ to two decimals. What does a $b^*$ close to 1 say about the heuristic?

Solution

Solve $53=\dfrac{(b^*)^6-1}{b^*-1}$ . Trying values: $b^*=1.9\Rightarrow 51.2$ , $b^*=1.92\Rightarrow 53.4$ , $b^*=1.915\Rightarrow 52.8$ . So $b^*\approx\mathbf{1.92}$ .

A $b^*$ close to 1 means the heuristic is very accurate (the search is nearly a straight line to the goal). A $b^*$ equal to the real branching factor means the heuristic is useless.

Part D: Local Search¶

Exercise D1: Hill climbing on 4-Queens¶

A state is a list of rows, one queen per column (rows and columns numbered 1 to 4). The loss $L$ is the number of attacking pairs. A move relocates one queen inside its column. Use steepest descent: move to the best neighbour and stop if no neighbour has a strictly lower loss.

Initial state: $(2,3,2,4)$ .

Compute $L$ of the initial state.
Compute $L$ for all 12 neighbours. Which neighbour is chosen?
Continue until the algorithm stops. What is the final state and its loss? Is it a solution?
What simple modifications would let the search finish? Apply one and show the solution.

Solution

1. Attacking pairs of $(2,3,2,4)$ : (col1, col2) diagonal, (col1, col3) same row, (col2, col3) diagonal. $L=3$ .

2. Neighbour losses (new row for the moved queen):

Moved column	New row	Resulting state	$L$
1	1	(1,3,2,4)	2
1	3	(3,3,2,4)	2
1	4	(4,3,2,4)	4
2	1	(2,1,2,4)	3
2	2	(2,2,2,4)	4
2	4	(2,4,2,4)	2
3	1	(2,3,1,4)	1
3	3	(2,3,3,4)	3
3	4	(2,3,4,4)	4
4	1	(2,3,2,1)	5
4	2	(2,3,2,2)	5
4	3	(2,3,2,3)	5

The best neighbour is $(2,3,1,4)$ with $L=1$ .

3. From $(2,3,1,4)$ the only attacking pair is (col1, col2) (diagonal). None of its neighbours has $L=0$ . The two solutions $(2,4,1,3)$ and $(3,1,4,2)$ differ from it in 2 and 4 columns, so none is a single move away. Neighbours with $L=1$ exist, for example $(2,4,1,4)$ , but they are not strictly better, so the algorithm stops at $(2,3,1,4)$ , $L=1$ : a local minimum, not a solution.

4. Options: sideways moves, random restart, simulated annealing. With a sideways move $(2,3,1,4)\to(2,4,1,4)$ (still $L=1$ ), moving queen 4 to row 3 gives $(2,4,1,3)$ with $L=0$ , which is a solution.

Exercise D2: Hill climbing on a small TSP¶

Distances (symmetric) between five cities:

	A	B	C	D	E
A	0	2	9	10	7
B	2	0	6	4	8
C	9	6	0	8	5
D	10	4	8	0	3
E	7	8	5	3	0

A tour starts and ends at A. Neighbourhood: swap two of the four non-A cities in the tour. Starting from A→C→B→D→E→A:

Compute the tour length.
Evaluate the six neighbours and run steepest-descent hill climbing until it stops.
Is the final tour a local or global optimum? How do you know?

Solution

1. $9+6+4+3+7=\mathbf{29}$ .

2. Neighbours of A C B D E:

Swap	Tour	Length
C↔B	A B C D E	26
C↔D	A D B C E	32
C↔E	A E B D C	36
B↔D	A C D B E	36
B↔E	A C E D B	23
D↔E	A C B E D	36

Move to A C E D B (23). Its neighbours: A E C D B (26), A D E C B (26), A B E D C (30), A C D E B (30), A C B D E (29), A C E B D (36). All are $\ge23$ , so the algorithm stops.

3. The final tour has length 23. There are only $4!/2=12$ distinct tours here, so brute force confirms 23 is also the global optimum (A C E D B is the reverse of A B D E C, with the same length). In general, hill climbing gives only a local optimum.

Exercise D3: Simulated annealing¶

Compute $P(\text{accept})=e^{-\Delta L/T}$ for $\Delta L=4$ with $T=8$ , $T=2$ and $T=0.5$ .
With $T=5$ , decide for each move whether SA accepts it. Draw $r\sim U(0,1)$ given in the table.

Move	$\Delta L$	$r$
1	+3	0.40
2	+10	0.20
3	−2	0.95
4	+5	0.35

The schedule is exponential, $T(t)=T_0\gamma^t$ with $T_0=100$ and $\gamma=0.9$ . What is $T$ after 10 iterations? After how many iterations does $T$ first drop below 1?
Explain why SA must remember the best state ever seen.

Solution

1. $e^{-0.5}\approx0.607$ ; $e^{-2}\approx0.135$ ; $e^{-8}\approx3.4\times10^{-4}$ .

Move	$\Delta L$	$r$	$P$	Accepted?
1	+3	0.40	$e^{-0.6}=0.549$	Yes ( $0.40<0.549$ )
2	+10	0.20	$e^{-2}=0.135$	No ( $0.20>0.135$ )
3	−2	0.95	1	Yes (improvement)
4	+5	0.35	$e^{-1}=0.368$	Yes ( $0.35<0.368$ )

3. $T(10)=100\cdot0.9^{10}\approx34.9$ . We need $0.9^t<0.01$ , so $t>\ln(0.01)/\ln(0.9)\approx43.7$ , i.e. $t=\mathbf{44}$ .

4. Because worse moves are accepted, the current state at the end of the run may be worse than a state visited earlier.

Exercise D4: Tabu search¶

States $0,\dots,7$ lie on a line. A move goes to state $i\pm1$ . The loss is:

State	0	1	2	3	4	5	6	7
$L$	6	4	3	5	7	4	1	2

Start in state 1.

Run hill climbing. Where does it stop?
Run tabu search where the tabu list holds the last $k=2$ visited states (including the current one). At each step move to the best non-tabu neighbour, even if it is worse. Give the sequence of states and tabu list until the global minimum is found.
What happens with $k=1$ ?

Solution

1. 1 (L=4) → 2 (L=3). Neighbours of 2 are 1 (4) and 3 (5), both worse. Stops at state 2, $L=3$ , a local minimum. The global minimum is state 6 ( $L=1$ ).

2. $k=2$ :

Iteration	Current	Tabu list	Candidates	Move to
0	1	[1]	0 (6), 2 (3)	2
1	2	[1, 2]	3 (5) (1 is tabu)	3
2	3	[2, 3]	4 (7) (2 is tabu)	4
3	4	[3, 4]	5 (4) (3 is tabu)	5
4	5	[4, 5]	6 (1) (4 is tabu)	6

Tabu search climbs over the barrier at states 3–4 and reaches the global minimum 6 ( $L=1$ ) at iteration 5.

3. With $k=1$ only the current state is tabu. From 2 the search goes back to 1 (L=4), then to 2, and so on forever. It cycles between 1 and 2 and never escapes. The tabu list must be long enough to prevent short cycles.

Part E: Genetic Algorithms¶

Exercise E1: Roulette-wheel selection¶

Maximise $f(x)=x^2$ over 5-bit integers. The population is:

Chromosome	A: `00110`	B: `10100`	C: `01011`	D: `11001`

Decode each chromosome and compute its fitness.
Compute the selection probability, cumulative probability and expected count $N\cdot P_i$ ( $N=4$ ).
Spins of the wheel give $r=0.45,\ 0.02,\ 0.90,\ 0.36$ . Which chromosomes enter the mating pool?
Why is rank-based selection preferable if one chromosome had fitness 10000 and the others about 10?

Solution

1–2.

	$x$	$f=x^2$	$P_i$	Cumulative	$N\cdot P_i$
A	6	36	0.030	0.030	0.12
B	20	400	0.338	0.369	1.35
C	11	121	0.102	0.471	0.41
D	25	625	0.529	1.000	2.12
Sum		1182	1		4

3. $r=0.45\to$ first cumulative value $\ge0.45$ is 0.471, so C. $r=0.02\to$ A. $r=0.90\to$ D. $r=0.36\to$ 0.369, so B. Mating pool: {C, A, D, B}.

4. The dominant chromosome would occupy almost the whole wheel and the population would converge prematurely. Rank-based selection depends only on the order, not on the magnitude of the fitness values.

Exercise E2: Crossover on bit strings¶

Parents: P1 = 11010011 and P2 = 00101100. Give both children for:

Single-point crossover after bit 3.
Two-point crossover with cuts after bit 2 and after bit 5.
Uniform crossover with mask 10110010 (1 = take from $P_1$ , 0 = take from $P_2$ for child 1; child 2 takes the opposite parent).

Solution

110|10011 and 001|01100 → child 1 = 11001100, child 2 = 00110011.
11|010|011 and 00|101|100 → child 1 = 11101011, child 2 = 00010100.
Child 1 takes P1 at positions 1, 3, 4, 7 and P2 at 2, 5, 6, 8: 10011110. Child 2 is the complement choice: 01100001.

Exercise E3: Permutation operators¶

Show with $P_1=[1,2,3,4,5]$ and $P_2=[3,5,1,4,2]$ that single-point crossover after position 2 gives an invalid child.
Apply order crossover (OX1) with $P_1=[1,2,3,4,5,6,7,8]$ and $P_2=[4,6,8,1,3,5,7,2]$ . Copy the slice at positions 3 to 5 of $P_1$ , then fill the remaining empty positions from left to right with the missing cities in the order they appear in $P_2$ .
Apply to $[3,1,4,2,5]$ : (a) swap mutation of positions 2 and 5, (b) inversion mutation of positions 2 to 4, (c) insertion mutation moving the gene at position 5 to position 2.
Why is inversion mutation a good choice for TSP?

Solution

Child = $[1,2\,|\,1,4,2]$ : cities 1 and 2 appear twice, and cities 3 and 5 are missing. Invalid.
The slice is 3 4 5, so the child is _ _ 3 4 5 _ _ _. Remaining cities in $P_2$ order (skipping 3, 4, 5): 6 8 1 7 2. Child = [6,8,3,4,5,1,7,2].
(a) $[3,5,4,2,1]$ . (b) reverse $[1,4,2]$ to get $[3,2,4,1,5]$ . (c) $[3,5,1,4,2]$ .
Inversion reverses a segment of the tour (a 2-opt move). It changes only 2 edges of the tour, so it is a gentle perturbation, whereas a swap can change up to 4 edges.

Exercise E4: One generation by hand¶

Maximise the number of ones (OneMax) over 6 bits. Population:

A: `110100`	B: `111011`	C: `000100`	D: `101010`

Compute the fitness of each chromosome and the population average.
Selection gave the mating pool {B, A, B, D}. Pair them as (B, A) and (B, D), and apply single-point crossover after bit 3 to each pair. Write all four children.
Mutation (bit flip): flip bit 4 of the last child. Write the new population, with fitness and average.
Did the average improve? Which operator contributed to the improvement of the best fitness?

Solution

1. Fitness: A=3, B=5, C=1, D=3. Average = $12/4=3$ .

2. (B, A): 111|011 × 110|100 → 111100, 110011. (B, D): 111|011 × 101|010 → 111010, 101011.

3. Flip bit 4 of 101011 → 101111. New population: 111100 (4), 110011 (4), 111010 (4), 101111 (5). Average = $17/4=\mathbf{4.25}$ .

4. The average rose from 3 to 4.25. Selection removed the weak chromosome C and duplicated B. Crossover recombined good segments but none of its children (fitness 4, 4, 4, 4) matched B (5). Mutation produced the one child with fitness 5 that is different from B (101111), which is how new genetic material enters the population.

Exercise E5: Design questions¶

For each problem, choose the encoding, the crossover and the mutation operator, and write the fitness function.

0/1 knapsack with 12 items and a weight limit.
Tuning 5 real-valued parameters of a controller.
Exam timetable where each of 20 exams gets a time slot (slots may repeat).
Delivery route through 15 cities.

Solution

Problem	Encoding	Crossover	Mutation	Fitness
Knapsack	Binary, length 12	Single-/two-point or uniform	Bit flip	Total value, with a penalty (or 0) if the weight exceeds the limit
Controller	Real vector of length 5	Arithmetic	Gaussian	Negative tracking error
Timetable	Integer vector, gene $i$ = slot of exam $i$	Uniform or one-point	Replace a gene by a random slot	$-$ (number of conflicts)
Route	Permutation of 15 cities	OX1 / PMX	Inversion or swap	$-$ (tour length)