Traveling Salesman Problem for visiting cities

Question

Implement TSP problem using best first algorithm (so it will be backtracking, branch-and-bound, and best-first). Since you are looking for a cycle, the start/finish city is not important. Therefore we assume that start and finish city is always index 0.

For the bound use solution of the relaxed problem as discussed in class: TSP uses 2 constraints,

all cities have to be visited, each city is visited once (except the start) Try dropping one of them and see if you can solve the resulting relaxed problem. Driver calls a function std::vector SolveTSP( char const* filename ); return value is a vector of city indices in order they are visited. The first and last values are always 0 (start=0, ...., finish=0). Example:

0 4 2 1 3 0 

This is an example of a map:

5
1 2 1 2 
  1 2 2 
    2 1 
      1 

where 5 is the number of cities.

I've coded a nearest neighbour heuristic and it solved half of the test cases. The rest of the cases timed out because the algorithm took too long. I asked around and a friend suggested having an early exit so that the algo won't have to continue calculating when the current path costs more than the best path. It solved 70% of the test cases but the last 3 test cases are still being timed out (the last 3 test cases are the hardest). Are there any more ways I can optimize my code?

This is my tsp.cpp:

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>

using namespace std;

const int INF = INT_MAX;

struct State {
    int city;
    int level;
    vector<int> path;
    int visited; // Bitmask to represent visited cities
    int cost;

    State(int _city, int _level, const vector<int>& _path, int _visited, int _cost)
        : city(_city), level(_level), path(_path), visited(_visited), cost(_cost) {}

    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

int CalculateLowerBound(const State& current, const vector<int>& distances, int numCities) {
    int lowerBound = current.cost;

    for (int city = 0; city < numCities; ++city) {
        if (!(current.visited & (1 << city))) {
            int minDist = INF;

            // Find the two smallest distances to unvisited cities
            for (int nextCity = 0; nextCity < numCities; ++nextCity) {
                if (city != nextCity && !(current.visited & (1 << nextCity))) {
                    minDist = min(minDist, distances[city * numCities + nextCity]);
                }
            }

            lowerBound += minDist;
        }
    }

    return lowerBound;
}

vector<int> readInput(char const* filename, int& numCities) {
    ifstream input(filename);
    input >> numCities;

    vector<int> distances(numCities * numCities);

    // Read distance values and store them in the flattened vector
    for (int i = 0; i < numCities; ++i) {
        for (int j = i + 1; j < numCities; ++j) {
            int distance;
            input >> distance;
            distances[i * numCities + j] = distances[j * numCities + i] = distance;
        }
    }

    return distances;
}

int CalculateDistance(int city1, int city2, const vector<pair<int, int>>& cityCoordinates) {
    int x1 = cityCoordinates[city1].first;
    int y1 = cityCoordinates[city1].second;
    int x2 = cityCoordinates[city2].first;
    int y2 = cityCoordinates[city2].second;

    // Calculate Euclidean distance
    double dx = x1 - x2;
    double dy = y1 - y2;
    double distance = sqrt(dx * dx + dy * dy);

    // Return the distance as an integer (rounding to the nearest integer)
    return static_cast<int>(distance + 0.5);
}

vector<int> SolveTSP(char const* filename) {
    int numCities;
    vector<int> distances = readInput(filename, numCities);

    // Initialize the initial state
    vector<int> initialPath = { 0 }; // Start at city 0
    int visited = 1; // Start city is visited
    State initial(0, 0, initialPath, visited, 0);

    // Priority queue for best-first search
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push(initial);

    // Initialize the best tour and its cost
    vector<int> bestTour;
    int bestCost = INF;

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        // Calculate the lower bound
        int lowerBound = CalculateLowerBound(current, distances, numCities);

        if (lowerBound >= bestCost) {
            continue; // Skip this path as it cannot lead to a better solution
        }

        if (current.level == numCities - 1) {
            // If all cities have been visited, add the return to start city and update best tour if necessary
            current.path.push_back(0);
            current.cost += distances[current.city * numCities];

            if (current.cost < bestCost) {
                bestTour = current.path;
                bestCost = current.cost;
            }
        }
        else {
            for (int nextCity = 0; nextCity < numCities; ++nextCity) {
                if (!(current.visited & (1 << nextCity))) {
                    // Create a new state for each unvisited city
                    vector<int> newPath = current.path;
                    newPath.push_back(nextCity);

                    int newVisited = current.visited | (1 << nextCity);

                    int newCost = current.cost + distances[current.city * numCities + nextCity];

                    pq.push(State(nextCity, current.level + 1, newPath, newVisited, newCost));
                }
            }
        }
    }

    return bestTour;
}

Answer 1

limited set size

struct State {
    ...
    int visited; // Bitmask to represent visited cities

The C++ containers library offers perfectly good datastructures. It's odd that you chose not to use an unordered_set std::vector<bool>, as G. Sliepen observes.

You didn't make any effort to obtain a wide integer when running on "small" word servers, such as a 32-bit host.

Choosing to interpret the initial bit as a sign bit can make debugging this code needlessly inconvenient.

Some TSP instances are easy to solve despite having a high city count. For example, a hundred cities stretched out along I-95 would lead to a fairly obvious solution.

(Using int rather than double for cost was perhaps a somewhat odd design choice, but I suppose it will work fine, without too many ties.)

        }
        else {

Please use a code pretty-printer / auto-formatter, to improve legibility.

Thank you for breaking out the CalculateLowerBound helper, it looks very nice and logical. I do worry that its quadratic cost may be trouble. Hopefully we don't ask it same question repeatedly, as the returned result is not memoized.

---

algorithm

any more ways i can optimize ?

The "iterate over each unvisited city" loop is simple and straightforward. Changing the order in which we consider each candidate might allow the current.cost < bestCost test to prune more effectively. Essentially we want to get a "pretty good" bestCost early on. You might try either of these two approaches:

1. Visit a random permutation of cities, rather than in the given sequential order.
2. Order candidates by distance from current.
3. Almost the same thing, use a quad-tree representation and visit candidates with same quad-tree prefix as current before visiting more distant candidates.