True or False:
Depth first search
is a complete search strategy.
DFID
guaranteed to find the shortest path to a goal node.
DFID
is guaranteed to terminate (assume that a goal node exists).
DFID
is just as fast as depth-first search.
DFID
requires less memory than best-first search.
The PageGather algorithm is an example of
unsupervised learning.
The version space algorithm is guaranteed
to terminate given enough examples and a finite hypothesis space.
(4 points) Draw a
game tree where the conspiracy number required to change the mini-max value at
the root from 4 to 6 is 2.
When
is a search procedure said to be {\em admissible}? Give an example of an admissible search procedure.
Game-playing
search (14 points)
Consider the following game tree. Assume it’s the maximizing player's
turn. Assume that $\alpha$/$\beta$ pruning of the
search tree is used.
The
labels on the leaf nodes are the static evaluations of each state.
max A
min B C D
max E F G H
I J K
L M N O
P Q R S T
U V W X Y Z
4 8 9 3
2 -2 9 -1 8
4 3 6 5 7
1
(3 points)
Prominently
label the nodes in the tree with their minimax values.
(1 points) Which move (ie, which node) would
be selected by Max?
(3 points) List the nodes that the
$\alpha$/$\beta$ procedure would prune away:
Suppose that we traverse the game tree from
right to left, instead of from left to right.
Is it possible that this will result in a change to:
The minimax value at the root?
The number of nodes pruned?
Suppose
POP adds the step puton(a ?X) to its plan, and that step threatens the causal
link puton(e d)-clear(b)--$>$puton(c b). State precisely {\em all} the
constraints POP could post to resolve this threat.
What
algorithm, heuristic or search strategy would you use to most effectively solve
the following problems:
(be
as specific and precise as you can be)
The
shortest path between two points in N-dimensional space
The
Horizon effect
Map
coloring
Learning
a concept whose description is some short Boolean formula
Learning
a concept in the presence of noise where the learned hypothesis have to be
examined by a person before they are accepted
Assigning
classes to rooms at UW based on enrollments, room sizes, and course meeting
times.