Contains the following exam papers: 2018-06, 2017-10,
2017-06, 2016-06, Practice paper 1, Practice Paper 2
2018-06
A rational agent is an agent that Acts in order to achieve the best outcome, or where there is
uncertainty, the best-expected outcome. Conceptually speaking, it does the “right thing”.
Fully observable, because the players’ sensors give it access to the complete state of the
environment at each point in time, i.e. they can see every state.
,Elements of the problem are the initial state, actions and transition model implicitly defines it,
together.
State representation: S ={A1,A2,A3,C1,C2} which represents the people who have not yet crossed
yet. The elements in the set represent the people who have not yet crossed. An ampty set
represents that everyone have crossed.
The initial state: S = { A1,A2,A3, C1, C2}
The notation represents a set, the elements in the set are the people who want to cross. If they are
in the set it means that they have not crossed yet and if they are not it means that they have
crossed. Initially no one has crossed that is why all the people are in the set.
The symbol S means state. {} symbols means the set.
A1 representing Adult 1
A2 representing Adult 2
A3 representing Adult 3
C1 representing Child 1
C2 representiong Child 2
Breadth-first search is a simple strategy in which the root node is expanded first, then all the
successors of the root node are expanded next, then their successors, and so on. In general, all
the nodes are expanded at a given depth in the search tree before any nodes at the next level
are expanded.
When applying it to a tree or graph, it expands the node with the shortest path from the
frontier.
Breadth First Search (BFS) algorithm with a branching factor of β at depth δ:
o Has a complexity of O(β δ )
o This is an exponential growth
Space/Complexity gets large quickly
, E.g. =b^d
=6^7
=279,94
Breadth-first-search uses a FIFO queue.
Depth -first search always expands the deepest node in the current frontier of the search tree.
Depth-first search uses a LIFO queue.
The. search proceeds immediately to the deepest level of the search tree, where the nodes have
no successors. As those nodes are expanded, they are dropped from the frontier, so then the
search "backs up" to the next deepest node that still has unexplored successors.
The space complexity is linear
E.g. = b.d
6x7=42
DFS has a clear space complexity advantage over BFS when a tree search is performed
Property is consistency and the condition for it is h(n) < look it up
For both tree-search and graph search A* needs to have the property of optimality. For tree-search
A* is optimal of h(n) is admissible. For graph-search version A* is optimal if h(n) is consistent.
,DFS uses LIFO. So let’s trace the steps.
Node expanded Frontier/Stack in order from
left to right
1 F IBE
2 E IBHFA
3 A IBHFEB
4 B
5
I J F H B E Why not M? because M have also been expanded since DFS you don’t stop unless you
expand the goall
,A = 5, B = 5, C =2, H =50
, In the format ( alpha, beta, v)
B( -INF, 5, 5)
A(5, INF, 5)
C(5, 2, 2)
H(5,2, 36)
Yes, because we pruned, thus we didn’t have to consider those options.
The difference between the global and local maxima is that
Local minima/maxima are local solutions in the search space that are optimal solutions to the
problem in the immediate neighbourhood (within a given range, there isn’t a solution that beats it).
A global maxima/minimum is a solution to the problem that is the best solution in the entire solution
space (no other solution beats it).
,Forward checking It is a domain reduction technique which establishes arc consistency.
The clients need to be assigned to shuttles.
Thus the clients are the variables.
Variables: X={Abe, Bongi, Charlie, Dozi, Erica}
Dx = {0,1,2,3,4,5} (representing the order that they are picked up.)
Abe≠Bongi
Abe≠ Charlie
Bongi ≠Charlie
Abe≠Dozi
Dozi≠Erica
, Charlie Abe Dozi
Eric
Bongi
2 shuttles are needed:
a: shuttle picks up Abe
b: shuttle picks up Charlie
c: shuttle picks up Dozi
d: 2nd shuttle needed. Pick up Bongi.
e: Pick up Erica
1.) !CvA
2.) !AvBvC
3.) !BvA
4.) !A
5.) B Negate the goal
6.) !B 3&4
, 7.) 0 5&6
Thus we have reached the empty set, thus we have proven p |= !B
Poisonous(JackOLantern)
Ax( Poisonous(x) => !Eats(Asale,x) )
Note that implication you must use A, not E. because it implies that if anything is poisonous he won’t
eat it.
Aq( Eats(Chiwa,q) => Eats(Kapeni,q))
This is important one to remember. Kapeni eats anything Chiwa eats can be reworded as “IF Chiwa
eats anything then Kapeni eats it to”.
Eats(Chiwa, ToadStools) ^ SickFromEating(Chiwa, ToadsStools) *ask tutor
but relates to AND
EvEr( (Eats(v,r) ^ SickFromEating(v,r)) => Poisonous(r) )
, a) E[2,3] = 0.97
2/5 = 0.4 =
1st calculate the remainder of each attribute:
Rfever = Rno + Ryes
= Pno * E[0,2] + Pyes * E[2,1]
= 0.4 * 0 + 0.6 * 0.91
= 0.546
Rother symptoms = Rno + Ryes
= Pno * E[0,1] + Pyes * E[2,2]
= 0.2 * 0 + 0.8 * 1
= 0.8
Rabnormal bloodwork = Rno + Ryes
= Pno * E[1,2] + Pyes*E[1,1]
= 0.6 * 0.91 + 0.4 * 1
= 0.946
Now calculate the information gain of each attribute:
Gfever = 0.97 – 0.546 = 0.424
Gother symptoms = 0.97 – 0.8= 0.17
Gabnormal bloodwork = 0.97 – 0.946 = 0.024
Fever should be used since it has the biggest information gain
2017-06, 2016-06, Practice paper 1, Practice Paper 2
2018-06
A rational agent is an agent that Acts in order to achieve the best outcome, or where there is
uncertainty, the best-expected outcome. Conceptually speaking, it does the “right thing”.
Fully observable, because the players’ sensors give it access to the complete state of the
environment at each point in time, i.e. they can see every state.
,Elements of the problem are the initial state, actions and transition model implicitly defines it,
together.
State representation: S ={A1,A2,A3,C1,C2} which represents the people who have not yet crossed
yet. The elements in the set represent the people who have not yet crossed. An ampty set
represents that everyone have crossed.
The initial state: S = { A1,A2,A3, C1, C2}
The notation represents a set, the elements in the set are the people who want to cross. If they are
in the set it means that they have not crossed yet and if they are not it means that they have
crossed. Initially no one has crossed that is why all the people are in the set.
The symbol S means state. {} symbols means the set.
A1 representing Adult 1
A2 representing Adult 2
A3 representing Adult 3
C1 representing Child 1
C2 representiong Child 2
Breadth-first search is a simple strategy in which the root node is expanded first, then all the
successors of the root node are expanded next, then their successors, and so on. In general, all
the nodes are expanded at a given depth in the search tree before any nodes at the next level
are expanded.
When applying it to a tree or graph, it expands the node with the shortest path from the
frontier.
Breadth First Search (BFS) algorithm with a branching factor of β at depth δ:
o Has a complexity of O(β δ )
o This is an exponential growth
Space/Complexity gets large quickly
, E.g. =b^d
=6^7
=279,94
Breadth-first-search uses a FIFO queue.
Depth -first search always expands the deepest node in the current frontier of the search tree.
Depth-first search uses a LIFO queue.
The. search proceeds immediately to the deepest level of the search tree, where the nodes have
no successors. As those nodes are expanded, they are dropped from the frontier, so then the
search "backs up" to the next deepest node that still has unexplored successors.
The space complexity is linear
E.g. = b.d
6x7=42
DFS has a clear space complexity advantage over BFS when a tree search is performed
Property is consistency and the condition for it is h(n) < look it up
For both tree-search and graph search A* needs to have the property of optimality. For tree-search
A* is optimal of h(n) is admissible. For graph-search version A* is optimal if h(n) is consistent.
,DFS uses LIFO. So let’s trace the steps.
Node expanded Frontier/Stack in order from
left to right
1 F IBE
2 E IBHFA
3 A IBHFEB
4 B
5
I J F H B E Why not M? because M have also been expanded since DFS you don’t stop unless you
expand the goall
,A = 5, B = 5, C =2, H =50
, In the format ( alpha, beta, v)
B( -INF, 5, 5)
A(5, INF, 5)
C(5, 2, 2)
H(5,2, 36)
Yes, because we pruned, thus we didn’t have to consider those options.
The difference between the global and local maxima is that
Local minima/maxima are local solutions in the search space that are optimal solutions to the
problem in the immediate neighbourhood (within a given range, there isn’t a solution that beats it).
A global maxima/minimum is a solution to the problem that is the best solution in the entire solution
space (no other solution beats it).
,Forward checking It is a domain reduction technique which establishes arc consistency.
The clients need to be assigned to shuttles.
Thus the clients are the variables.
Variables: X={Abe, Bongi, Charlie, Dozi, Erica}
Dx = {0,1,2,3,4,5} (representing the order that they are picked up.)
Abe≠Bongi
Abe≠ Charlie
Bongi ≠Charlie
Abe≠Dozi
Dozi≠Erica
, Charlie Abe Dozi
Eric
Bongi
2 shuttles are needed:
a: shuttle picks up Abe
b: shuttle picks up Charlie
c: shuttle picks up Dozi
d: 2nd shuttle needed. Pick up Bongi.
e: Pick up Erica
1.) !CvA
2.) !AvBvC
3.) !BvA
4.) !A
5.) B Negate the goal
6.) !B 3&4
, 7.) 0 5&6
Thus we have reached the empty set, thus we have proven p |= !B
Poisonous(JackOLantern)
Ax( Poisonous(x) => !Eats(Asale,x) )
Note that implication you must use A, not E. because it implies that if anything is poisonous he won’t
eat it.
Aq( Eats(Chiwa,q) => Eats(Kapeni,q))
This is important one to remember. Kapeni eats anything Chiwa eats can be reworded as “IF Chiwa
eats anything then Kapeni eats it to”.
Eats(Chiwa, ToadStools) ^ SickFromEating(Chiwa, ToadsStools) *ask tutor
but relates to AND
EvEr( (Eats(v,r) ^ SickFromEating(v,r)) => Poisonous(r) )
, a) E[2,3] = 0.97
2/5 = 0.4 =
1st calculate the remainder of each attribute:
Rfever = Rno + Ryes
= Pno * E[0,2] + Pyes * E[2,1]
= 0.4 * 0 + 0.6 * 0.91
= 0.546
Rother symptoms = Rno + Ryes
= Pno * E[0,1] + Pyes * E[2,2]
= 0.2 * 0 + 0.8 * 1
= 0.8
Rabnormal bloodwork = Rno + Ryes
= Pno * E[1,2] + Pyes*E[1,1]
= 0.6 * 0.91 + 0.4 * 1
= 0.946
Now calculate the information gain of each attribute:
Gfever = 0.97 – 0.546 = 0.424
Gother symptoms = 0.97 – 0.8= 0.17
Gabnormal bloodwork = 0.97 – 0.946 = 0.024
Fever should be used since it has the biggest information gain
