Answer Happy

45m 47m 49m 54m 61m 50m 32m 47m 48m 38m 50m 49m 66m 37m 46m 24m 28m 48m 55m 42m 32m 49m 68m 55m 9m T 51m 31m 36m 63m 46m 53m 75m 36m 57m 37m 60m 25m 50m 9m
-The map above shows measured travel times (in minutes) between towns in a part of South Africa. The table on the right shows straight-line distances (SLD) from each town to M (Mahikeng). An algorithm needs to plan a route from some starting point to the goal state M. The programmer proposes to calculate a heuristic value as follows: Use the straight-line distance from a node to Mahikeng and assume that the distance is travelled at an average speed of 100km/h (100km/60min) to estimate the amount of minutes from that node to the goal. 7.1) Is the heuristic admissible? Motivate your answer. (2) 7.2) Can the heuristic be simplified to use the SLD only? Motivate your answer. (2) 7.3) Draw the search tree for best-first search from P to M using the proposed heuristic. Label the nodes with the letter, the path length up to there, the heuristic value and the total estimate at that point. (8) 7.4) What is the route that the algorithm calculated from P to M? (1) 7.5) What are the heuristic value at P and the actual travel time from P to M. Which value was expected to be bigger? (3) TOWN A Carletonville B Brits C Coligny D Ditsobotla E VEntersdorp F RandFontein G| MaGaliesburG H Sannies Hof Koster K L Lichtenburg N O Ottosdal P Q Klerksdorp R Rustenburg S Sasolburg T Tarentaal V Vanderbijlpark W Swartruggens Y Parys Z Zeerust Nooitgedacht Potchefstroom SLD (km) to Mahikeng 229 266 105 121 160 260 237 95 153 63 41 141 214 188 199 304 222 303 130 269 69