Question 4
SEARCH
The figure shows a map on a uniform grid where each tile is 1x1 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in alphabetical order.
Use Manhattan Distance as the heuristic function.
Tie-breaker: If several nodes have the same cost, use node labels to break the tie.
Based on the above data, answer the given subquestions.
What is the path found by Branch-and-Bound search algorithm? Enter the path as a comma separated list of node labels.
Use the Branch-and-Bound variation that avoids cyclic expansions like S,F,S,F,S,F,...
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z,G