Opening the paper…
Quiz Space
Question 1
SEARCH
Figure shows an infinite state space with finite branching, where S is the start node and G is the goal node, and G is at the center of a unit circle, and the remaining nodes are on the unit circle. (Note: circular grid is shown by dashed lines which are not part of the state space.)
Take the radial distance as the heuristic value:
h(G)=0; h(S)=1; and h(Ak)=1, for all k in {1, 2, . . .}.
MoveGen returns neighbours in alphabetical order (A1,A2,..., G,S).
Tie-breaker: use alphabetical order to break ties.
Note: sum(1, a, a^2, a^3, ..., a^(n-1)) is given by ((1 - a^n)/(1 - a)).
Based on the above data, answer the given subquestions
Does the Breadth First Search find the path to the goal?
**SEARCH**\ Figure shows an infinite state space with finite branching, where S is the start node and G is the goal node, and G is at the center of a unit circle, and the remaining nodes are on the unit circle. (Note: circular grid is shown by dashed lines which are not part of the state space.) Figure from the passage in the original paper Take the radial distance as the heuristic value:\ h(G)=0; h(S)=1; and h(Ak)=1, for all k in \{1, 2, . . .\}.\ MoveGen returns neighbours in alphabetical order (A1,A2,..., G,S).\ **Tie-breaker:** use alphabetical order to break ties.\ **Note:** sum(1, a, a^2, a^3, ..., a^(n-1)) is given by ((1 - a^n)/(1 - a)).\ Based on the above data, answer the given subquestions Does the Breadth First Search find the path to the goal? **SEARCH**\ Figure shows an infinite state space with finite branching, where S is the start node and G is the goal node, and G is at the center of a unit circle, and the remaining nodes are on the unit circle. (Note: circular grid is shown by dashed lines which are not part of the state space.) Figure from the passage in the original paper Take the radial distance as the heuristic value:\ h(G)=0; h(S)=1; and h(Ak)=1, for all k in \{1, 2, . . .\}.\ MoveGen returns neighbours in alphabetical order (A1,A2,..., G,S).\ **Tie-breaker:** use alphabetical order to break ties.\ **Note:** sum(1, a, a^2, a^3, ..., a^(n-1)) is given by ((1 - a^n)/(1 - a)).\ Based on the above data, answer the given subquestions Does the Best First Search find the path to the goal? **SEARCH**\ Figure shows an infinite state space with finite branching, where S is the start node and G is the goal node, and G is at the center of a unit circle, and the remaining nodes are on the unit circle. (Note: circular grid is shown by dashed lines which are not part of the state space.) Figure from the passage in the original paper Take the radial distance as the heuristic value:\ h(G)=0; h(S)=1; and h(Ak)=1, for all k in \{1, 2, . . .\}.\ MoveGen returns neighbours in alphabetical order (A1,A2,..., G,S).\ **Tie-breaker:** use alphabetical order to break ties.\ **Note:** sum(1, a, a^2, a^3, ..., a^(n-1)) is given by ((1 - a^n)/(1 - a)).\ Based on the above data, answer the given subquestions Does the Branch and Bound algorithm find the path to the goal?