FFigures 5 and 6 show maps where all the towns are on a grid. Each town T has coordinates (Ti, Tj), where Ti Tj are non-negative integers. We use the term Euclidean distance for the straight-line distance between two towns, and the term driving distance for the length of the shortest driving route connecting two towns. The only roads that exist connect towns that have Euclidean (straight-line) distance 1 from each other (however, there may be towns with Euclidean distance 1 from each other that are NOT directly connected by a road, for example in Figure 4). Consider greedy search, where the node to be expanded is always the one with the shortest Euclidean distance to the destination [h(n) where h(n) is the Euclidean distance from n to the destination]. Also consider A* search where the next node to expand is picked f(n) = g(n) + h(n) [when g(n) is cumulative actual road distance between start and n]. For each of the maps showing on Figures 3 and 4, which of the following statements is true?

• Greedy search always performs better than or the same as A*, depending on the start and end states.
• Greedy search always performs worse than or the same as A*, depending on the start and end states.
• Greedy search performs sometimes better, sometimes worse, and sometimes the same as A*, depending on the start and end states.
• Greedy search always performs the same as A*, irrespective of the start and end states.

Justify your answer. For the purposes of this question, the performance of a search algorithm is simply measured by the number of nodes visited by that algorithm. Note that you have to provide separate answers for Figure 5 and for Figure 6.

0,0-0,10,2 0.30,40,5- 0,7 - 0,8 1,11,21,3 1,61,7_ 1,8 2,02,12,2 2,3 2.4 2,5- 2,6 2,7- 2,8 3,0 3,1-3,2 3,3 3,4 3,5 3,6 3,73,8 4,04,1-4,2 4.4-4,5- 4,6- 4.7 5,0 5,1 5,2 5,3 5,45,5 5,6-5,7-5.8 6,0._ 6,16,2-6,3 6,46.5 6,6- 6,7 -6,8 7,07,1 7,2 7,37,4 7,6 7,7 7,8 8,0 8,3 8,4-8,5 8,6 8,78,8 - 0,0_0,1 0.20.3 0,40,5 0,60,70,8 1,6-1,7 1,8 2,02.1 2,2- 2,32,4 2,42,5 -2,6 2.7 2,8 3.03,1 3,2 3,3,-, 3,4 3,5 3,6 3,7 3,8 ,2-- 4,3 4,4- 4,5 4,7-4,8 5,05,1-5,2 5,3, 5,4 5,5 5,6 .. 5,75,8 6,0 6,1 6,2 6,46.5 6.66,7 - 6,8 7,3 7,4 7,5 7,6 7,7 7,8 8,0 8,18,2- 8,3 8,4-8,5 8,6 _ 8,7_8,8