Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
22 / 22 published solutions
Question 39 MSQ · 1.0 marks
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
Which of the following will be present in MoveGen(411)?
6406534313530.
132
6406534313531.
222
6406534313532.
402
6406534313533.
510
Published solution
**1. Try each nonempty cup in 411:** Selecting A removes four shells, then sows into B,C,A,B, producing 132. Since its first digit 1 is below 4, this move is invalid.
**2. Try B and C:** Selecting B moves its one shell to C, giving 402. Selecting C moves its shell to A, giving 510. Their first digits 4 and 5 satisfy the validity rule, so MoveGen(411)=[402,510].
**Answer: C, D — C and D — 402 and 510.**
A: **Incorrect:** Sowing from A produces it, but it violates the first-digit nondecrease rule.
B: **Incorrect:** It is not produced by any single cup selection from 411.
C: **Correct:** Selecting B produces 402, which passes the validity rule.
D: **Correct:** Selecting C produces 510, which passes the validity rule.
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
h(411) is equal to __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 7
Published solution
**1. Apply the given evaluation:** For state abc, \(h(abc)=a+b\).
**2. Substitute the digits:** \(h(411)=4+1=5\).
**Answer: 5.**
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
For the state space Graph-123, the lowest value of h is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 7
Published solution
**1. Enumerate the reachable states:** Graph-123 contains 123,204,231,303,312,330,402,411,420,501,510,600.
**2. Evaluate the first two cups:** Their h values in that order are 3,2,5,3,4,6,4,5,6,5,6,6. The minimum is 2, at state 204.
**Answer: 2.**
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
For the state space Graph-123, the highest value of h is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 7
Published solution
**1. Bound the evaluation:** Every move preserves all six shells and \(h=a+b=6-c\le6\), since c≥0.
**2. Show the bound is attained:** Reachable states 330,420,510 and 600 have c=0 and h=6. Thus the maximum is 6.
**Answer: 6.**
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
For the state space Graph-123, the heuristic function h defines a __________ .
6406534313537.
maximization problem
6406534313538.
minimization problem
Published solution
**1. Interpret the heuristic’s intended aim:** h counts shells in cups A and B, with upper bound 6. Larger h means more shells in those first two cups and is preferred by the course’s evaluation convention.
**2. Relate it to the target:** Goal 600 attains h=6, though other states also tie at 6. Best-first search therefore prioritizes larger h, not smaller h.
**Answer: A — Maximization problem.**
**Convention note:** The formula a+b alone does not logically prescribe an optimization direction; this answer uses the intended preference for gathering shells in the first two cups. h=6 is not by itself a goal test.
A: **Correct:** The specified evaluation is used as a reward to be maximized.
B: **Incorrect:** It is not being treated as a remaining-distance estimate to minimize.
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
Select the statements that are true in the state space Graph-123.
6406534313539.
Every state is connected to every other state.
6406534313540.
Every move is reversible.
6406534313541.
The number of shells in each state is the same (constant).
6406534313542.
None of these.
Published solution
**1. Check invariants:** A move removes shells and redistributes exactly those shells, so the total remains six in every reachable state.
**2. Check directionality:** 123 can reach 204, but valid moves cannot reduce the first digit back from 2 to 1. Thus not all reachability is mutual, and not all moves are reversible.
**Answer: C — The number of shells is constant.**
A: **Incorrect:** Directed reachability is not universal; 204 cannot return to 123.
B: **Incorrect:** The first-digit nondecrease constraint prevents reversing moves that increase it.
C: **Correct:** Sowing preserves the six-shell total.
D: **Incorrect:** The conservation statement is true.
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
In the state space Graph-123, __________ .
6406534313543.
every state has exactly one incoming edge
6406534313544.
every state has exactly one outgoing edge
6406534313545.
there is at least one state which has no incoming edges
6406534313546.
there is at least one state which has no outgoing edges
Published solution
**1. Identify a source:** No generated edge enters 123; every successor of it has first digit at least 2, and valid moves can never return that digit to 1.
**2. Identify a sink:** In 600 only A is nonempty. Sowing its six shells gives 222, which lowers the first digit and is invalid, so MoveGen(600) is empty.
**3. Disprove fixed-degree claims:** State 123 has zero incoming and two outgoing edges, while 600 has no outgoing edge.
**Answer: C, D — C and D.**
A: **Incorrect:** State 123 has no incoming edge.
B: **Incorrect:** State 123 has two outgoing edges and 600 has none.
C: **Correct:** The start state 123 has no incoming edge in the generated graph.
D: **Correct:** The target 600 has no valid outgoing move.
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
The number of unique states in the state space Graph-123 is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 17
Published solution
**1. Generate successors once per new state:** 123→204,231; 204→411; 231→312,330; 312→303,420; 330→411; 303→411; 411→402,510; 402→510; 420→501; 510→501; 501→600; 600 has none.
**2. Deduplicate converging paths:** The distinct labels are 123,204,231,303,312,330,402,411,420,501,510,600: twelve states.
**Answer: 12.**
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
Use Depth-First Search to find a path from “123” to “600” where the MoveGen function returns
neighbours in ascending order. At the point when GoalTest returns true, the goal state will be
present in the OPEN list, what other states will be present in the OPEN list at that point?
Enter the states in ascending order as a comma separated list.
Enter NIL if no other states are present in OPEN.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 123,204
Published solution
**1. Run ascending-successor DFS:** OPEN starts [123]. After 123 it is [204,231]; after 204, [411,231]; after 411, [402,510,231].
**2. Preserve already-open nodes:** Inspecting 402 generates 510, but 510 is already in OPEN and is not inserted again. Then 510 opens 501, which opens 600.
**3. Inspect the frontier at success:** Just before the goal test, OPEN is [600,231]. Excluding the goal itself leaves only 231.
**Answer: 231.**
**Convention note:** The passage says the goal remains in OPEN when tested. If an implementation removes it immediately before testing, the remaining non-goal list is still [231].
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
Use Breadth-First Search to find a path from “123” to “600” where the MoveGen function returns
neighbours in ascending order. At the point when GoalTest returns true, the goal state will be
present in the OPEN list, what other states will be present in the OPEN list at that point?
Enter the states in ascending order as a comma separated list.
Enter NIL if no other states are present in OPEN.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 123,204
Published solution
**1. Use FIFO expansion:** The inspected order is 123,204,231,411,312,330,402,510,303,420,501,600. A generated label already in OPEN or CLOSED is dropped.
**2. Follow the last frontier entries:** After 420, OPEN contains only 501. Expanding 501 replaces it with 600. Thus at the goal test OPEN contains the goal alone.
**3. Exclude the goal:** No other state remains, so enter NIL.
**Answer: NIL.**
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
Use Best-First Search to find a path from “123” to “600” where the MoveGen function returns
neighbours in ascending order. List the heuristic values of the nodes in the path (from “123” to
“600”) discovered by Best-First Search.
Enter the heuristic values as a comma separated list. Enter NIL if no path is found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 2,4,2
Published solution
**1. Use maximization best-first search:** At each step choose the largest h in OPEN, retaining alternative frontier nodes and using ascending labels to resolve ties.
**2. Trace the discovered parent path:** 123(h=3)→231(5)→330(6)→411(5)→510(6)→501(5)→600(6). State 411 outranks the deferred 312(h=4); 501 outranks deferred 402(h=4).
**3. Extract only evaluations:** The path’s h sequence is 3,5,6,5,6,5,6.
**Answer: 3,5,6,5,6,5,6.**
**Convention note:** Greedy best-first search can move to a lower evaluation when it is the best node left in OPEN. Strict hill climbing would instead stop at 330.
**STATE SPACE SEARCH**
**Background:**
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia.
There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the
number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a **non-empty** cup, remove all shells from that
cup and distribute those shells in a round-robin manner. **Complete all three steps to complete a**
**single move.**
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each
cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
**Valid move:** a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or
equal to the first digit 'a' in input state.
**MoveGen example:** the state 360 allows only two moves: select cup A to generate 171, or select
cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
**Problem statement:**
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups
as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then
answer the subquestions.
**IMPORTANT: your MoveGen function must consider only valid moves and it must return the**
**neighbours in ascending order.**
For the state space Graph-123, which of the following algorithms will find the shortest path from
“123” to “600” when the MoveGen function returns neighbours in ascending order?
6406534313551.
Best-First Search
6406534313552.
Breadth-First Search
6406534313553.
Depth-First Search
6406534313554.
Hill Climbing
Published solution
**1. Determine the shortest distance:** BFS finds 123→204→411→510→501→600, a five-move route. No route with fewer moves is generated by the level-order search.
**2. Check this instance’s DFS parents:** DFS inspects 402 before 510, but 510 is already in OPEN with parent 411. Its returned path is therefore the same five-move route, rather than a path through 402.
**3. Compare the remaining algorithms:** Maximization best-first returns 123→231→330→411→510→501→600, with six moves. Hill climbing stops at 330 when all successors have lower h.
**Answer: B, C — B and C.**
**Convention note:** DFS is shortest here by the specified ordering and duplicate policy, not by a general shortest-path guarantee.
A: **Incorrect:** Its returned route has six moves, one more than the minimum.
B: **Correct:** FIFO level expansion returns a minimum-hop route.
C: **Correct:** For this particular graph and RemoveSeen rule, its parent chain is also a five-move shortest route.
D: **Incorrect:** It fails to reach 600 because it cannot leave the local maximum at 330.
**Genetic Algorithm**
Which of the following are constructive methods?
6406534313555.
Search algorithm that uses 2-city exchange.
6406534313556.
Genetic algorithm that uses single-point crossover.
6406534313557.
Greedy Heuristic.
6406534313558.
Nearest Neighbour Heuristic.
6406534313559.
Savings Heuristic.
Published solution
**1. Distinguish construction from modification:** Constructive methods build a complete tour from partial edges, a growing path or separate routes. Perturbation modifies an existing tour, and crossover recombines parents.
**2. Classify:** Greedy edge selection, nearest neighbour and savings merges are constructive. Two-city exchange is perturbative, and single-point crossover is recombination.
**Answer: C, D, E — C, D and E.**
A: **Incorrect:** It swaps positions in an existing complete tour.
B: **Incorrect:** It combines parent encodings instead of constructing from partial tour components.
C: **Correct:** It adds feasible edges to construct a complete tour.
D: **Correct:** It extends a partial route one city at a time.
E: **Correct:** It merges initially separate base-centred routes.
**Genetic Algorithm**
Tour representations are basically raw lists (list of city names or list of city positions) which are
interpreted differently by each representation. Given a symmetric TSP, for which of the following
representations the raw list reversal will produce a new tour?
6406534313560.
Path representation
6406534313561.
Adjacency representation
6406534313562.
Ordinal representation
6406534313563.
None of these
Published solution
**1. Reverse a path encoding:** Reversing the city order traces the same undirected cycle backward, so it does not create a different symmetric TSP tour.
**2. Reverse the other raw lists:** An adjacency list’s entries belong to fixed reference cities; reversing entries changes those assignments and can produce self-loops or disconnected cycles. Ordinal positions have shrinking bounds, which raw reversal can violate.
**3. Apply the guaranteed-valid interpretation:** None of these raw-list reversals is an operation guaranteed to produce a new valid undirected tour.
**Answer: D — None of these.**
**Convention note:** The wording is interpreted as a guaranteed representation-preserving operation. Particular adjacency or ordinal lists can coincidentally reverse into another valid tour; that is not a general guarantee.
A: **Incorrect:** It only reverses traversal of the same symmetric cycle.
B: **Incorrect:** Raw reversal does not guarantee a valid single-cycle adjacency encoding.
C: **Incorrect:** Raw reversal can place a large ordinal rank in a position with too few remaining cities.
D: **Correct:** No listed representation guarantees a new valid tour under raw reversal.
**Genetic Algorithm**
Compute the ordinal representation of tour P1 (given in path representation). Use A,B,C,D,E,F as
the index sequence.
P1: E,F,A,C,D,B
Enter the ORDINAL representation as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 1,3,5,9,6,4
Published solution
**1. Use shrinking-list ranks:** Begin with ABCDEF and remove each selected city after recording its current one-based rank.
**2. Compute each rank:** E is 5 in ABCDEF; F is 5 in ABCDF; A is 1 in ABCD; C is 2 in BCD; D is 2 in BD; B is 1 in B.
**3. Combine the ranks:** E,F,A,C,D,B becomes 5,5,1,2,2,1.
**Answer: 5,5,1,2,2,1.**
**Genetic Algorithm**
Path representation of two parent tours are given below. Express the parent tours in ordinal
representation (use A,B,C,D,E,F as the index sequence) and generate offspring using midpoint
crossover. Enter the ordinal representation of one of the child tours.
P1: E,F,A,C,D,B
P2: C,A,D,B,E,F
Enter the ordinal representation as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 1,3,5,9,6,4
Published solution
**1. Encode each parent:** P1=E,F,A,C,D,B gives ordinal (5,5,1,2,2,1). P2=C,A,D,B,E,F gives (3,1,2,1,1,1), by recording and deleting from ABCDEF.
**2. Cut at the midpoint:** Split each six-gene code after gene 3. Exchange suffixes to obtain (5,5,1|1,1,1) and (3,1,2|2,2,1).
**3. Supply one child:** Enter 5,5,1,1,1,1. Every gene stays within its position’s shrinking-list bound.
**Answer: 5,5,1,1,1,1.**
**TSP**
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Use D as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is
__________ . Enter the path representation of the tour starting from D and in the order the cities are
visited by the Nearest Neighbour Heuristic.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z
Published solution
**1. Select the closest unvisited city at each step:** D: A=80, B=23, C=35, E=86; choose B; B: A=42, C=10, E=21; choose C; C: A=45, E=24; choose E; E: A=64; choose A.
**2. Close the tour:** Return from A to D at cost 80. The path representation lists each city once; this return is implicit.
**Answer: D,B,C,E,A.**
**TSP**
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
What is the cost of the tour generated by Nearest Neighbour Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17
Published solution
**1. Select the closest unvisited city at each step:** D: A=80, B=23, C=35, E=86; choose B; B: A=42, C=10, E=21; choose C; C: A=45, E=24; choose E; E: A=64; choose A.
**2. Close the tour:** Return from A to D at cost 80. The path representation lists each city once; this return is implicit.
**3. Add every edge, including the return:** 23+10+24+64+80=201.
**Answer: 201.**
**TSP**
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Construct a tour using Greedy Heuristic. Enter the path representation of the tour starting from
city D.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z
Published solution
**1. Use sorted edges with feasibility checks:** Accept an edge only if no city’s degree exceeds 2 and no cycle forms before all cities can be included.
**2. Process the edge list:** BC (10): accept; BE (21): accept; BD (23): skip, degree limit; CE (24): skip, premature cycle; CD (35): accept; AB (42): skip, degree limit; AC (45): skip, degree limit; AE (64): accept; AD (80): accept.
**3. Trace the accepted cycle:** D → A → E → B → C → D. Rotating the starting city or reversing direction represents the same undirected tour.
**Answer: D,A,E,B,C.**
**TSP**
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
What is the cost of the tour generated by Greedy Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17
Published solution
**1. Use sorted edges with feasibility checks:** Accept an edge only if no city’s degree exceeds 2 and no cycle forms before all cities can be included.
**2. Process the edge list:** BC (10): accept; BE (21): accept; BD (23): skip, degree limit; CE (24): skip, premature cycle; CD (35): accept; AB (42): skip, degree limit; AC (45): skip, degree limit; AE (64): accept; AD (80): accept.
**3. Trace the accepted cycle:** D → A → E → B → C → D. Rotating the starting city or reversing direction represents the same undirected tour.
**4. Sum the cycle:** 80+64+21+10+35=210.
**Answer: 210.**
**TSP**
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Construct the savings tour using D as the base city. The savings for the pairs AB, AC, BC and BE,
respectively, are 61, 70, 48 and 88. Compute the savings for the remaining pairs of cities and then
compute the savings tour. Enter the path representation of the savings tour starting from city D.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z
Published solution
**1. Calculate savings relative to D:** (s(i,j)=d(D,i)+d(D,j)-d(i,j)). The full list is AB=61, AC=70, AE=102, BC=48, BE=88, CE=97.
**2. Merge by descending savings:** AE (102): merge; CE (97): merge; BE (88): skip, interior endpoint; AC (70): skip, premature cycle; AB (61): merge. Merge only different chains at their endpoints, preventing premature cycles and degree greater than 2.
**3. Connect the two remaining chain ends to the base:** The tour is D → B → A → E → C → D. The path representation omits the final repeated base.
**Answer: D,B,A,E,C.**
**TSP**
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
For the given TSP, which of the following algorithms produce a better tour?
6406534313571.
Greedy Heuristic
6406534313572.
Nearest Neighbour Heuristic
6406534313573.
Savings Heuristic
**Deep Learning**
**Section Id :** 64065391697
**Section Number :** 4
Published solution
**1. Compare the computed closed-tour costs:** Nearest neighbour from D gives D–B–C–E–A–D with cost 23+10+24+64+80=201. Greedy gives D–A–E–B–C–D with cost 80+64+21+10+35=210.
**2. Evaluate the savings route:** D–B–A–E–C–D costs 23+42+64+24+35=188. Since 188 is lower than both 201 and 210, Savings produces the best of these three tours.
**Answer: C — Savings Heuristic.**
A: **Incorrect:** Its cost is 210, the highest of the three.
B: **Incorrect:** Its cost 201 exceeds the savings tour’s 188.
C: **Correct:** Its cost 188 is the smallest.
