Complete all of the exercises 3.A, 3.B, 3.C, 3.D, and 3.E. For the exercises proscribed below you must also complete the additional instructions provided and submit as part of your assignment.

You will be using the graph search tool on the AISpace web site to complete these assignments. There is a tutorial on using the tool at http://www.aispace.org/search/index.shtml

Complete exercise 3.A. As part of your assignment you must provide a reflective statement that indicates what you learned as part of the exercise (Assignment part A). You statement must be at least 200 words in length. Statements under this length will receive less points.

http://www.aispace.org/exercises/exercise3-a-1.shtml

Complete exercise 3.B. As part of your assignment, provide a response IN YOUR OWN WORDS to the following questions. (Assignment part B)

http://www.aispace.org/exercises/exercise3-b-1.shtml

What is meant by search algorithm completeness?

What is meant by search algorithm optimality?

What are the advantages of breadth-first search (BFS) over depth-first search (DFS)?]

What is the advantage of DFS over BFS?

Consider the search problem represented in the following figure, where a is the start node and f is the goal node. Would you prefer DFS or BFS for this problem? Why?

Which sequences of paths are explored by BFS and DFS in this problem?

Complete exercise 3.C. As part of your assignment, provide a response IN YOUR OWN WORDS to the following questions. (Assignment part C)

http://www.aispace.org/exercises/exercise3-c-2.shtml

What is the distinction between informed and uninformed search?

What is a heuristic?

When is a heuristic admissible?

A* can be seen as a combination of what two search strategies?

Consider the search problem represented in the following figure, where a is the start node and e is the goal node. The pair [f, h] at each node indicates the value of the f and h functions for the path ending at that node. Given this information, what is the cost of each arc? The cost = 2 is given as a hint

Is the heuristic function h admissible? Explain why or why not.

Trace A* on this problem. Show what paths are in the frontier at each step.

Complete exercise 3.D. As part of your assignment, you must provide a reflective statement that documents your findings about the various search approaches to include your observations, which forms of search were more efficient and which less efficient for the Vancouver neighborhood graph and why? You statement must be at least 200 words in length. Statements under this length will receive less points. (Assignment part D)

Complete exercise 3.E. As part of your assignment, provide a response IN YOUR OWN WORDS to the following questions. (Assignment part E)

http://www.aispace.org/exercises/exercise3-e-1.shtml

In branch and bound (B&B), how is the upper bound (UB) calculated?

How is the lower bound (LB) calculated for a path?

With B&B, when do we prune a path?

What is the UB when only the start node has been explored?

Which goal node is found first by B&B?

What is the UB immediately after the first goal node is found?

Is the second goal found by B&B?

Rubric

For each part of the assignment (A-E) rate the completeness on a scale of 1 5 where one indicates that the question was either not answered or the answer did not respond to the question to 5 where there was a complete response to the question.