1. Search

Figure 1: Search problem description

Imagine we are living the real scene in a science fiction movie in which aliens have launched attacks to our cities. Aliens also cut off all the phone, Internet, electricity and so it forces us to use our memory and common sense to navigate through our cities to safe shelters. Assuming that we are at downtown area (S) and the safe shelters are at location T. Figure 1 above shows how the streets are connected with each other. The edges are labelled with distances and the nodes are labelled with a heuristic estimate to the destination T. When performing search, ties are broken by choosing the node that is alphabetically first.

1.1 Show a path if using Breadth First Search and a path if using Depth First Search

1.2 Show a path using Best First Search and a path using A* search. Would you find any path returned by A* the same with a path returned by a Best First Search? Why/Why not?