Artificial Intelligence: Problem Set 6: Solutions

Problem 1.

The best move from the root is to the left.

Problem 2:

Problem 3:

Initially,

G = { A-J X 1-10 }
S = { emptyset }

On encountering the point C,5: IN:

The rule in G, A-J X 1-10, is correct, so unchanged.
The rule in S is a false negative and must be generalized. There are four minimal generalizations that include C,5: A-C X 1-5, A-C X 5-10, C-J X 1-5, C-J X 5-10.

Therefore the new values of G and S are
G: { A-J X 1-10 }
S: { A-C X 1-5, A-C X 5-10, C-J X 1-5, C-J X 5-10 }.

On encountering the point F,3: OUT.

The rule A-J X 1-10 in G is a false positive. There are four maximal specializations that exclude F,3: A-E X 1-10, G-J X 1-10, A-J X 1-2, A-J X 4-10. However, the rules G-J X 1-10 and A-J X 1-2 are inconsistent with the previous point C,5 : IN.

The rule A-C X 1-5 in S gives the correct answer, and so is unchanged.
The rule A-C X 5-10 in S gives the correct answer, and so is unchanged.
The rule C-J X 1-5 in S is a false positive and so is dropped.
The rule C-J X 5-10 in S gives the correct answer, and so is unchanged.

Therefore,
G = { A-E X 1-10, A-J X 4-10 }
S = { A-C X 1-5, A-C X 5-10, C-J X 5-10 }.

On encountering the point E,8 : OUT.

The rule A-E X 1-10 in G is a false positive. The maximal specializations of this rule that exclude point E,8 are A-D X 1-10, A-E X 1-7, and A-E X 9-10. However, the last of these is inconsistent with the previous point C,5 : IN.

The rule A-J X 4-10 gives a false positive for E,8. The maximal specializations of this rule that exclude E,8 are A-D X 4-10, F-J X 4-10, and A-J X 9-10. However, all but the first of these is inconsistent with the previous point C,5 : IN.

The rule A-C X 1-5 in S gives the correct answer, and so is unchanged.
The rule A-C X 5-10 in S gives the correct answer, and so is unchanged.
The rule C-J X 5-10 in S is a false positive, and so is dropped.

Therefore,
G = { A-D X 1-10, A-E X 1-7, A-D X 4-10 }
S = { A-C X 1-5, A-C X 5-10 }