CMPUT 366: Assignment #1

1

[15 points] Construct a search graph with no more than 10 nodes for which all of the following are true:

1. Least-cost first search returns an optimal solution.

2. Breadth-first search returns the highest-cost solution.

3. Depth-first search returns a solution whose cost is strictly less than the highest-cost solution and strictly

more than the least-cost solution.

Feel free to include multiple goal nodes in your graph. Be sure to list the start and goal node(s), all edge costs

and all edge directions (if your graph is directed). Draw the graph as well.

2

[5 points] List the paths that are removed from the frontier by a depth-first search of the search problem you gave

for Question 1, in the order in which they are removed from the frontier. Stop the trace when the path removed

ends in a goal state.

2

3

[5 points] List the paths that are removed from the frontier by a breadth-first search of the search problem you

gave for Question 1, in the order in which they are removed from the frontier. Stop the trace when the path

removed ends in a goal state.

4

[5 points] List the paths that are removed from the frontier by a least-cost first search of the search problem you

gave for Question 1, in the order in which they are removed from the frontier. Stop the trace when the path

removed ends in a goal state.

5

[2 points] Come up with a solvable four-node search graph on which greedy best-first search (PM 3.6) never

reaches the goal. The four nodes should include the start node and the goal node. Draw the four-node graph

below. Label each edge with its cost and each node with its heuristic value. The heuristic must be admissible.

Mark the start node and the goal node.

6

[2 points] Trace the greedy best-first search on the search problem you came up with for Question 5 and list the

paths that get removed from the frontier. Stop the trace after showing that the algorithm will never reach the

goal node.

3

7

[6 points] A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right

using a raft. The farmer can take one item at a time (hen, fox, or bushel of grain) using the raft. The hen cannot

be left alone with the grain, or it will eat the grain. The fox cannot be left alone with the hen, or it will eat the hen.

For example, the farmer cannot move from one side x of the river to the other side y if it would mean leaving

the fox and hen together on side x. The farmer can load an item onto the raft, move the raft from one side of the

river to the other, or unload an item from the raft. The farmer wants to move the items with the fewest number

of trips across the river as possible.

Classify this problem using the primary representational dimensions covered in the lectures.

8

[20 points] Represent the problem in Question 7 as a graph search problem: define the set of states/nodes, the

start node, the goal node(s). Define the edges via defining neighbours of each state obtained via the farmer’s

actions. Define costs of each edge. You do not have to draw the graph or explicitly list all nodes and edges.

4

9

[5 points] What is the branching factor for your graph from Question 8? Justify your answer.

10

[10 points] Construct a non-constant admissible heuristic for the problem in Question 7.

11

[5 points] Prove that your heuristic for Question 10 is indeed admissible.

5

12

[60 points] Implement your representation from Question 8 and heuristic from Question 10 in Python 3 by editing the River_problem class in the provided riverProblem.py. We will run your code with the command

python3 riverProblem_run.py. Your code must complete within 2 minutes for full marks.1

Submit all of your code (including provided boilerplate files) in a single zip file.

Submission

The assignment you downloaded from eClass is a single ZIP archive which includes this document as a PDF and its

LATEX source as well as Python files needed for Question 12. You are to unzip the archive into an empty directory,

work on the problems and then zip the directory into a new single ZIP archive for submission.

Each assignment is to be submitted electronically via eClass by the due date. Your submission must be a single

ZIP file containing:

1. a single PDF file with your answers;

2. file(s) with your Python code.

To generate the PDF file with your answers you can do any of the following:

• insert your answers into the provided LATEX source file between \begin{answer} and \end{answer}.

Then run the source through LATEX to produce a PDF file;

• print out the provided PDF file and legibly write your answers in the blank spaces under each question. Make

sure you write as legibly as possible for we cannot give you any points if we cannot read your hand-writing.

Then scan the pages and include the scan in your ZIP submission to be uploaded on eClass;

• use your favourite text processor and type up your answers there. Make sure you number your answers in

the same way as the questions are numbered in this assignment.

1

It should really run in far less time than this.

6

Sale!