AUTOMATED PLANNING\ The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments. PREDICATES onTable(X) - X is on the table. on(X,Y) - X is directly placed on Y. clear(X) - X has nothing above it, it is clear. holding(X) - The arm is holding X. armEmpty - The arm is not holding any block, it is empty. OPERATORS Pickup(X) - Pick up X directly from the table. Preconditions: { armEmpty, clear(X), onTable(X) } Add-Effects : { holding(X) } Del-Effects : { armEmpty, onTable(X) } Putdown(X) - Place X directly on the table. Preconditions: { holding(X) } Add-Effects : { armEmpty, onTable(X) } Del-Effects : { holding(X) } Unstack(X,Y) - Pick up X that is directly on Y. Preconditions: { armEmpty, clear(X), on(X,Y) } Add-Effects : { clear(Y), holding(X) } Del-Effects : { armempty, on(X,Y) } Stack(X,Y) - Place X directly on Y. Preconditions: { holding(X), clear(Y) } Add-Effects : { armEmpty, on(X,Y) } Del-Effects : { holding(X), clear(Y) } Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.\ Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.\ A planning problem is …

(C) on(G,M); on(E,M); { on(E,M), on(G,M) }; END

(A) { on(E,M), on(G,M) }; on(E,M); on(G,M); END

(B) { on(E,M), on(G,M) }; on(G,M); on(E,M); END

(D) on(E,M); on(G,M); { on(E,M), on(G,M) }; END

AI Search Methods Quiz 2 PYQ Sep 2023: 3 Dec 2023

Question 1

+0 marksOne correct option

Printed graph sheets (hard copy) will be provided for registered candidates only.

ASK FOR PRINTED GRAPH SHEETS

8 PAGES TWO-SIDE PRINT

A
Printed graph sheets were provided to me.
B
Printed graph sheets were not provided to me.
C
I did not use graph sheets.

Show answer

Correct answer

A
Printed graph sheets were provided to me.

Question 1 on its own page

Question 2

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

In the map, S is the first node to be refined, determine the next 4 nodes from the 2nd to 5th node refined by A*. Enter the nodes in the order they are refined.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: W,X,Y,Z

Show answer

Correct answer: A,D,B,C

Question 2 on its own page

Question 3

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

For the 4 nodes listed in the previous question, list the f-values of those nodes as a comma separated list. Use the same node order used in the previous question.
Enter a comma separated list of natural numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 2,7,1,8

Show answer

Correct answer: 19,21,26,30

Question 3 on its own page

Question 4

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

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

Show answer

Correct answer: S,A,D,B,C,G

Question 4 on its own page

Question 5

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

A* may revise the f-values of nodes when it visits them again. List all the f-values assigned to node ‘E’, excluding +INFINITY (or +LARGE) assigned initially.
Enter a comma separated list of f-values.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 3,1,4

Show answer

Correct answer: 34,32

Question 5 on its own page

Question 6

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

For w=3, what is the path found by WA* algorithm?
Enter the path as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z,G

Show answer

Correct answer: S,D,B,E,G

Question 6 on its own page

Question 7

+1 markNumerical answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

What is the cost of the path found by Branch-and-Bound algorithm?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 32

Question 7 on its own page

Question 8

+1 markOne correct option

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the subquestions.

Is the heuristic admissible in the given map?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

A
Yes

Question 8 on its own page

Question 9

+1 markNumerical answer

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

What is the length of the optimal plan? Enter the number of actions in the optimal plan. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 6

Question 9 on its own page

Question 10

+1 markOne or more correct options

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

Which of the following are applicable actions for the given planning problem?

Select all that apply.

A
Pickup(D)
B
Pickup(G)
C
Pickup(M)
D
Unstack(C,M)
E
Unstack(E,D)

Show answer

Correct answers

B
Pickup(G)
D
Unstack(C,M)
E
Unstack(E,D)

Question 10 on its own page

Question 11

+1 markOne or more correct options

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

Which of the following are relevant actions for the given planning problem?

Select all that apply.

A
Pickup(G)
B
Stack(E,M)
C
Stack(G,E)
D
Unstack(C,M)
E
Unstack(E,D)

Show answer

Correct answers

B
Stack(E,M)
C
Stack(G,E)

Question 11 on its own page

Question 12

+1 markOne correct option

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

Which of the following can be pushed as the first three elements onto the stack by the Goal Stack Planning algorithm? In the representation below the stack has a bottom on the right marked by the entry END. Use appropriate tie-breakers listed.

A
{ on(E,M), on(G,M) }; on(E,M); on(G,M); END
B
{ on(E,M), on(G,M) }; on(G,M); on(E,M); END
C
on(G,M); on(E,M); { on(E,M), on(G,M) }; END
D
on(E,M); on(G,M); { on(E,M), on(G,M) }; END

Show answer

Correct answer

C
on(G,M); on(E,M); { on(E,M), on(G,M) }; END

Question 12 on its own page

Question 13

+1 markOne correct option

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

For the subgoal ordering given in the goal description (and using the given tie breaking rules), which of the following is the first action popped out of the stack in Goal Stack Planning?

A
Pickup(G)
B
Stack(G,E)
C
Unstack(E,D)
D
Unstack(C,M)

Show answer

Correct answer

A
Pickup(G)

Question 13 on its own page

Question 14

+1 markOne correct option

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

For the subgoal ordering given in the goal description (and using the given tie breaking rules), does the Goal Stack Planning algorithm find an optimal plan?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

B
No

Question 14 on its own page

Question 15

+1 markOne correct option

AUTOMATED PLANNING
The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

PREDICATES

text

1    onTable(X)  -  X is on the table.
2    on(X,Y)     -  X is directly placed on Y.
3    clear(X)    -  X has nothing above it, it is clear.
4    holding(X)  -  The arm is holding X.
5    armEmpty    -  The arm is not holding any block, it is empty.

OPERATORS

text

1    Pickup(X) - Pick up X directly from the table.
2       Preconditions: { armEmpty, clear(X), onTable(X) }
3       Add-Effects  : { holding(X) }
4       Del-Effects  : { armEmpty, onTable(X) }
5
6    Putdown(X) - Place X directly on the table.
7        Preconditions: { holding(X) }
8        Add-Effects  : { armEmpty, onTable(X) }
9        Del-Effects  : { holding(X) }
10   Unstack(X,Y) - Pick up X that is directly on Y.
11      Preconditions: { armEmpty, clear(X), on(X,Y) }
12      Add-Effects  : { clear(Y), holding(X) }
13      Del-Effects  : { armempty, on(X,Y) }
14
15   Stack(X,Y) - Place X directly on Y.
16      Preconditions: { holding(X), clear(Y) }
17      Add-Effects  : { armEmpty, on(X,Y) }
18      Del-Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to deadends and cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Based on the above data, answer the given subquestions.

If the subgoals in the goal description are swapped places then does the Goal Stack Planning algorithm find an optimal plan?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

A
Yes

Question 15 on its own page

Question 16

+1 markWritten answer

GAMES
The figure shows a game tree with evaluations W (win), L (loss) and D (draw) from Max's perspective. The nodes are labeled in a level-by-level (a,b,...,e) left-to-right (1,2,...) manner as indicated in the game tree.

Based on the above data, answer the given subquestions.

What is the outcome (W, D or L) of the game when both players play perfectly?
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X

Show answer

Correct answer: W

Question 16 on its own page

Question 17

+1 markWritten answer

GAMES
The figure shows a game tree with evaluations W (win), L (loss) and D (draw) from Max's perspective. The nodes are labeled in a level-by-level (a,b,...,e) left-to-right (1,2,...) manner as indicated in the game tree.

Based on the above data, answer the given subquestions.

You are allowed to change the eval of one leaf node, change the eval such that the game will end in a draw when both players play perfectly. Which node will you change and what is the new eval? Enter the label of the node you wish to change and the new eval as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: a1,X

Show answer

Correct answer: c13,D or c13,L or c15,D or c15,L or d13,D or d13,L

Question 17 on its own page

Question 18

+1 markWritten answer

GAMES – AlphaBeta, SSS*

Based on the above data, answer the given subquestions.

List the horizon nodes in the best strategy.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,B,C,D

Question 18 on its own page

Question 19

+1 markWritten answer

GAMES – AlphaBeta, SSS*

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: F,G,H,J,K,L

Question 19 on its own page

Question 20

+1 markWritten answer

GAMES – AlphaBeta, SSS*

Based on the above data, answer the given subquestions.

List the horizon nodes in the initial cluster formed by SSS* algorithm.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,E,I

Question 20 on its own page

Question 21

+1 markWritten answer

GAMES – AlphaBeta, SSS*

Based on the above data, answer the given subquestions.

List the horizon nodes assigned SOLVED status by the SSS* algorithm.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,B,C,D,E,I or A,E,I,B,C,D

Question 21 on its own page

Question 22

+1 markNumerical answer

TSP
The distance matrix and sorted segment costs for 5 cities (A to E) are provided below along with the BnB search tree. Use the Branch-and-Bound algorithm to compute the optimal tour.

Based on the above data, answer the given subquestions.

What is the lower bound on the cost of the tour as per the TSP BnB algorithm discussed in class? Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 342

Question 22 on its own page

Question 23

+1 markWritten answer

TSP
The distance matrix and sorted segment costs for 5 cities (A to E) are provided below along with the BnB search tree. Use the Branch-and-Bound algorithm to compute the optimal tour.

Based on the above data, answer the given subquestions.

What is the first segment E1 (XY) used for refining S0?
Enter edge label XY
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: XY

Show answer

Correct answer: DE or ED

Question 23 on its own page

Question 24

+1 markNumerical answer

TSP
The distance matrix and sorted segment costs for 5 cities (A to E) are provided below along with the BnB search tree. Use the Branch-and-Bound algorithm to compute the optimal tour.

Based on the above data, answer the given subquestions.

What is the cost of the node ~E1 that excludes segment XY?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 391

Question 24 on its own page

Question 25

+1 markWritten answer

TSP
The distance matrix and sorted segment costs for 5 cities (A to E) are provided below along with the BnB search tree. Use the Branch-and-Bound algorithm to compute the optimal tour.

Based on the above data, answer the given subquestions.

What is the second segment E2 (UV) that is used for refinement? What is the cost of the node E2. Enter the segment UV and the cost as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: UV,42

Show answer

Correct answer: CE,342 or EC,342

Question 25 on its own page

Question 26

+1 markNumerical answer

TSP
The distance matrix and sorted segment costs for 5 cities (A to E) are provided below along with the BnB search tree. Use the Branch-and-Bound algorithm to compute the optimal tour.

Based on the above data, answer the given subquestions.

What is the cost of the optimal tour?
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 346

Question 26 on its own page