I have a few more updates about Problem Set 1:
1.) As Geoff mentioned in class today, we now recognize that we
under-specified the expansion rule for A* in problem 1a.) by not
standardizing a method of tie breaking when two nodes have the same
f(n) value. When this occurs we ask that you break ties in the following way
to ensure that there is a unique solution (since we did not
specify this on the handout, if you have already handed in your
homework we will not deduct points for other methods of tie breaking).
Given two nodes, n and n' such that f(n) = f(n'), if n and n' are in different
rows choose the one that is North of the other, if n and n' are in
the same row choose the one that is West of the other. Here is an
example picture to illustrate, let f(A)= f(B) = f(C) = f(D),
------------------------------
| A | ... | C |
| B | ...
... | D |
------------------------------
You should expand the nodes in the following order, A->C->B->D.
2.) With regard to problem 1b.), one student asked "Should/Can we use
a visited list for our DFS algorithm to keep track of which spaces we
have already searched?" The truth is there are good reasons to
implement DFS with or without a visited list, how you choose to do it
on the homework is up to you, but please justify your decision.
3.) With regard to the same problem (1b.) another student asked "I
don't want to use the priority queue implementation you provided, can
I use my own implementation?" As we mentioned on this homework
priority queue implementation does not really fall within the scope of
our class (which is why we provided the data structure to you) so we
do not care how you ascertain the order of nodes to visit as long as
it works correctly. However, keep in mind that in any real
application a poorly implemented sorting data structure can add a
significant amount of unnecessary computational effort.
4.) Finally I have a policy note about homework solutions. Rather
than handing out TA generated solutions to the coding problems on the
homework we will choose one student solution that we deem to be
particularly elegant/efficient. This solution will be distributed via
the course website as the official solution, so do your best coding.
5.) An additional clarification,
Someone asked about problem 3b.) "How exactly do I graph q1 - q2?" This is
meant to be a graph with q1 on the x-axis and q2 on the y-axis (q1 vs. q2)
showing each point on the edge of the arm's c-space. In other words, the
graph should have points at the largest valid values of q1 and q2 (think about
how this is related to the intersection test we ask you to perform). In
Matlab you might want to plot this using the image show command ("imshow").