$3.$a$.$i $(1$ pt$)$ Is Breadth$-$First Search $($BFS$)$ an appropriate algorithm to use for finding the optimal solution path in the Rook Jumping Maze $($Yes$/$No$)?$ Why or why not?

YOUR ANSWER.

$3.$a$.$ii $(1$ pt$)$ Is Depth$-$First Search $($DFS$)$ an appropriate algorithm to use for finding the optimal solution path in the Rook Jumping Maze $($Yes$/$No$)?$ Why or why not?

YOUR ANSWER.

$3.$a$.$iii $(1$ pt$)$ Is Greedy Search an appropriate algorithm to use for finding the optimal solution path in the Rook Jumping Maze $($Yes$/$No$)?$ Why or why not? YOUR ANSWER.

$3.$a$.$iv $(1$ pt$)$ Is $\backslash (\backslash$Lambda$^\{*\}\backslash )$ Search an appropriate algorithm to use for finding the optimal solution path in the Rook Jumping Maze $($Yes$/$No$)?$ Why or why not? If you answered "Yes" describe how the heuristic works in your justification. YOUR ANSWER.

$3.$a$.$v $(1$ pt$)$ Is Value Iteration an appropriate algorithm to use for finding the optimal solution path in the Rook Jumping Maze $($Yes$/$No$)?$ Why or why not? If you answered "Yes", describe how the reward and transition functions work in words. YOUR ANSWER.

$3.$a$.$vi $(1$ pt$)$ Is Q$-$learning an appropriate algorithm to use for finding the optimal solution path in the Rook Jumping Maze $($Yes$/$No$)?$ Why or why not? If you answered "Yes", describe how the reward and transition functions work in words. YOUR ANSWER.

$3.$a$.$vii $(1$ pt $)$ Considering all of the above algorithms, which is the most appropriate to best find the optimal solution path? $($Hint: Consider completeness, finding the optimal solution path, efficiency, etc.$)$

YOUR ANSWER.

$3.$b$.(2$ pts$)$ Compute the average branching factor $($i$.$e$.,$ the average number of successors$)$ for the maze in the image above. You may express your answer as a fraction or a decimal.

YOUR ANSWER

$3.$c$.(3$ pts$)$ Suppose you wanted to use Breadth$-$First Search $($BFS$),$ Depth$-$First Search $($DFS$),$ Uniform Cost Search $($UCS$),$ or $\backslash (\backslash$Lambda$^\{*\}\backslash ),$ but you wanted to run the search from the goal to the initial state. That is: the cell labeled $\backslash ($ G $\backslash )$ is the initial state, and the cell with the circle is the goal state. To do this, you will need a predecessor function instead of a successor function. Describe in words how this predecessor function would work.

YOUR ANSWER

$3.$d$.(2$ pts$)$ Compute the average branching factor $($i$.$e$.,$ the average number of predecessors$)$ for the maze in the image above using your predecessor function. You may express your answer as a fraction or a decimal. $3.$e$.(3$ pts$)$ Given the choice between running the search forward from initial state to goal, or backward from goal to initial state, which would you choose, and why?

YOUR ANSWER