Traveling Salesman Quiz - Batch 1

What is the Traveling Salesman Problem (TSP)?

• A) A problem of finding the longest route that visits each city exactly once.

• B) A problem of finding the shortest route that visits each city exactly once and returns to the starting city.

• C) A problem of finding the shortest path between two specific cities.

• D) A problem of finding the shortest path that visits only a subset of cities.

Which of the following statements about TSP is true?

• A) It is an easy problem to solve for large numbers of cities.

• B) It is a type of optimization problem.

• C) It is a problem that cannot be represented graphically.

• D) It always has a unique solution.

What does TSP stand for?

• A) Traveling Salesperson Problem

• B) Traveling Salesman Problem

• C) Traveling Saleswoman Problem

• D) Traveling Student Problem

What is the output of the TSP?

• A) The total number of cities visited.

• B) The shortest path that visits each city exactly once and returns to the starting city.

• C) The longest path that visits each city exactly once.

• D) The average distance between cities.

Which algorithm guarantees an optimal solution for TSP but is impractical for large datasets due to its high time complexity?

• A) Nearest Neighbor Algorithm

• B) Genetic Algorithm

• C) Simulated Annealing

• D) Brute-Force Algorithm

In TSP, what is meant by a "tour"?

• A) A path that visits each city exactly once.

• B) A path that visits each city exactly once and returns to the starting city.

• C) A path that visits some cities multiple times.

• D) A path that visits only one city.

• A

• B

• C

• D

Which data structure is typically used to represent distances between cities in TSP?

• A) Linked List

• B) Stack

• C) Adjacency Matrix

• D) Queue

Which of these algorithms can be used to find an approximate solution for TSP?

• A) Brute-Force Algorithm

• B) Breadth-First Search

• C) Genetic Algorithm

• D) Depth-First Search

Which Java method can shuffle a list of cities to create a random initial population for a Genetic Algorithm?

• A) Collections.shuffle()

• B) Arrays.sort()

• C) Collections.sort()

• D) Arrays.shuffle()

How many permutations of cities need to be checked in a brute-force solution to TSP for n cities?

• A) n

• B) n^2

• C) n!

• D) 2^n