uniform cost serach implementAssume the following graph represents the future options you have after you graduate from SQU.

Assume the start node is S SQU and your goal node is R $=$ Retire, with different options in between for

what you can do between you graduate from college and retirement.

The edge distances represent, roughly, the "cost of transition" between different careers. You also have

heuristics of node$-$to$-$goal distances which roughly represent the number of years you have to work until

you retire. For example, it may take $25$ years to go from SQU $($S$)$ to retirement $($R$)$ while it may roughly

take $30$ years from Grad School $($B$)$ to retirement, but only $2$ years from being an Entrepreneur $($E$)$ to

retirement $($R$).$

$A=$ Industry $|B=$ Grad School $|C=$ Professor Job $|D=$ Government $|E=$ Entrepreneur

Use alphabetical order to break ties when deciding the priority to use for extending nodes.Part$1$: Answer the following questions and provide the answer in a PDF file named part$1\_$ID$.$pdf

$[1$pts$]$ Using a basic $($uninformed$)$ search algorithm you learned in this course, find a path

with the minimum search efforts to go from $S$ to $R.$ What algorithm did you decide to use?

$[2$pts$]$ Using the algorithm you chose in the previous part, draw the search tree and

$[1$pts$]$ give the final path $.$

$[4$pts$]$ Use $A^{**}$ to find a path from $S$ to $R.$ Use this space to draw the corresponding search

tree and show your work. $[1$pts$]$ What is the path cost?$[1$pts$]$ Is the provided heuristics to the goal admissible? Explain your answer.

Part$2.$ Write a Python program to implement Breadth$-$first$-$Search, Depth$-$first$-$Search, Uniform$-$Cost

Search, Hill$-$Climbing, and $A^{**}$ algorithms while considering the following requirements:

Use appropriate data structure for the search graph.

Implement a function $($or method$)$ to find the neighbor$($s$)$ of a node in the graph.

Display the result of each iteration $($frontier and expanded nodes$).$

Display the path found given any start state and goal state.

Display the path cost.

Submit all the solution files of your implementation

For optimal search algorithms, you need to consider the edge cost.

Submission instructions:

Create a folder and name it hw$1\_$ID$,$ where ID is your student ID$.$