Q13 Lookahead Graph Search Recall from lecture the...

Q13 Lookahead Graph Search Recall from lecture the general algorithm for Graph Search reproduced below.Using GRAPH-SEARCH, when a node is expanded it is added to the closed set. This means that even if a node is added to the fringe multiple times it will not be expanded more than once. Consider an alternative version of GRAPH-SEARCH, LOOKAHEAD-GRAPH-SEARCH, which saves memory by using a "fringe-closed-set" keeping track of which states have been on the fringe and only adding a child node to the fringe if the state of that child node has not been added to it at some point. Concretely, we replace the highlighted block above with the highlighted block below.Now, we've produced a more memory efficient graph search algorithm. However, in doing so, we might have affected some properties of the algorithm. To explore the possible differences, consider the example graph below.Q13.1 If using LOOKAHEAD-GRAPH-SEARCH with an A* node expansion strategy, which path will this algorithm return？ (We strongly encourage you to step through the execution of the algorithm on a scratch sheet of paper and keep track of the fringe and the search tree as nodes get added to the fringe.)

A、S→A→D→G

B、S→B→G

C、S→A→C→G

D、S→B→D→G