Write a Java program to implement an $\backslash (\backslash$mathrm$\{$A$\}^\{*\}\backslash )$ search algorithm for a goal$-$based agent to find the cheapest path from the start state to one of the goal states. Use the search space example in Figure $2\mathrm{.}1$ to test your program.

Figure $2\mathrm{.}1$: Search Space Example. A is the start state. G$1,$ G$2,$ and G$3$ are three goal states. The numbers in the black squares are the heuristic values which indicate the estimate cost between the state and the goal state. The numbers on the arcs indicate the path$-$cost between two states. Follow the instructions below during the implementation of your software program.

$1.$ The actual path$-$cost values in the search space is entered to the java program as an $\backslash (\backslash$mathrm$\{$n$\}\backslash$times $\backslash$mathrm$\{$n$\}\backslash )$ square matrix, as shown in the template program at the end of the assignment.

$1.$ For example: The search space in Figure $2\mathrm{.}1$ below is represented by the following $\backslash (10\backslash$times $10\backslash )$ matrix

$2.$ The heuristic values of all states are represented by an $\backslash ($ n $\backslash )-$size vector, as shown in the template program at the end of the assignment.

$-$ For example, the heuristic vector of the search space in Figure $2\mathrm{.}1$ is represented by the following vector:

$-\backslash (\backslash$mathrm$\{$S$\}=\backslash \{5,7,3,4,6,8,5,0,0,0\backslash \}\backslash )$

$3.$ The program uses $\backslash (\backslash$mathrm$\{$A$\}^\{*\}\backslash )$ search algorithm to find the cheapest path from the start state to one of the goal states. The goal states are the ones with $0$ value in the heuristic vector. $4.$ The software program should print out the cheapest path, the goal state, and the number of cycles it took to reach the final goal state.

Use the template below:

$```$

public class MyClass $\{$

public static void main$($String args$[])\{$

int$[][]$ cost$\_$matrix $=\{\{0,0,0,6,1,0,0,0,0,0\},$

$\{5,0,2,0,0,0,0,0,0,0\},$

$\{9,3,0,0,0,0,0,0,0,0\},$

$\{0,0,1,0,2,0,0,0,0,0\},$

$\{6,0,0,0,0,2,0,0,0,0\},$

$\{0,0,0,7,0,0,0,0,0,0\},$

$\{0,0,0,0,2,0,0,0,0,0\},$

$\{0,9,0,0,0,0,0,0,0,0\},$

$\{0,0,0,5,0,0,0,0,0,0\},$

$\{0,0,0,0,0,8,7,0,0,0\}\}$;

int$[]$ heuristic$\_$vector $=\{5,7,3,4,6,8,5,0,0,0\}$;

$//$ Identify the Goal States and save them in a new vector

$//$ Write a program to implement the A$*$ search

$//$ Print the cheapest path, the goal state and the number of cycles

$\}$

$\}$

$```$