Assignment #1 Construct a search graph

CMPUT 301: 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