[SOLVED] graph Questions:

Questions:
COMP7015 Artificial Intelligence Assignment 1 (Deadline: October 22, 2019)
1. The slide-tile puzzle consists of six tiles, and an empty space in the configuration shown in Figure 1.
Figure 1. The Sliding Block Puzzle
The puzzle has two legal moves with associated costs: A tile may move into an adjacent empty location. This has a cost of 1. A tile can hop over one or two other tiles into the empty position. This has a cost equal to the number of tiles jumped over.
The goal is to have all the tiles in an ascending order from left to right. The position of the blank is not important.
(a) What is the size of the state space?
(b) Propose a heuristic for solving this problem and analyze it with respect to
admissibility, and monotonicity.
2. Given the following graph:
3
2
1
6
5
4
A4B4C 3
3 S3
4
36G5 D2E8F
where S is a start state, and G is a goal state.
(a) Construct the corresponding search tree;
(b) Show the solution found by Uniform-Cost search.
3. Consider the following facts:
Everyone who loves all animals is loved by someone.
Anyone who kills an animal is loved by no one.
Jack loves all animals.
Either Jack or Curiosity killed the cat, who is named Tuna.
1 of Page 2

(a) Represent the above facts in first-order logic. (Hint: The number of first-order logic sentences may be more than four.)
(b) Convert all sentences in Part 3(a) to INF.
(c) Show that Curiosity kills the cat by using Proof-by-Contradiction.
4. Suppose that you are to deal with the situations described in the following table,
which gives the history of
Number Supervisor
1 Patrick
2 Patrick
3 Thomas
4 Patrick
5 Sally
eight past production runs in a factory setting:
Use ID3 with Gain Ratio to draw the decision tree.
Operator
Joe Samantha
Jim
Jim b no Joe c no
Machine Overtime
a no b yes
Output
high low
low high high low low
low
Samantha c no Joe c no
6 Thomas
7 Thomas
8 Patrick Jim a yes
< End>
b yes
2 of Page 2