A grid of 48 squares (6 rows by 8 columns) is numbered 0 to 47, row by row. Square 7 is marked GO (t ...

---

A grid of 48 squares (6 rows by 8 columns) is numbered 0 to 47, row by row. Square 7 is marked GO (the goal) and square 40 is marked START. The squares numbered 8 to 11, 16 to 19, 13, 23, 30, and 34 to 37 are filled in black and are blocked. (1) Write out the steps of Dijkstra's algorithm on this grid (8-connected; diagonal edge cost = 1.5, horizontal and vertical edge cost = 1). At each step, list the grid cells in the open set with their running cost and the cells in the visited set, and write the final path as a list of grid cell ids. Then write out the steps of the A* algorithm (8-connected, assume uniform action cost), listing at each step the open set with f-costs (use Manhattan distance to the goal as the heuristic, assigning Cartesian coordinates with the start at (0, 0), so the goal is at (7, 5)) and the visited set, and write the final path as a list of cell ids. (2) Give one main difference between A* and Dijkstra's algorithm. (3) Which single data structure can be used to improve the performance of both algorithms? (4) Which algorithm (A* or Dijkstra's) returns an optimal path?