Question

LGhemri Fall2018 3) Search Strategies: Drtmn Consider the map above. You are starting from Boynton Labs on the right and you want to go to the GROVES 1. 2. 3. WEAPONS ANNEX. Going to the city of ALDERWOOD after leaving the lab: Draw your scarch space using the breadth first search strategy. Find the number of nodes you will have to visit in order to get to your destination, list them. Draw your search space using a depth first search strategy. Find the number of nodes you will have to visit in order to get to your destination, list them. Which search strategy gives the smallest number of nodes visited before reaching your

Answer 1

Answering only the first question since there are multiple questions. Please check the names of the places since the image is blurred.

3) Search Strategies:

1. Using BFS we will explore one descendent layer at a time. First we will explore all the cities that are children of the node Boynton Labs and so on. So using BFS the visited nodes will be as Boynton Labs -> City of Alderwood -> Prado Cherries and Apples -> Rodriguez Apples -> Kazuhiri Apples and Grapes -> Dorfman Aspergus -> Gorves Weapons Annex. Hence the number of nodes visited is 7.

2. Using DFS we will move to the deepest layer and traceback when there is no more descndent and so on. From Boynton Labs first we will explore the city, City of Alderwood which is a must as per the question. And then go to its leftmost child, i.e., US Gov and so on. Therefore using DFS the visited nodes will be as Boynton Labs -> City of Alderwood -> Prado Cherries and Apples -> US Gov -> Rodriguez Apples -> Kazuhiri Apples and Grapes -> Dorfman Aspergus -> Gorves Weapons Annex. Hence the number of nodes visited is 8.

3. BFS provides the smallest number of nodes visited before reaching the destination.