Theory and Practice of Artificial Intelligence

FIND A SOLUTION AT Academic Writers Bay

Theory and Practice of Artificial Intelligence
Recursion, Examples and Exercises
Daniel Polani
School of Physics, Engineering and Computer Science
University of Hertfordshire
March 1, 2021
All rights reserved. Permission is granted to copy and distribute these slides in full or in part for purposes of
research, education as well as private use, provided that author, affiliation and this notice is retained.
Use as part of home- and coursework is only allowed with express permission by the responsible tutor and, in
this case, is to be appropriately referenced.
Theory and Practice of Artificial Intelligence 20 / 142
Exercise 2
Assumptions
Consider the tower of Hanoi
problem with three poles and
n disks.
Task
Write a function hanoi(.)
that moves a tower of size n
from a given start pole to a
target pole.
Theory and Practice of Artificial Intelligence 21 / 142
Exercise 3
Assumptions
Consider the tower of Hanoi
problem with three poles and
n disks.
Task
Write a function hanoi(.)
that moves a tower of size n
from a given start pole to a
target pole.
Example
def hanoi(n, start, goal, ignore):
if n == 1:
print start, “->”, goal
return
hanoi(n-1, start, ignore, goal)
print start, “->”, goal
hanoi(n-1, ignore, goal, start)
hanoi(4, 1, 2, 3)
Theory and Practice of Artificial Intelligence 21 / 142
Stateful Functions” (Generators and Yields)
Functions: information processing, then return result
a new call, new variables, new results
Generators: information processing, then yield result
new call to generator retains old state and
continues with new results
Example
def colours():
yield “red”
yield “green”
yield “black”
for c in colours():
print c
Example
def colours():
for c in [“red”,”green”,”black”]:
yield c
for c in colours():
print c
Theory and Practice of Artificial Intelligence 22 / 142
Exercise 4 (Permutation)
Assumptions
Consider a list […]
of elements.
Task
Write a generator
perm(.) that produces
all permutations of
above list.
Theory and Practice of Artificial Intelligence 23 / 142
Exercise 5 (Permutation)
Assumptions
Consider a list […]
of elements.
Task
Write a generator
perm(.) that produces
all permutations of
above list.
Example (Wrong! | Why?)
def insertion(e, s):
for i in range(len(s)+1):
s[i:i] = [e]
yield s
def perm(s):
if s == []:
yield []
else:
e, s1 = s[0], s[1:]
for s1p in perm(s1):
for p in insertion(e,s1p):
yield p
for p in perm([1,2,3,4]): print p
Theory and Practice of Artificial Intelligence 23 / 142
Exercise 6 (Permutation)
Assumptions
Example (Right! | Why?)
Consider a list […]
of elements.
Task
Write a generator
perm(.) that produces
all permutations of
above list.
def insertion(e, s):
for i in range(len(s)+1):
yield s[:i] + [e] + s[i:]
def perm(s):
if s == []:
yield []
else:
e, s1 = s[0], s[1:]
for s1p in perm(s1):
for p in insertion(e,s1p):
yield p
for p in perm([1,2,3,4]): print p
Theory and Practice of Artificial Intelligence 24 / 142
Copying Lists
Warning: Applying Functions to Lists
Functions/generators can modify lists destructively!
Example
def modifier(s):
s[2:4] = [“foo”, “bar”]
s = [1,2,3,4,5,6]
print “before:”, s
modifier(s)
print “after:”, s
# [1,2,3,4,5,6]
# [1,2,’foo’,’bar’,5,6]
Theory and Practice of Artificial Intelligence 25 / 142
Copying Lists
Warning: Applying Functions to Lists
Functions/generators can modify lists destructively!
Example
def modifier(s):
s[2:4] = [“foo”, “bar”]
s = [1,2,3,4,5,6]
print “before:”, s
modifier(s)
print “after:”, s
# [1,2,3,4,5,6]
# [1,2,’foo’,’bar’,5,6]
Example
def modifier(s):
s = s[:]
s[2:4] = [“foo”, “bar”]
s = [1,2,3,4,5,6]
print “before:”, s
modifier(s)
print “after:”, s
# [1,2,3,4,5,6]
# [1,2,3,4,5,6]
Theory and Practice of Artificial Intelligence 25 / 142
Proof of Correctness I
Question
How do you demonstrate that
1 you get all permutations?
2 you get each permutation exactly once?
Sanity Check
How many resulting permutations?
n! is a good start | it does not guarantee correctness, but if
this is wrong, that needs fixing first.
Theory and Practice of Artificial Intelligence 26 / 142
Proof of Correctness II
Induction
show that base case is correct (this is trivial)
assume that permutation generator for the smaller list (length
n – 1) is correct, i.e. that
1 it generates all permutations
2 all of them exactly once
under this assumption, prove that full list permutation (n)
retains this property.
Theory and Practice of Artificial Intelligence 27 / 142
Proof of Correctness III
Proof Idea
Base Case: obvious. Empty list has only itself as
permutation. Done.
Note: Not talking about debugging, only want to know whether recursion step covers
everything
Recursion Step: 1 Do we get all?
Assume, some arbitrary permutation given.
Is it included? We covered the case of the
empty list, so assume the list is not empty.
Recursion says: we know it is correct for list
of shorter length n – 1.
What now?
2 Do we get all of them exactly once?
Theory and Practice of Artificial Intelligence 28 / 142
Sheep and Cow Problem
Solution Part 1
E = 0
C = 1
S = 2
start_stable = [C, C, C, C, E, S, S, S, S]
goal_stable = [S, S, S, S, E, C, C, C, C]
Theory and Practice of Artificial Intelligence 29 / 142
Sheep and Cow Problem | Considerations
Possible Moves
1 Cow moves one field to the right (if empty)
2 Sheep moves one field to the left (if empty)
3 Cow jumps over one Sheep into an empty field
4 Sheep jumps over one Cow into an empty field
Theory and Practice of Artificial Intelligence 30 / 142
Sheep and Cow Problem | Considerations II
Patterns of Possible Moves
Cow moves right:
….C_….
…._C….
Sheep moves left:
…._S….
….S_….
Cow jumps right:
….CS_…
…._SC….
Sheep jumps left:
…._CS….
….SC_….
Idea
1 can only jump into empty
field
2 identify candidates for
moving/jumping animal
3 need to be inside field
4 need to conform to one of
the given patterns
Theory and Practice of Artificial Intelligence 31 / 142
Sheep and Cow Problem
Solution Part 2
def successors(stable):
# find empty spot
empty = stable.index(E)
# generate list of unfiltered candidate positions
candidates = [empty-2, empty-1, empty+1, empty+2]
# keep only those which are inside the stable
candidates = [c for c in candidates if c >= 0 and c < len(stable)]
# Cows can always move right, Sheep always left, and from two fields
# apart, they have to jump over an opposite animal
candidates = [c for c in candidates if
stable[c:c+2] == [C, E] or # cow can move right
stable[c-1:c+1] == [E, S] or # sheep can move left
stable[c:c+3] == [C, S, E] or # cow jumps over sheep
stable[c-2:c+1] == [E, C, S]] # sheep jumps over cow
# make sure that all these entries are occupied
# (not necessary for operation, just better style)
assert not [c for c in candidates if stable[c] == E]
for c in candidates:
new_stable = stable[:] # make a copy
# move the candidate into empty pos
new_stable[c], new_stable[empty] = new_stable[empty], new_stable[c]
yield new_stable # remember where we were
Theory and Practice of Artificial Intelligence 32 / 142
Sheep and Cow Problem
Solution Part 3
def solution(stable):
if stable == goal_stable:
return [stable]
# else, depth first
for new_stable in successors(stable):
# print new_stable
sol = solution(new_stable)
if sol:
return [stable] + sol
for s in solution(start_stable):
print s
Theory and Practice of Artificial Intelligence 33 / 142

READ ALSO...   briefly define democracy and evaluate
Order from Academic Writers Bay
Best Custom Essay Writing Services

QUALITY: 100% ORIGINAL PAPERNO PLAGIARISM – CUSTOM PAPER