AI: Search Methods for Problem Solving · End Term · May 2024 · AN

**SEARCH**

Based on the above data, answer the given subquestions.

What is the path found by the Best First Search algorithm? Enter the path as a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: S,X,Y,Z**

**SEARCH**

Based on the above data, answer the given subquestions.

What is the path found by A* search algorithm? Enter the path as a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: S,X,Y,Z**

**SEARCH**

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,A,S,A,S,A,... NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: S,X,Y,Z**

**SEARCH**

Based on the above data, answer the given subquestions.

For the given map, which algorithm finds the shortest path from S to G?

**SEARCH**

Based on the above data, answer the given subquestions.

What can you say about the heuristic function for the given graph?

**TSP Branch-and-Bound**

Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes (2nd to 5th node) that are refined by the TSP Branch-and-Bound algorithm. Enter the nodes (node reference numbers) in the order they are refined. Enter a comma separated list of node reference numbers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: a9,b9,c9,d9**

**TSP Branch-and-Bound**

Which node represents the optimal tour and what is the cost of the optimal tour? Enter the node reference number and the tour cost in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a node reference number followed by tour cost, separated by comma. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: a9,42**

**TSP Branch-and-Bound**

Determine the number of cities in the TSP instance. Enter the number of cities in the text box, or enter NIL if it is not possible to determine the number of cities. Enter an integer. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: 42**

**TSP Branch-and-Bound**

Start from city A, what is the path representation of the optimal tour? Enter the path representation in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a comma separated list of cities (city labels). NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: A,X,Y**

**GAMES**

Based on the above data, answer the given subquestions.

Which of the following is a strategy for the MAX player?

**GAMES**

Based on the above data, answer the given subquestions.

List the leaf nodes in the best strategy for MAX. Enter the node labels in alphabetical order. Enter a comma separated list of node labels in alphabetical order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: X,Y,Z**

**GAMES**

Based on the above data, answer the given subquestions.

List the leaf nodes pruned by Alpha-Beta. Enter a comma separated list of node labels in alphabetical order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: X,Y,Z**

**GAMES**

Based on the above data, answer the given subquestions.

List the leaf nodes solved (assigned SOLVED status) by SSS*. Enter a comma separated list of node labels in alphabetical order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: X,Y,Z**

**PROBLEM DECOMPOSITION**

List the first three nodes (including S) expanded by AO* algorithm. List the nodes in the order they are expanded. Observe that primitive nodes are not expanded. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: X,Y,Z**

**PROBLEM DECOMPOSITION**

Determine the value of the start node S after each node is expanded. What are the values of S after the 1st, 2nd and 3rd nodes are expanded, respectively? Enter the 3 values in the textbox. Enter a comma separated list of numbers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: 12,42,17**

**PROBLEM DECOMPOSITION**

What is the final value of the start node S? Enter a number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: 42**

**RULE BASED EXPERT SYSTEMS**

Which of the following rule-data tuples are in the conflict-set?

**RULE BASED EXPERT SYSTEMS**

If the Inference Engine uses **Specificity** as the conflict resolution strategy then which of the following rule-data tuples will qualify?

**RULE BASED EXPERT SYSTEMS**

If the Inference Engine uses **Recency** as the conflict resolution strategy then which of the following rule-data tuples will qualify?

**AUTOMATED PLANNING**

Based on the above data, answer the given subquestions.

Which of the following are **applicable** actions in the start state?

**AUTOMATED PLANNING**

Based on the above data, answer the given subquestions.

Which of the following are **relevant** actions in the goal state?

**AUTOMATED PLANNING**

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are mutex action pairs in Layer 1?

**AUTOMATED PLANNING**

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are mutex proposition pairs in Layer 1?

**CONSTRAINT SATISFACTION** The set of junctions (L, W, Y and T type junctions) that occur in a 2D line drawing of trihedral objects is provided below. The in-plane clockwise/counterclockwise rotations of these junctions are valid as well. These junctions provide constraints on the possible edge assignments (convex, concave, arrow) for the edges/lines in 2D line drawings of trihedral objects. The junctions carry unique labels: L1, L2, L3, L4, L5, L6, T1, T2, T3, T4, W1, W2, W3, Y1, Y2, Y3. When required, use the labels in short answers.

**Note:** A 2D line drawing of trihedral objects is considered to be consistent if all the edges and junctions can be assigned labels that are consistent with each other, otherwise the drawing is considered to be inconsistent and all labels are reset to NIL. Apply a suitable algorithm to assign consistent labels to edges/junctions in the 2D line drawings in the sub-questions. Choose a suitable edge and junction order for solving the problems. Based on the above data, answer the given subquestions.

Assign consistent labels to all the edges and junctions in the 2D line drawing shown below. Enter the labels of the junctions 1, 2, 3, 4 in the text box, in that order. Enter NIL if the drawing has no consistent label assignment.

Enter a comma separated list of junction labels, or enter NIL. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: Y9,T9,W9,L9**

**CONSTRAINT SATISFACTION** The set of junctions (L, W, Y and T type junctions) that occur in a 2D line drawing of trihedral objects is provided below. The in-plane clockwise/counterclockwise rotations of these junctions are valid as well. These junctions provide constraints on the possible edge assignments (convex, concave, arrow) for the edges/lines in 2D line drawings of trihedral objects. The junctions carry unique labels: L1, L2, L3, L4, L5, L6, T1, T2, T3, T4, W1, W2, W3, Y1, Y2, Y3. When required, use the labels in short answers.

**Note:** A 2D line drawing of trihedral objects is considered to be consistent if all the edges and junctions can be assigned labels that are consistent with each other, otherwise the drawing is considered to be inconsistent and all labels are reset to NIL. Apply a suitable algorithm to assign consistent labels to edges/junctions in the 2D line drawings in the sub-questions. Choose a suitable edge and junction order for solving the problems. Based on the above data, answer the given subquestions.

Assign consistent labels to all the edges and junctions in the 2D line drawing shown below. Enter the labels of the junctions 1, 2, 3, 4 in the text box, in that order. Enter NIL if the drawing has no consistent label assignment.

Enter a comma separated list of junction labels, or enter NIL. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: Y9,T9,W9,L9**