Exercises: Artificial Intelligence

The farmer, fox, goose and grain

 Problem
• A farmer has to cross a river with his fox,
goose and grain. Each trip, his boat can only
carry himself and one of his possessions. How
can he cross the river if an unguarded fox eats
the goose and an unguarded goose the grain.
– Find a good representation.
– Perform Depth-first search (queues)
– Perform Breadth-first search (search tree)
Farmer, Fox, Goose and Grain

PROBLEM REPRESENTATION
 Representation
• States of the form [L|R], where:
– L: Items on left bank
– R: Items on right bank
• L and R contain:
– Fa: Farmer
– Fo: Fox
– Go: Goose
– Gr: Grain
 Representation
• Start: [Fa Fo Go Gr|]
• Goal: [|Fa Fo Go Gr]
• Rules:
– R1: [Fa X|Y] ö [X|Fa Y]
– R2: [X|Fa Y] ö [Fa X|Y]
– R3: [Fa z X|Y] ö [X|Fa z Y]
– R4: [X|Fa z Y] ö [Fa z X|Y]
– No combination (Fo,Go) or (Go,Gr) on either bank,
without the farmer.
Farmer, Fox, Goose and Grain

DEPTH-FIRST SEARCH
 Depth-first search (queues)
• Input:
– QUEUE: Path only containing root
• Algorithm:
– WHILE (QUEUE not empty && goal not reached) DO
• Remove first path from QUEUE
• Create paths to all children
• Reject paths with loops
• Add paths to front of QUEUE
– IF goal reached
• THEN success
• ELSE failure
 Depth-first search (queues)
• Start = (<[Fa Fo Go Gr|]>)
 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
– Paths to Children:
• R3: <[Fa Fo Go Gr|][Fo Gr|Fa Go]>
• Q1 = (< [Fo Gr|Fa Go]>)
[Fa Fo Go Gr|]
 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
• Q1 = (< [Fo Gr|Fa Go]>)
[Fa Fo Go Gr|]

– Paths to Children:
• R2: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go]>
• R4: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Go Gr|]>
• Q2 = (< [Fa Fo Gr|Go]>)
[Fa Fo Go Gr|][Fo Gr|Fa Go]
 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
• Q1 = (< [Fo Gr|Fa Go]>)
[Fa Fo Go Gr|]

• Q2 = (< [Fa Fo Gr|Go]>)

[Fa Fo Go Gr|][Fo Gr|Fa Go]

– Paths to Children:
• R1: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Fo Gr|Fa Go]>
• R3: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go]>
• R3: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Fo|Fa Go Gr]>
• Q3 = (< [Gr|Fa Fo Go]>,<
[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go] [Fa Fo Go Gr|][Fo

[Gr|Fo Go Gr]>)
Gr|Fa Go][Fa Fo Gr|Go]
 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
• Q1 = (< [Fo Gr|Fa Go]>)
[Fa Fo Go Gr|]

• Q2 = (< [Fa Fo Gr|Go]>)

[Fa Fo Go Gr|][Fo Gr|Fa Go]

• Q3 = (< [Gr|Fa Fo Go]>,<

[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go] [Fa Fo Go Gr|][Fo Gr|Fa

[Gr|Fo Go Gr]>)
Go][Fa Fo Gr|Go]

– Paths to Children:
• R4: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Fo Gr|Go]>
• R4: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo]>
• Q4 = (< [Fa Go Gr|Fo]>,<
[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go] [Fa Fo Go

Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go] [Gr|Fo Go Gr]>)

 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
• Q1 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go]>)
• Q2 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go]>)
• Q3 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo
Gr|Go][Gr|Fo Go Gr]>)

• Q4 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo]>,<[Fa Fo Go Gr|][Fo

Gr|Fa Go][Fa Fo Gr|Go][Gr|Fo Go Gr]>)

– Paths to Children:
• R3: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Gr|Fa Fo Go]>
• R3: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr]>
• Q5 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr]>,<[Fa Fo
Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fo Go Gr]>)
 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
• Q1 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go]>)
• Q2 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go]>)
• Q3 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo
Gr|Go][Gr|Fo Go Gr]>)

• Q4 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo
Gr|Go][Gr|Fo Go Gr]>)

• Q5 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr]>,<[Fa Fo Go Gr|][Fo

Gr|Fa Go][Fa Fo Gr|Go][Gr|Fo Go Gr]>)
– Paths to Children:
• R2: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go|Fo Gr]>
• R4: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Fo Go|Gr]>
• R4: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go Gr|Fo]>
• Q6 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go|Fo
Gr]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Fo
Go|Gr]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fo Go Gr]>)
 Depth-first search (queues)
• S = (<[Fa Fo Go Gr|]>)
• Q1 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go]>)
• Q2 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go]>)
• Q3 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fo Go
Gr]>)
• Q4 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo
Gr|Go][Gr|Fo Go Gr]>)

• Q5 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo
Gr|Go][Gr|Fo Go Gr]>)

• Q6 = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go|Fo Gr]>,<[Fa Fo Go Gr|][Fo
Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Fo Go|Gr]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fo
Go Gr]>)
– Paths to Children:
• R1: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go|Fo Gr][Go|Fa Fo Gr] >
• R3: <[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go|Fo Gr][|Fa Fo Go Gr]>
• G = (<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Go|Fo Gr][|Fa Fo Go Gr]>,<[Fa Fo
Go Gr|][Fo Gr|Fa Go][Fa Fo Gr|Go][Gr|Fa Fo Go][Fa Go Gr|Fo][Go|Fa Fo Gr][Fa Fo Go|Gr]>,<[Fa Fo Go Gr|][Fo Gr|Fa Go][Fa Fo
Gr|Go][Gr|Fo Go Gr]>)
 Depth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo])

([Go|Fa Fo Gr])

([Fa Go|Fo Gr]) ([Fa Fo Go|Gr])

([|Fa Fo Go Gr])
Farmer, Fox, Goose and Grain

BREADTH-FIRST SEARCH
 Breadth-first search (queues)
• Input:
– QUEUE: Path only containing root
• Algorithm:
– WHILE (QUEUE not empty && goal not reached) DO
• Remove first path from QUEUE
• Create paths to all children
• Reject paths with loops
• Add paths to end of QUEUE
– IF goal reached
• THEN success
• ELSE failure
Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])
Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo])
Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

([Go|Fa Fo Gr])
Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

([Go|Fa Fo Gr]) ([Go|Fa Fo Gr])

 Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

([Go|Fa Fo Gr]) ([Go|Fa Fo Gr])

([Fa Go|Fo Gr]) ([Fa Fo Go|Gr])

 Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

([Go|Fa Fo Gr]) ([Go|Fa Fo Gr])

([Fa Go|Fo Gr]) ([Fa Fo Go|Gr]) ([Fa Go|Fo Gr]) ([Fa Go Gr|Fo])
 Breadth-first search (search tree)
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

([Go|Fa Fo Gr]) ([Go|Fa Fo Gr])

([Fa Go|Fo Gr]) ([Fa Fo Go|Gr]) ([Fa Go|Fo Gr]) ([Fa Go Gr|Fo])

([|Fa Fo Go Gr])
Farmer, Fox, Goose and Grain

ENTIRE SEARCH TREE

 Entire search tree
([Fa Fo Go Gr|])

([Fo Gr|Fa Go])

([Fa Fo Gr|Go])

([Gr|Fa Fo Go]) ([Fo|Fa Go Gr])

([Fa Go Gr|Fo]) ([Fa Fo Go|Gr])

([Go|Fa Fo Gr]) ([Go|Fa Fo Gr])

([Fa Go|Fo Gr]) ([Fa Fo Go|Gr]) ([Fa Go|Fo Gr]) ([Fa Go Gr|Fo])

([|Fa Fo Go Gr]) ([|Fa Fo Go Gr]) ([Gr|Fa Fo Go])

Exercises: Artificial Intelligence

Bidiretional Search
 Problem
• Which methods other than breadth-first can
be used in bidirectional search?
– Is it possible to replace breadth-first for either or
both of the forward and backward direction?
• Does the method still work if the check for the
shared state is replaced by a check for
identical end nodes?
Bidirectional Search

PROBLEM 1: BREADTH-FIRST?
 Other methods than 2 x breadth-first
• Bidirectional search is complete for each
combination with at least one complete
search-strategy.
– 2 x Breadth-first
– 2 x Depth-first
– Breadth-first and Depth-first
• Not each combination benefits from searching
at both ends.
 2 x Depth-first

• Forward:
– (<S>) Ø(<SA>,<SE>) Ø(<SAB>,<SE>) Ø(<SABC>,<SE>)
Ø(<SABCD>,<SE>) Ø(<SABCDF>,<SE>)
• Backward:
– (<G>) Ø(<GK>,<GL>) Ø(<GKJ>,<GL>) Ø(<GKJI>,<GL>)
Ø(<GKJIH>,<GL>) Ø(<GKJIHF>,<GL>)
A B C D

S E F L G

H I J K
 2 x Breadth-first

• Forward:
– (<S>)Ø(<SA>,<SE>)Ø(<SE>,<SAB>)Ø(<SAB>,<SEF>)
• Backward:
– (<G>)Ø(<GK>,<GL>)Ø(<GL>,<GKJ>)Ø(<GKJ>,<GLF>)

A B C D

S E F L G

H I J K
 Breadth-first and Depth-first

• Forward (Breadth-first):
– (<S>)Ø(<SA>,<SE>)Ø(<SE>,<SAB>)Ø(<SAB>,<SEF>)
Ø(<SEF>,<SABC>)
• Backward (Depth-first):
– (<G>)Ø(<GJ>,<GD>)Ø(<GJI>,<GD>)Ø(<GJIH>,<GD>)
Ø(<GJIHF>,<GD>)

A B C D
S G
E F H I J
Bidirectional Search

PROBLEM 2: SHARED-STATE CHECK?

 Replace shared-state check

• When only checking identical end-states,

paths can cross each other unnoticed.
• Forward:
– (<S>)Ø(<SA>)Ø(<SAB>)Ø(<SABG>)
• Backward:
– (<G>)Ø(<GB>)Ø(<SBA>)Ø(<SBAG>)

S A B G
Exercises: Artificial Intelligence

Beam Search
 Beam Search
• Input:
– QUEUE: Path only containing root
– WIDTH: Number
• Algorithm:
– WHILE (QUEUE not empty && goal not reached) DO
• Remove all paths from QUEUE
• Create paths to all children (of all paths)
• Reject paths with loops
• Sort new paths (according to heuristic)
• (Optimization: Remove paths without successor)
• Add WIDTH best paths to QUEUE
– IF goal reached
• THEN success
• ELSE failure
Exercises: Artificial Intelligence

Path Search
 Problem
• Find a path from ‘S’ to ‘G’, without passing
through black squares.
– Legal steps (order):
• up, left, right, down
G
• Perform:
– Depth-first search
– Hill-climbing I Search S
• With suitable heuristic
– Greedy Search
• With same heuristic
Path Search

DEPTH-FIRST SEARCH
 Depth-first Search

G
G

S S
 Depth-first Search

G
G

2 1

S S
 Depth-first Search

G
G

2 1 3

S S
 Depth-first Search

G
G

2 1 3 4

S S
 Depth-first Search

G
G

2 1 3 4 5

S S
 Depth-first Search

G
G

2 1 3 4 5 6

S S
 Depth-first Search

G
G
7

2 1 3 4 5 6

S S
 Depth-first Search

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

12 11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

13 12 11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

14 13 12 11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

15 14 13 12 11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

16 15 14 13 12 11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

17 16 15 14 13 12 11 10

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

17 16 15 14 13 12 11 10

18 9

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

17 16 15 14 13 12 11 10

18 19 9

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

17 16 15 14 13 12 11 10

18 19 20 9

G 8
G
7

2 1 3 4 5 6

S S
 Depth-first Search

17 16 15 14 13 12 11 10

18 19 20 9

G 8
G
7

2 1 3 4 5 6

S S
Path Search

HILL-CLIMBING I SEARCH
Heuristic: Manhatten Distance

4 3 2 3 4 5 6 7

3 2 1 2 3 4 5 6

2 1 0 1 2 3 4 5

3 2 6

4 2 3 4 5 6 7

5 4 4 5 6 8

6 5 4 5 6 7 8 9

7 6 5 6 7 8 9 10
 Hill-climbing I Search
• Input:
– QUEUE: Path only containing root
• Algorithm:
– WHILE (QUEUE not empty && goal not reached) DO
• Remove first path from QUEUE
• Create paths to all children
• Reject paths with loops
• Sort new paths using heuristic
• Add sorted paths to front of QUEUE
– IF goal reached
• THEN success
• ELSE failure
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 1

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3 4

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3 4 5

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G 8
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G 9 8
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G 10 9 8
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G 11 10 9 8
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G 12 11 10 9 8
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Hill-climbing I Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G 12 11 10 9 8
2 1 G 1 2 3 4 5
3 2 6 7

4 2 3 4 5 6 7 2 1 3 4 5 6

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
Path Search

GREEDY SEARCH
 Greedy Search
• Input:
– QUEUE: Path only containing root
• Algorithm:
– WHILE (QUEUE not empty && goal not reached) DO
• Remove first path from QUEUE
• Create paths to all children
• Reject paths with loops
• Add paths to QUEUE and sort the entire QUEUE (heuristic)
– IF goal reached
• THEN success
• ELSE failure
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 1

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3 4

5 4 S 5 6 8 S
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3 4

5 4 S 5 6 8 S 5
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3 4

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1 3/7 4

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2 1/8 3/7 4

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4/10

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4/10

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4/10

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4/10

5 4 S 5 6 8 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4/10

5 4 S 5 6 8 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 2/9 1/8 3/7 4/10

5 4 S 5 6 8 15 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6
4 2 3 4 5 6 7 16 2/9 1/8 3/7 4/10

5 4 S 5 6 8 15 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
G
2 1 G 1 2 3 4 5
3 2 6 17

4 2 3 4 5 6 7 16 2/9 1/8 3/7 4/10

5 4 S 5 6 8 15 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
18 G
2 1 G 1 2 3 4 5
3 2 6 17

4 2 3 4 5 6 7 16 2/9 1/8 3/7 4/10

5 4 S 5 6 8 15 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
18 19 G
2 1 G 1 2 3 4 5
3 2 6 17

4 2 3 4 5 6 7 16 2/9 1/8 3/7 4/10

5 4 S 5 6 8 15 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
 Greedy Search

4 3 2 3 4 5 6 7
3 2 1 2 3 4 5 6
18 19 G
2 1 G 1 2 3 4 5
3 2 6 17

4 2 3 4 5 6 7 16 2/9 1/8 3/7 4/10

5 4 S 5 6 8 15 14 S 5/6
6 5 4 5 6 7 8 9 13 12 11
7 6 5 6 7 8 9 10
Exercises: Artificial Intelligence

Water Jugs
 Problem
• Solve the water jugs problem
– Given two jugs of 4 liter and 3 liter respectively, fill
the 4 liter jug with 2 liter of water.
– Find a good heuristic.
– Perform Hill-climbing II Search.
Water jugs

PROBLEM REPRESENTATION
 Representation
• States of the form [x,y], where:
– x: contents of 4 liter jug
– y: contents of 3 liter jug
• Start: [0,0]
• Goal: [2,0]
 Representation
• Rules:
– Fill x: [x,y] ⁄ x < 4 ö [4,y]
– Fill y: [x,y] ⁄ y < 3 ö [x,3]
– Empty x: [x,y] ⁄ x > 0 ö [0,y]
– Empty y: [x,y] ⁄ y > 0 ö [x,0]
– Fill x with y: [x,y] ⁄ x+y > 4 ⁄ y > 0 ö [4,(x+y-4)]
– Fill x with y: [x,y] ⁄ x+y ≤ 4 ⁄ y > 0 ö [(x+y),0]
– Fill y with x: [x,y] ⁄ x+y > 3 ⁄ x > 0 ö [(x+y-3),3]
– Fill y with x: [x,y] ⁄ x+y ≤ 3 ⁄ x > 0 ö [0,(x+y)]
Water jugs

HEURISTIC
 Heuristic
• H([x,y]) = f(x) + f(y)
• f(x) is defined as follows:
x 0 1 2 3 4
f(x) 2 1 0 1 3

– We need a jug filled with 2 liter.

– To obtain a jug filled with 2 liter we need a jug
filled with either 1 or 3 liter.
– We consider an empty jug better than a jug filled
with 4 liter.
Water jugs

HILL-CLIMBING II SEARCH
Hill-climbing II Search
4
[0,0]

3 5
[0,3] [4,0]
Hill-climbing II Search
4
[0,0]

3 5
[0,3] [4,0]

3 4
[3,0] [4,3]
Hill-climbing II Search
4
[0,0]

3 5
[0,3] [4,0]

3 4
[3,0] [4,3]

2 5
[3,3] [4,0]
Hill-climbing II Search
4
[0,0]

3 5
[0,3] [4,0]

3 4
[3,0] [4,3]

2 5
[3,3] [4,0]

3 4
[4,2] [4,3]
 Hill-climbing II Search
4
[0,0]

3 5
[0,3] [4,0]

3 4
[3,0] [4,3]

2 5
[3,3] [4,0]

3 4
[4,2] [4,3]

4 2 5
[4,3] [0,2] [4,0]
 Hill-climbing II Search
4
[0,0]

3 5
[0,3] [4,0]

3 4
[3,0] [4,3]

2 5
[3,3] [4,0]

3 4
[4,2] [4,3]

4 2 5
[4,3] [0,2] [4,0]

2
[2,0]