$1$ Breadth$-$First Search $($BFS$)3$ A$*$ Search

Consider the the graph from Question $1,$ where you are tasked with finding the shortest path from node

$A($the start node$)$ to node $O($the goal node$).$ The graph has uniform edge costs of $1$ for all edges. The

heuristic values $h(n)$ for each node are provided in the table below:

Table $1$: Heuristic values for each node in the graph. $3\mathrm{.}1$ Admissibility of the Heuristic

Based on the heuristic values given above, is the heuristic $h(n)$ admissible for this graph? Justify your

answer by checking whether the heuristic satisfies the admissibility condition for at all nodes in the graph.

$3\mathrm{.}2$ A$*$ search

Irrespective of your answer to $3\mathrm{.}1,$ assume that the heuristic is admissible. Apply the A$*$ search algorithm

to find the shortest path from node $A$ to node $O.$ Show the steps of the algorithm, including: $1.$ The

nodes expanded at each step. $2.$ The total cost $f(n)=g(n)+h(n)$ at each step for each expanded node.

The final path and its total cost.

Given the following graph, apply the Breadth$-$First Search $($BFS$)$ algorithm starting from node A$.$ Show

the order in which the nodes are visited. You can assume that ties are broken alphabetically.

$2$ Depth$-$First Search $($DFS$)$

Consider the same graph as in Question $1.$ This time, perform Depth$-$First Search $($DFS$)$ starting from

node A$.$ Show the order in which the nodes are visited. You can assume that ties are broken alphabetically.