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&lt;int&gt;* path, int total_cost, QList&lt;int&gt;* remaining_cities)
{
    int last_visited_city = path-&gt;last();

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

    if(remaining_cities-&gt;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-&gt;push_back(HOME_CITY);

       total_cost += distance_matrix[last_visited_city][HOME_CITY];

       if (total_cost &lt;= current_minimum_cost)
       {
           // we have a new winner!
           current_minimum_cost = total_cost;

           // forget about the previous 'winner' and save the visited path
           tsp_solution-&gt;clear();
           foreach(int element , *path)
               tsp_solution-&gt;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:    
    foreach(int next_city_to_visit , *remaining_cities)
    {
      QList&lt;int&gt;*newPATH = new QList&lt;int&gt;();
      newPATH-&gt;append(*path);
      newPATH-&gt;push_back(next_city_to_visit);

      int total_cost_for_this_new_path = total_cost + distance_matrix[last_visited_city][next_city_to_visit];

      // make a list of 'remaining cities' to visti:
      QList&lt;int&gt;* newREMAINING_CITIES = new QList&lt;int&gt;();
      newREMAINING_CITIES-&gt;append(*remaining_cities);

      // of course we do not have to visit 'next_city_to_visit' twice
      newREMAINING_CITIES-&gt;removeOne(next_city_to_visit);

      // recursion:
      tsp ( newPATH , total_cost_for_this_new_path , newREMAINING_CITIES );
      delete newPATH;
      delete newREMAINING_CITIES;
    }
}


My questions:


Does this function make sense? It seems to work for all my test cases.
Once I go up to 20 cities, it takes a long while to calculate, over an hour.
On memory management: is issuing delete newPATH enough to clear the memory? Or should I issue a delete for all members of the list newPATH? (I guess not as the members are all ints)
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 &lt;algorithm&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;numeric&gt;
#include &lt;limits&gt;

static const int max = 13;

void setup(int distances[max][max]) {
    for (int i = 0; i &lt; max; i++) {
        distances[i][i] = 0;
        for (int j = i + 1; j &lt; max; j++) {
            int d = rand() % 50;

            distances[i][j] = d;
            distances[j][i] = d;
        }
    }
}

int main() {
    int distances[max][max];

    setup(distances);

    std::vector&lt;int&gt; route(max);

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

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

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

    std::cout &lt;&lt; "best distance: " &lt;&lt; best_distance &lt;&lt; "\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).