Exercise $1(10$ points$).$ Consider the A$*$ algorithm using a perfect heuristic function h$,$ i$.$e$.,$ for any node $($state$)$ n$,$ h$($n$)$ equals the minimal cost from n to a goal state. Modify the pseudocode for A$^(**)($fig$.3\mathrm{.}7)$ so it improves in space and$/$or time complexity as much as possible. The better the solution the higher the grade. Explain your answer.

PLEASE WRITE THE ANSWER IN THIS PSEUDOCODE FORMAT

Pseudocode:

function BEST$-$FIRST$-$SEARCH$($problem$,$f$)$returns a solution node or failure node$$NODE$($STATE$=$problem.INITIAL$)$

frontier$$a priority queue ordered by f $,$with node as an element

reached$$a lookup table, with one entry with key problem.INITIAL and value node

while not IS$-$EMPTY$($frontier$)$do

node$$POP$($frontier$)$

if problem.IS$-$GOAL$($node$.$STATE$)$then return node

for each child in EXPAND$($problem$,$node$)$do

s$$child$.$STATE

if s is not in reached or child.PATH$-$COST $<mtext></mtext><mi></mi>$reached$[$s$].$PATH COST then

reached$[$s$]$child add

child to frontier

return failure

function EXPAND$($problem$,$node$)$yields nodes

s$$node$.$STATE

for each action in problem.ACTIONS$($s$)$do

s $$problem$.$RESULT$($s$,$action$)$

cost$$node$.$PATH$-$COST $+$problem$.$ACTION$-$COST$($s$,$action$,$s $)$

yield NODE$($STATE$=$s $,$PARENT$=$node, ACTION$=$action, PATH COST$=$cost$)$