Prune Juice

Consider a uniform grid that extends infinitely in all directions.

We start out at the grid point marked S. Assume the goal is far away and not shown in the figures.

Click here to open the graph in a new window.

In the grid on the left, each state has four child states (movement on the grid is limited to up, down, left, and right). In the one on the right, each state has eight children (diagonal moves are allowed).

In this problem, we will examine the effects of various pruning strategies on breadth-first search.

Case 1: No Pruning

Answer the following questions about breadth-first search with no pruning (not even Pruning Rule 1).

In the left-most grid, how many paths of length 1 are ever added to the agenda?

In the left-most grid, how many paths of length 2 are ever added to the agenda?

In the right-most grid, how many paths of length 1 are ever added to the agenda?

In the right-most grid, how many paths of length 2 are ever added to the agenda?

Case 2: Pruning Rule 1

Answer the following questions about breadth-first search with Pruning Rule 1, which prunes from the tree paths that contain any state more than once.

In the left-most grid, how many paths of length 1 are ever added to the agenda?

In the left-most grid, how many paths of length 2 are ever added to the agenda?

In the right-most grid, how many paths of length 1 are ever added to the agenda?

In the right-most grid, how many paths of length 2 are ever added to the agenda?

Case 3: Dynamic Programming

Answer the following questions about breadth-first search with Dynamic Programming, which never visits any state more than once.

In the left-most grid, how many paths of length 1 are ever added to the agenda?

In the left-most grid, how many paths of length 2 are ever added to the agenda?

In the right-most grid, how many paths of length 1 are ever added to the agenda?

In the right-most grid, how many paths of length 2 are ever added to the agenda?