Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Example Exam Questions on

Search, MiniMax and KRR

for Artificial Intelligence

(COMP2611)

2022

Question 1:  Search

The following graph diagram represents a transport network. Each circle represents a town (identi- fied by the letter in the circle) and each line represents a road linking two towns. Next to each road is a number which is a measure of the distance between the two connected towns when travelling along that road. Roads can be travelled in either direction.

This network is to be used as input to a search algorithm, in order to find the shortest route starting at town S and ending at town G.

To guide the search for a good route, a heuristic  function has been specified which gives an estimate of the cost of getting from any given town to the goal town G. The value of this function is given in the circle underneath the town’s designating letter.

 

1. What is the optimal route from S to G and what is its length?                               [2 marks]

2.  State whether the specified heuristic is admissible. Briefly explain your answer in one or two sentences.                                                                                                                      [2 marks]

3. Write down the sequence in which nodes will be expanded until the goal destination G is reached, while performing a best first search (also known as greedy search).           [2 marks]

4. Write down the sequence in which nodes will be expanded, until the goal destination G is reached, while performing a uniform cost search.                                                      [2 marks]

5. Write down the sequence in which nodes will be expanded until the goal destination G is reached, while performing an A*  (A-Star ) search.                                                     [2 marks]

6.  The straight line distance from a location to the destination provides a heuristic function that is appropriate for many kinds of route planning problem. Briefly explain (2 or 3 sentences) a reason why this heuristic does not perform well for all route planning problems.   [2 marks]

Question 2:  Minimax

Consider the following game tree for an adversarial game:

Max 

Min 

Max 

 

 

3          4         6          10        1          8          5         3          2         6           7

 

1. Use Minimax to compute the values of all the non-leaf nodes and add these to diagram (i) on the supplementary answer sheet.                                                                                [3 marks]

2.  To make the optimal next move, should Max take the left, middle or right branch?  [1 mark]

3.  By copying the above tree and annotating your diagram, show how alpha-beta pruning can be used to efficiently calculate the minimax values required to make the fist move choice without looking at all nodes.  Show the value bounds used in the computation and clearly indicate which nodes and/or sub trees are pruned from the search.                                       [5 marks]


Question 3:  Logical Representation

1.  Translate the following sentence into Propositional Logic:

· If I get paid tomorrow, I will see you on Friday, otherwise I won’t.             · You can’t climb the mountain unless you have good boots and sun cream.

[1 mark] [2 marks]


2.  Translate the following sentences into First-Order Predicate Logic:


(a) All pigs have curly tails.

(b)  Susan and Tom both visited the same museum.

(c) I don’t like anyone who doesn’t like me.

(d) Every student has at least two books.

[2 [2 [2 [3


marks] marks] marks] marks]


3. A propositional model assigns the truth values:  A = t, B = t, C = f .  According to this model, what would be the truth value of the formula A 二 (B 二 C)  ?                   [1 mark]

 

4. M =  〈D, δ〉  is a model for a first-order language with a unary predicate F and a binary relation R. The domain of M is the set {a, b, c, d, e}, and the denotations of F and R are as follows:

· δ(F) = {a, b, c, d}

· δ(R) = {〈a, c〉,〈b, c〉,〈b, d〉,〈c, e〉,〈d, c〉,〈e, e〉}

Which of the following formulae are satisfied by this model?                                   [2 marks]

F1. Vx[F (x) v R(x, x)]

F2.  axVy[R(x, y)]

F3.  ax[F (x) A R(x, x)]

F4.  axVy[R(x, y) v R(y, x)


Question 4:  Logical Proof

1.  Convert the following formula into clausal form (a.k.a. Conjunctive Normal Form). Give your answer in the standard form, where it is represented as a set of sets of literals:     [3 marks]

 

-(A v B) 二 ((C v D) A E).

(Note: ‘Literals’ are atomic propositions or negated atomic propositions.)

 

2. Use binary propositional resolution to show that the following set of propositional clauses is

inconsistent:


[5 marks]

{{P, Q, R},  {-P, S},  {-Q, S, T},  {-R, S},  {-S},  {-T}}


3. Using only rules specified in the limited rule set given below, construct a Natural Deduction proof of the following sequent:                                                                                    [6 marks]

P v Q,   P 二 Vx[S(x)],   (Q v R) 二 S(a)   上    S(a)

 

Natural Deduction Rule Set:

[ P ]nα      [ Q ]nó

  vIr             vIl                      vEn

 

P   Q(P) Q  E                                              VE

 

Where P , Q, C are any formulae, φ(ν) is a formula containing variable ν and κ is any constant (so φ(κ) is the formula resulting from substituting κ in place of ν in φ(x)).