CS360/SE360: Artificial Intelligence
Individual Written Assignment 1
1. Please read the following description and answer all the questions.
The diagram in (a) needs to show only those valid/necessary/useful states.
b. Represent all states in (a) and (b) using same 6-tuple (a tuple of 6 positive integers).
Mention the initial and final states also as 6-tuple. How many ways the solution can be
found? (Assume that only one missionary and one cannibal can row the boat).
2. Consider the problem 3.15 in the textbook.
What is the full search space size (assume k can be any positive integer)? If you had to choose,
would you pick breadth-first or depth-first search as a method for exploring a larger portion of
this state space? Explain your answer.
3. Imagine you have a state space where a state is represented by a tuple of three positive
integers (i,j,k), and you have three actions: decrease i by 1 (as long as i > 0), decrease j
by 1 (as long as j > 0), and decrease k by 1 (as long as k > 0). The goal state is (0,0,0).
Assume that a given search method does not revisit states it has already seen, and that
whenever there are multiple successors for a given state it first expands the state you get
from the action of decreasing i by 1 (if possible), then the action of decreasing j by 1,
then k.
a. What is the branching factor for this problem?
b. Is this state space a graph or a tree?
c. If the initial state is (2,2,2):
i. Draw the set of the state space that you can reach from this initial state.
Label the states with the upper-case letters A, B, C, …, from left to right,
top to bottom.
ii. List out the states with the upper-case letters A, B, C, …, to show the
order in which they would be expanded by depth-first search.
iii. List out the states with the upper-case letters A, B, C, …, to show the
order in which they would be expanded by breadth-first search.
iv. List out the states with the upper-case letters A, B, C, …, to show the
order in which they would be expanded by iterative deepening search.
d. If the initial state is (i,j,k), what is the time complexity, as a function of i, j, and k,
of:
i. Depth-first search
1
2
ii. Breadth-first search
4. Formulate Sudoku as a search problem. What are the states, actions, initial state, and
goal condition?
5. If h(s) is an admissible heuristic:
a. Is ℎ1(𝑠) = ℎ(𝑠)
0.7 an admissible heuristic?
b. Is ℎ2(𝑠) = ℎ(𝑠)
1.7 an admissible heuristic?
Please explain your answers.
6. Consider a graph with nodes A, B, C, D, E, F, G, and S. The start state is S and the goal
state is G. The edges in the graph are as follows: (A,B,4), (A,D,5), (A,S,2), (B,C,4), (B,E,6),
(B,F,3), (C,G,1), (D,E,3), (D,S,3), (E,F,4), (F,G,5). (The notation (A,B,4) means that there is
an edge between nodes A and B, and that the cost of traveling that edge is 4.)
Nodes should be expanded alphabetically if two or more nodes have the same evaluation cost.
Use the following table for the heuristic function:
n
S A B C D E F G
h(n) 10 7 3 1 5 4 2 0
Draw the graph first and then use Greedy Best First search to
a. List the nodes in the order they would be generated.
b. List the nodes that lie along the final correct path to the goal.
c. What is the cost of the solution? Is it optimal? Explain.
Requirements:
1. Type in your name, student number and class number (e.g., CS/SE-360 D?) at the top of
1
st page.
2. Use a word processor (e.g., MS word or others) to type your answers, save and print them
in hardcopy using A4 size papers and submit it to me on 18/3/2025 (for Tuesday Class),
19/3/2025 (for Wednesday class) and 20/3/2025 (for Thursday Class) in the class session.
3. Draw clearly the necessary diagrams as needed using a drawing tool.
4. For complexity analysis, represent it in terms of Big O.
5. All answers must be written in English. No Chinese answer is allowed.
請加QQ：99515681 郵箱：
[email protected] WX：codinghelp
