Figure 2 Polygon 1: ((220, 616), (220, 666), (251, 670), (272, 647) Polygon 2: (341, 655), (359, 667), (374, 651). (366, 577) Polygon 3: ((311, 530). (311, 559), (339, 578), (361, 560), (361, 528), (336, 516)) Polygon 4: (105, 628), (151, 670), (180, 629), (156, 577), (113, 587) Polygon 5: (118, 517), (245, 517), (245, 577), (118, 557) Polygon 6: ((280, 583), (333, 583), (333, 665), (280, 665) Polygon 7: ((252, 594), (290, 562), (264, 538)) Polygon 8: ((198, 635), (217, 574), (182, 574) Note: This figure is for illustration purpose only. Positions of the polygons inside the figure may not reflect their actual coordinates. 3) Implement an algorithm to find the shortest path from the start node to the end node using A* (A-star) heuristic search. Use the straight-line distance to the end node as a heuristic funct Show your pseudo code for this algorithm. Is this an admissible heuristic function? Why or why not? [15 points] Hint: Define the necessary functions to implement the search problem. This should include a function that takes a vertex as input and returns the set of vertices that can be reached in a straight line from the given vertex. You may need to implement a function that detects whethe or not two line segments intersect. The problem can be solved using shortest path algorithms b you are required to use A*. 4) Present the solutions for the following pair of starting point and ending point using the A* algorithm you implemented. Show the optimal path. [15 points) Start: (115, 655) End: (380, 560) 5) Is it possible to solve the problem using a breadth-first or a depth-first search algorithm? If answer is yes, briefly discuss your solutions. Otherwise please explain. [10 points)