Q$3.(4$p$)$ A simple sliding$-$tile puzzle consists of $3$ numbered tiles and an empty space. The puzzle has two

legal moves with associate costs: $($i$)$ A tile may move into an adjacent empty location. This has a cost

of $1.($ii$)$ A tile can move over one other tile into the empty position. This has a cost of $2.$ The start

and goal positions are given below. Set up a state$-$space search formulation for this puzzle:

a$)$ Specify the form of state descriptions, the starting state, and the goal state for this problem.

b$)$ Name the operators on states and describe what each operator does to a state description.

c$)$ Propose a heuristic function hat$(h)$ for solving this problem.

d$)$ Use the $A^{*}$ algorithm to find a solution path using your heuristic function. You can either show

the search tree or the state of the priority queue as $A^{*}$ progresses.

e$)$ Is your solution path optimal? Give a formal argument.In this question you will use three informed search algorithms to find the path between AIn this question you will use three informed search algorithms to find the path between A

and G in the graph below: $($a$)$ Uniform Cost Search, $($b$)$ Best$-$first Search, and $($c$)$ A$$

search.

and G in the graph below: $($a$)$ Uniform Cost Search, $($b$)$ Best$-$first Search, and $($c$)$ A$$

search.