Traveling Salesperson Problem (TSP) Optimization Analysis

The Traveling Salesperson Problem (TSP) is a classic optimization problem where a salesperson needs to visit a set of cities and return to the starting city, minimizing the total travel distance. This challenge asks you to implement a basic TSP solver and then analyze its performance with different city counts and algorithms, providing insights into the computational complexity of the problem. This is useful for understanding the trade-offs between different optimization approaches and their scalability.

Problem Description

You are tasked with creating a Rust program that solves the Traveling Salesperson Problem using a brute-force approach (checking all possible permutations) and then analyzes its performance. The program should:

1. Generate Random Cities: Create a function that generates a specified number of cities, each represented by an (x, y) coordinate pair as a tuple (f64, f64).
2. Calculate Distance: Implement a function to calculate the Euclidean distance between two cities.
3. Brute-Force TSP Solver: Implement a function that takes a vector of cities as input and finds the shortest possible route using a brute-force approach (generating all permutations of cities and calculating the total distance for each). The function should return the shortest route (a vector of city indices) and the total distance.
4. Performance Analysis: The main part of the program should:
   • Generate cities for different numbers of cities (e.g., 5, 10, 15, 20).
   • For each number of cities, run the brute-force TSP solver and measure the execution time using std::time::Instant.
   • Print the number of cities, the execution time, and the shortest distance found.
   • Store the results in a suitable data structure (e.g., a vector of tuples) for later analysis.

Examples

Example 1:

Input: 5 cities
Output:
Cities: 5
Time: 0.001234 seconds
Shortest Distance: 10.56789

Explanation: The program generates 5 random cities, calculates all possible routes, finds the shortest one, and reports the time taken and the distance.

Example 2:

Input: 10 cities
Output:
Cities: 10
Time: 0.005678 seconds
Shortest Distance: 25.89012

Explanation: Similar to Example 1, but with 10 cities, resulting in a longer execution time due to the increased number of permutations.

Example 3: (Edge Case - Small Number of Cities)

Input: 3 cities
Output:
Cities: 3
Time: 0.000123 seconds
Shortest Distance: 5.43210

Explanation: Demonstrates the very fast execution time for a small number of cities.

Constraints

• The number of cities should be between 3 and 20 (inclusive).
• City coordinates should be floating-point numbers (f64) between 0.0 and 100.0.
• Execution time should be measured accurately using std::time::Instant.
• The brute-force approach is required for the TSP solver. Do not use more efficient algorithms like dynamic programming or heuristics for this challenge.
• The program should compile and run without errors.

Notes

• Consider using the permutations crate to generate all possible permutations of cities efficiently. Add it to your Cargo.toml file: permutations = "0.4"
• The brute-force approach has a time complexity of O(n!), where n is the number of cities. This means the execution time will increase very rapidly as the number of cities increases.
• Focus on clear and readable code. Use meaningful variable names and comments to explain your logic.
• The goal is to demonstrate an understanding of TSP and performance analysis, not to create the most efficient TSP solver. The brute-force approach is intentional to highlight the problem's complexity.
• You can use a simple text-based output format for the performance analysis results. No need for fancy visualizations.