Opening the paper…
AI: Search Methods for Problem Solving, Quiz 2
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.) Arc of nodes S, A1, A2, A3, A4, … with edge costs 1/2, 1/4, 1/8, 1/16 and dashed links to G, plus a direct S–G edge of cost 3 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.) Arc of nodes S, A1, A2, A3, A4, … with edge costs 1/2, 1/4, 1/8, 1/16 and dashed links to G, plus a direct S–G edge of cost 3 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.) Arc of nodes S, A1, A2, A3, A4, … with edge costs 1/2, 1/4, 1/8, 1/16 and dashed links to G, plus a direct S–G edge of cost 3 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?