Program Overview
The Travelling Salesman Problem (TSP) is a classic optimization problem in computer science and operations research. It aims to find the shortest possible route that visits each city exactly once and returns to the origin city.
Program Structure
- Data Representation: The cities and their distances are represented using a 2D array.
- Permutation Generation: We generate all possible permutations of city visits to find the shortest path.
- Cost Calculation: For each permutation, we calculate the total travel cost and track the minimum cost found.
C++ Code
#include <iostream>
#include <vector>
#include <string>using namespace std; // Function to calculate the total travel cost for a given path int calculateCost(const vector<vector>& distance, const vector& path) { int cost = 0; for (size_t i = 0; i < path.size(); ++i) { int from = path[i]; int to = path[(i + 1) % path.size()]; // Wrap around to the start cost += distance[from][to]; } return cost; } // Function to solve TSP using brute-force approach void solveTSP(const vector<vector>& distance) { int numCities = distance.size(); vector cities(numCities); // Initialize the cities vector for (int i = 0; i < numCities; ++i) { cities[i] = i; } int minCost = numeric_limits::max(); vector bestPath; // Generate all permutations of cities do { int currentCost = calculateCost(distance, cities); if (currentCost < minCost) { minCost = currentCost; bestPath = cities; } } while (next_permutation(cities.begin(), cities.end())); // Output the best path and its cost cout << "Minimum cost: " << minCost << endl; cout << "Best path: "; for (int city : bestPath) { cout << city << " "; } cout << endl; } int main() { // Example distance matrix vector<vector> distance = { {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0} }; solveTSP(distance); return 0; }
Documentation
Explanation of the Code:
- Libraries: The program includes the necessary libraries:
<iostream>,<vector>,<algorithm>, and<limits>. - calculateCost Function: This function calculates the total cost of traveling a specific path defined by the order of cities visited. It wraps around to the start city to complete the cycle.
- solveTSP Function: This function implements the brute-force solution by generating all permutations of the cities using
std::next_permutation. It calculates the cost for each permutation and keeps track of the minimum cost and the corresponding path. - Main Function: It defines a sample distance matrix, calls
solveTSP, and prints the results.
Functions
- calculateCost: Takes a distance matrix and a path. It calculates the total travel cost for that path.
- solveTSP: Takes a distance matrix, generates all possible paths, and finds the minimum travel cost and corresponding path.
Input
The distance matrix is a 2D vector where distance[i][j] represents the distance from city i to city j.
Output
The program outputs the minimum cost and the best path that achieves this cost.
