Comparing Searches

In this exercise, we will consider the following graph:

Click here to open the graph in a new window.

• the start state is S
• the goal state is G
• children are pushed onto the agenda in reverse alphabetical order. The first three paths pushed onto the agenda after S (our initial path) are SF, SE, and SD, in that order. Notice that, depending on whether we are running BFS or DFS, the order in which paths are popped off the agenda will be different.

Enter any paths as a sequence of state names, with no punctuation, e.g. ABCD

Part 1: DFS with Pruning Strategy 1

In this first part, we will consider searching on this graph using depth-first search, and using the following pruning strategy:

• prune paths that contain any state more than once

1.1 Agenda

In the boxes below, enter the sequence of partial paths that are pushed on to the agenda using this strategy. If there are more boxes than are required, enter None in any boxes you do not need.

1. S
2. SF
3. SE
4. SD
5. 
6. 
7. 
8. 
9. 
10. 

1.2 Final Path

What is the final path found using this strategy?

Part 2: DFS with Dynamic Programming

Now we will consider searching on this graph using depth-first search, and using the following pruning strategy (the dynamic programming principle):

• never visit any state more than once

2.1 Agenda

In the boxes below, enter the sequence of partial paths that are pushed on to the agenda using this strategy. If there are more boxes than are required, enter None in any boxes you do not need.

1. S
2. SF
3. SE
4. SD
5. 
6. 
7. 
8. 
9. 
10. 

2.2 Final Path

What is the final path found using this strategy?

Part 3: BFS

Now we will consider searching on this graph using breadth-first search.

3.1 Agenda

In the boxes below, enter the sequence of partial paths that are pushed on to the agenda using BFS, regardless of which pruning strategy is used. If there are more boxes than are required, enter None in any boxes you do not need.

1. S
2. SF
3. SE
4. SD
5. 
6. 
7. 
8. 
9. 
10. 

3.2 Final Path

What is the final path found using this strategy?