AI Search Methods End Term: 13 September 2026, Set 1 (May 2026 term)

SEARCH
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit squares each 1m x 1m. The grid (intersection points and unit sides) forms a graph (nodes and undirected edges). Start node (S) is at the center of the plane. Goal node (G) is at the north east corner of the plane. MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South]. Take h(X) as the square of the Euclidean distance.

Answer the sub-questions based on the above problem using algorithms presented in the lectures.

How many distinct TSP tours can be constructed by traversing only along the edges in the graph? Give a precise and concise answer. Answers Case Sensitive : Yes

SEARCH
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit squares each 1m x 1m. The grid (intersection points and unit sides) forms a graph (nodes and undirected edges). Start node (S) is at the center of the plane. Goal node (G) is at the north east corner of the plane. MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South]. Take h(X) as the square of the Euclidean distance.

Answer the sub-questions based on the above problem using algorithms presented in the lectures.

What will be the depth of the shallowest leaf node in the Breadth First search tree when GoalTest returns true? Give a precise and concise answer. (Note: nodes already seen are not reopened.) Answers Case Sensitive : No

SEARCH
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit squares each 1m x 1m. The grid (intersection points and unit sides) forms a graph (nodes and undirected edges). Start node (S) is at the center of the plane. Goal node (G) is at the north east corner of the plane. MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South]. Take h(X) as the square of the Euclidean distance.

Answer the sub-questions based on the above problem using algorithms presented in the lectures.

What will be the cost of the path found by the A* algorithm? Use Big-O notation. Answers Case Sensitive : No