T12-D3: (PROLOG and Knowledge-Based System) -- SOLUTION SKETCH
Practice Problem 1,2,3 of Ch.9.4.2 of [SG3].
(i) ?-before(jefferson, kennedy) Answer: FALSE [pattern matching]
(ii) ?-president(X, lewis_and_clark) Answer: X=jefferson [pattern matching]
(iii) ?-precedes(jefferson, X)
Answer: X=lincoln, X=fdr, X=kennedy, X=nixon
Working for (iii): [via rule-expansion by the inference engine]
?-precedes(jefferson,X)
|
+--> R1: before(jefferson,X) Gives: X=lincoln [pattern matching]
|
+--> R2: [before(jefferson,Z) and precedes(Z,X)]
|substitute Z=lincoln
[before(jefferson,lincoln) and precedes(lincoln,X)]
precedes(lincoln,X)]
+--> R1: before(lincoln,X) Gives: X=fdr
+--> R2: [before(lincoln,W) and precedes(W,X)];
|subs W=fdr
[before(lincoln,fdr) and precedes(fdr,X)]
precedes(fdr,X)] (shortened working)
+--> R1: before(fdr,X) Gives: X=kennedy
+--> R2: [before(fdr,kennedy) and precedes(kennedy,X)]
precedes(kennedy,X)]
+--> R1: before(kennedy,X) Gives: X=nixon
+--> R2: [before(kennedy,nixon) and precedes(nixon,X)]
precedes(nixon,X)]
+--> R1: before(nixon,X) No solution for X
+--> R2: [before(nixon,S) and precedes(S,X)]
(No-soln-for-S; recursion STOPS)
[Note the recursive application of the rule R2 in the above.]
T12-Q2: (5 points) (Pancake Flipping) (SOLUTION SKETCH)
(i) Greedy Algorithms:
1243 ==> 4213 ==> 3124 ==> 2134 ==> 1234 (4 flips)
(ii) State space graph:
2413 ==== 4213 ==== 3124
|
|
3412 ==== 2143 ==== [1243] ==== 3421 ==== 4321
| |
| |
4123 2431
(iii) Optimal sequence: 1243 ==> 3421 ==> 4321 ==> 1234
T12-Q1: (10 points) (eight-puzzle) (SOLUTION SKETCH)
123
46
758
|
+-------------------------+-------------------------+
| | |
23 123 123
146 4 6 746
758 758 58
| | |
| +------------+------------+ |
| | | | |
2 3 1 3 123 123 123
146 426 46 456 746
758 758 758 7 8 5 8
| | | | |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+
| | | | | | | | | |
23 243 13 13 12 123 123 123 123 123
146 1 6 426 426 463 468 456 456 7 6 746
758 758 758 758 758 75 78 78 548 58
Goal state is reachable in three moves!
123 123 123 123
46 ---> 4 6 ---> 456 --> 456
758 758 7 8 78
T12-Q3: (15 points) (PROLOG & KBS) (SOLUTION SKETCH)
(a)(i) ?-before(U, kennedy) gives U=fdr [by pattern matching]
(a)(ii) ?-precedes(kennedy, nixon)
gives ==> TRUE
[via rule-expansion by the inference engine]
?-precedes(kennedy, nixon)
+--> R1: before(kennedy, nixon) ==> TRUE [by pattern matching]
(a)(iii) ?-precedes(S, fdr)
==> S=lincoln, S=jefferson
[via rule-expansion by the inference engine]
?-precedes(S, fdr)
|R1
+--> before(S, fdr) ==> S=lincoln [by pattern matching]
| [meaning precedes(lincoln, fdr) = true; ]
|R2
+--> before(S, T), precedes(T,fdr)
| |R1
| +--> before(T,fdr) ==> T=lincoln
|
|substitute T=lincoln
before(S, lincoln) ==> S=jefferson
+--> before(S, T), precedes(T,fdr)
| |R2
| +--> before(T, U), precedes(U,fdr)
| | +--> before(U,fdr) ==> U=lincoln
| |
| |substitute U=lincoln
| before(T, lincoln) ==> T=jefferson
|
|substitute T=jefferson
before(S, jefferson) ==> S=null
[End of rule expansion]
(b)(i) ?-precedes(carter, T). (Show sequence of rule-expansions to get the answer.)
==> T=reagan, T=bush-41
[via rule-expansion by the inference engine]
?-precedes(carter, T)
|R1
+--> before(carter, T) ==> T=reagan [ANSWER] [by pattern matching]
| [meaning precedes(carter, reagan) = true; ]
|R2
+--> before(carter, Z1), precedes(Z1, T)
|==>Z1=reagan
before(carter, reagan), precedes(reagan, T)
/R1
+--> before(reagan, T)
/ ==> T=bush-41 [ANSWER]
/R2
+--> before(reagan, Z2), precedes(Z2, T)
|==>Z2=bush-41
before(reagan, bush-41), precedes(bush-41, T)
before(reagan, bush-41), precedes(bush-41, T)
|R1
+--> before(bush-41, T) ==> T=null
|R2
+--> before(bush-41, Z3), precedes(Z3, T)
==>Z3=null
[End of rule expansion]
(b)(ii) ?-precedes(kennedy, reagan).
==> FALSE
[via rule-expansion by the inference engine]
?-precedes(kennedy, reagan)
|R1
+--> before(kennedy, reagan) ==> FALSE [by pattern matching]
|R2
+--> before(kennedy, U1), precedes(U1, reagan)
|==>U1=nixon
before(kennedy, nixon), precedes(nixon, reagan)
/R1
+--> before(nixon, reagan)
/ ==> FALSE
/R2
+--> before(nixon, U2), precedes(U2, reagan)
==>U2=null
[End of rule expansion]