Homework 1 Informed and Uninformed Search

40 pts total
1 Defining a Problem
Consider the farmer, sheep, dog, and cabbage problem we discussed in class.
(Refer to the slides for the exact problem specification.) Answer each of the
following.
1.1 State Space
(2 pts) Describe the state space to this problem. What would the initial
state be?
1.2 Possible Actions
(2 pts) Given a general state s, describe what an action means. Given the
state (CD, FS) (i.e., the cabbage and the dog are on the left side of the river,
and the farmer and sheep are on the right side), give a valid action.
1.3 Transition Model
(2 pts) Given a general state s, describe what the transition model returns.
Given the action you named above, what would the transition model return?
1.4 Goal Test
(2 pts) Given a general state s, describe what the goal test returns.
1.5 Path Cost
(2 pts) What would a potential path cost be, and what would it mean in
terms of the search?
22 Uninformed Search
Figure 1: Question 2, 3 Graph
Given the above graph in Figure 1, assume node S is the start state and
nodes K, M, and N are goal states. Execute each of the following search
algorithms like we did in class. Assume expansion happens from left to right.
If you encounter a tie, expand the node that comes first alphabetically (e.g.,
B before D). For full credit, be sure to show the Expanded (2 pts) and
Frontier (2 pts) node lists at each step. Give the final path to the solution
you found, along with the corresponding total cost (1 pt for both).
2.1
(5 pts) Breadth-First Search (BFS)
2.2
(5 pts) Depth-First Search (DFS)
32.3
(5 pts) Uniform-Cost Search (UCS)
2.4
(5 pts) Iterative-Deepening Search (IDS)
3 Informed Search
Refer once more to the graph in Figure 1. Assume the values for the heuristic
function h(n) are those listed in Table 1, where nodes K - N all have value
4. Assume once more that S is the start state. This time, assume node J is
the goal state. Execute each of the following search algorithms like we did in
class. Assume expansion happens from left to right. If you encounter a tie,
expand the node that comes first alphabetically (e.g., B before D). For full
credit, be sure to show the Expanded (2 pts) and Frontier (2 pts) node lists
at each step. Give the final path to the solution you found, along with the
corresponding total cost (1 pt for both).
Node S A B C D E F G H I J K - N
h(n) 5 1 7 1 3 4 1 1 4 1 2 4
Table 1: Heuristic Function Values
3.1
(5 pts) Greedy Best-First Search
3.2
(5 pts) A* Search
4