Quiz Space

AI: Search Methods for Problem Solving · Quiz 1 · 15 Mar 2026 · January 2026 term

Question 23: TSP\ Use the distance matrix (and the sorted edge list) …

Question 23

+1 markOne or more correct options

TSP
Use the distance matrix (and the sorted edge list) to construct TSP tours.

Based on the above data, answer the given subquestions.

Consider N cities on the Euclidean plane, for each city, begin at that city and compute a tour using Nearest Neighbour Heuristic. From the resulting N tours, select the cheapest tour. What can you conclude about the procedure?

Select all that apply.

  1. A

    This procedure will always return the optimal TSP tour.

  2. B

    This procedure will not always return the optimal TSP tour.

  3. C

    This procedure may not always terminate.

  4. D

    This procedure will always terminate.

Show answer

Correct answers

  • B

    This procedure will not always return the optimal TSP tour.

  • D

    This procedure will always terminate.

See the whole paperTake it as a mock test

Question 23 of 23 in the IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 1 paper sat on 15 Mar 2026, in the January 2026 term (AI 15 Mar 26). It carries 1 mark.

More questions from this paper

  1. Q1STATE SPACE SEARCH\ Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the o…
  2. Q2STATE SPACE SEARCH\ Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the o…
  3. Q3STATE SPACE SEARCH\ Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the o…
  4. Q4STATE SPACE SEARCH\ Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the o…
  5. Q5STATE SPACE SEARCH\ Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the o…
  6. Q6STATE SPACE SEARCH\ Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the o…
  7. Q7SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  8. Q8SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  9. Q9SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  10. Q10SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  11. Q11SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  12. Q12SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  13. Q13SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  14. Q14SEARCH\ Background:\ On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite cor…
  15. Q15Which of the following algorithms are designed to escape local minima?
  16. Q16Stochastic Hill Climbing decides whether to move from N to a randomly selected neighbour x based on the probability fun…
  17. Q17What is the total number of tours possible for 4 cities?\ Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESI…
  18. Q18Given a 4-city tour as input, how many unique tours (unique neighbours) will be generated by a MoveGen using the 2-city…
  19. Q19TSP\ Use the distance matrix (and the sorted edge list) to construct TSP tours. Based on the above data, answer the giv…
  20. Q20TSP\ Use the distance matrix (and the sorted edge list) to construct TSP tours. Based on the above data, answer the giv…
  21. Q21TSP\ Use the distance matrix (and the sorted edge list) to construct TSP tours. Based on the above data, answer the giv…
  22. Q22TSP\ Use the distance matrix (and the sorted edge list) to construct TSP tours. Based on the above data, answer the giv…