Artifical intelligence

A* algorithm

Question

A)

B)

Note:

provide complete working for each and every step performed for both parts

Consider the following map (not drawn to scale) B 12 19 11 20 17 10 K 15 15 M Part a) Use A algorithm to work out a route from town A to town M. Use the following cost functions g(n) = Total cost of reaching from town A to town n (step cost of each move is given on the map) h(n) = Straight line distance between town n and town M These costs are given in the table below. h(n) can be used as an estimated distance to M Town Distance Town Distance A 56 H 10 B 22 1 8 30 J 5 D 29 K 30 E 29 L 15 F 30 M 0 G 14 i) ii) Showing the order of nodes expanded by A* (Show complete working on the next page) What path/route would be found by A* using this heuristic function? Part b) Repeat the above question for the following heuristic function Town B D E Distance 80 10 50 Town H I J K L M Distance 30 20 50 20 60 10 20 0 F G 30 60