Homework 3: Searches
You will get the opportunity to code up the
standard search algorithms while doing the search lab. In
this assignment, you will experiment with some of the more advanced
searches, such as iterative searches, a learning-based search,
and various local searches.
- Problem 3.11 parts a, b, and c.
- Suppose your implementation of Iterative Deepening takes 10
times
as
much space per node as your Bidirectional implementation. If b=3 at
what depth (d) should you switch algorithms assuming you are motivated
only by space concerns.
- Consider the following graph. In the
graph, o
is the origin (all trials start
from this state) and g
is the
goal
(all trials end in
this state). Show what the heuristic values for each state (o,a,b,c,d,g) are
after one trip
(one episode) from the origin to the goal when the LRTA* algorithm is
used. Initially, all heuristics are set to 0. When
there is a tie,
choose the node which comes first in the alphabet.
Repeat
and show what the heuristic values for each state are after a second
trip (two episodes) from the origin to the goal when the LRTA*
algorithm is used.
- Apply some of the steps for using
a gradient ascent algorithm to find the maximum of a function. Consider
the function f(x, y)
= x3y − 2xy2 +
x − 4.
If we use gradient ascent beginning at (x0, y0) = (1,−1) and
a
“stepping” factor of k = 0.1,
what values of (x, y) will be reached after one step? Recall that
gradient ascent computes the
step direction by creating the vector of partial derivatives.