Travelling Salesman in Qt

I am writing a recursive function based on the Travelling Salesman Problem.

Is this a correct way of doing things, or am I creating memory leaks?

Prerequisites are:

• a two dimensional matrix distance_matrix[][] to store the distances between the cities

• a global int called current_minimum_cost which will be MAX_INT for starters (or any high 'impossible' number), it keeps track of the cost of the current 'optimal' path

• remaining_cities: a QList of ints which at starting point contains all the cities to visit (except the HOME_CITY) (every city is represented by an integer, the same integer is used to look up the distance between two cities by using distance_matrix[cityA][cityB].

• path: a QList of ints which stores the current path followed (so 0 , 7, 2, 5) means the salesman goes from his HOME_CITY to city #7 to city #2 to city #5 . At starting point it only contains the HOME_CITY (which is 0)

• after doing his tour, the salesman has to return to his HOME_CITY (0)

```
void tsp(QList path, int total_cost, QList remaining_cities)
{
int last_visited_city = path->last();

if(total_cost > current_minimum_cost)
{
//cost higher than current_minimum_cost => ABORT
return;
}

if(remaining_cities->empty())
{
//all cities visited

//only add the distance back to the home city (salesman returns home)
//path += HOME_CITY en total_cost += terug naar HOME_CITY";
path->push_back(HOME_CITY);

total_cost += distance_matrix[last_visited_city][HOME_CITY];

if (total_cost clear();
foreach(int element , *path)
tsp_solution->push_back(element);
}
// if not, than it means that "returning home" makes the trip more costly than the previous 'winner' (we always 'return home', so this is also taken into account with the previous 'winner')
return;
}

// calculate the new possibilities to travel to from the current city:

I'd have serious doubts about its being the fastest possible code, but just for fun let's consider the simplest possible code to generate correct answers.

The standard library has next_permutation, which can generate all the possible permutations of a collection. So, let's consider how we do this. We start with a 2D array of distances between cities. We then have a collection to represent a route through the cities. Since each city must appear once in the collection, we can start with it just containing numbers from 0 to N in order. We then permute those, find the distance for each, keep the shortest, and we're (eventually) done.

#include 
#include 
#include 
#include 
#include 

static const int max = 13;

void setup(int distances[max][max]) {
    for (int i = 0; i  route(max);

    std::iota(route.begin(), route.end(), 0);

    int best_distance = std::numeric_limits::max();
    do {
        int distance = 0;
        for (int i = 1; i  best_distance)
                break;
        }
        distance += distances[route[max - 1]][0];

        if (distance < best_distance) best_distance = distance;
    } while (std::next_permutation(route.begin() + 1, route.end()));

    std::cout << "best distance: " << best_distance << "\n";
}

Now some might wonder why I'd question this being the fastest way to do the job. Generic algorithms are, after all, intended to provide nearly the speed of custom-written code--their runtime overhead is usually quite minimal.

While that's true, in this case an important optimization is missed. If we view the routes as a tree or a graph, we can stop traversing a branch as soon as we reach a node where the current distance is greater than the best distance so far. This can avoid visiting a large number of paths based on a single test.

Using next_permutation, however we don't get that optimization. Since we don't know the relationships between paths, information we obtain from traversing one path can't be used to eliminate other possible paths.

While probably pretty fast for small sets of data, this is likely to be substantially slower than many others when N gets large at all.

Note: this does not depend upon the triangle inequality (and the test data it generates almost certainly doesn't follow the triangle inequality either).

StackExchange Code Review Q#54940, answer score: 5