6
\$\begingroup\$

I've been recently doing classes on the traveling salesman problem. I've been tackling the nearest neighbor heuristic for the problem and seeing that the algorithm was simplistic, I've decided to see how fast would be solutions implemented in different languages. I've implemented several versions of the solution using different lua extensions, of those most importantly, luajit. I've also done the same algorithm in C.

What surprised me is that luajit solution using C data structures actually beats the pure C implementation significantly (5-6 times faster) C was compiled with gcc -o3 and the problem size was such that completion times were on the order of a few seconds.

I'm not very well versed in the ways of the language, so I wonder if I didn't do something right in C code:

#include <math.h>

typedef struct city {double x; double y; double ind;} city;

double tsp(city* cities, int N){
    city current=cities[0];
    double S=0;
    for (int i=N-1; i>0; i--){
        int pos=i;
        city  viewing= cities[i];
        double d2=pow((current.x-viewing.x),2)+pow((current.y-viewing.y),2);
        double ind=viewing.ind;
        for (int j=1; j<i; j++){
            viewing=cities[j];
            double D2=pow((current.x-viewing.x),2)+pow((current.y-viewing.y),2);
            if ((D2 < d2)||((D2==d2)&&(viewing.ind<ind))){
                pos=j;
                d2=D2;
                ind=viewing.ind;
            }
        }
        S+=sqrt(d2);
        current=cities[pos];
        cities[pos]=cities[i];
    }
    return S+sqrt(pow((cities[0].x-cities[1].x),2)+pow((cities[0].y-cities[1].y),2));
}

The function implements the following algorithm: start at city[0], find nearest city, go there, find nearest unvisited city, go there, repeat until no cities left, go to city[0].

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Peilonrayz
    May 14, 2017 at 23:57
  • \$\begingroup\$ Code was not altered. The edit was extending the text of the question for better understanding. \$\endgroup\$
    – Dimitry
    May 15, 2017 at 5:37

1 Answer 1

7
\$\begingroup\$

Well, the first thing to do is extracting the distance-calculation and replacing the costly call to pow():

inline static double distance2(city* a, city* b) {
    double dx = a->x - b->x;
    double dy = a->y - b->y;
    return dx * dx + dy * dy;
}

Next, let's stop always copying the cities when not really needed.

Optionally, use a sentinel value (INFINITY) so we don't need to single out any candidate for nearest city.

Another nearly gratuitious change I did was starting with the last city given.

I suggest you also invest in slightly more spaces, they make things more readable, especially around operators.

The changed function:

double tsp(city* cities, int N) {
    double S = 0;
    for (int i = N; --i > 0;) {
        double best_d2 = distance2(cities + i, cities + 0);
        int best_pos = 0;
        for(int j = i; --j > 0;) {
            double d2 = distance2(cities + i, cities + j);
            if(d2 < best_d2 || d2 == best_d2 && cities[j].ind < cities[best_pos].ind) {
                best_d2 = d2;
                best_pos = j;
            }
        }
        S += sqrt(best_d2);
        city temp = cities[best_pos];
        cities[best_pos] = cities[i - 1];
        cities[i - 1] = temp;
    }
    return S + sqrt(distance2(cities, cities + N - 1));
}
\$\endgroup\$
7
  • \$\begingroup\$ I would put braces to the if - it's hard to read now. \$\endgroup\$
    – pgs
    May 13, 2017 at 23:45
  • 1
    \$\begingroup\$ An artificial sentinel like INFINITY is almost always wrong. Prefer a natural double best_d2 = distance2(cities + i, cities), and loop for(int j = i; --j > 0;). Also sqrt is only needed once, outside of the loop. \$\endgroup\$
    – vnp
    May 14, 2017 at 5:18
  • \$\begingroup\$ @vnp: Using the sentinel means one less callsite for distance2. Well, maybe that should be measured... Calls to sqrt are already at a minimum... \$\endgroup\$ May 14, 2017 at 8:34
  • \$\begingroup\$ Isn't this double best_d2 = distance2(cities + i, cities + 0); an error? It always initializes best_d2 to distance between city0 and the current one, but what if the city0 is the closest one to the current? We have already left from the city0 once and must only revisit it at the end of the travel. \$\endgroup\$
    – Dimitry
    May 14, 2017 at 20:05
  • \$\begingroup\$ Well, as I said one change I did was building up the city-list from the end of the array to the front, so at that point cities[0] is never visited, cities[i] and following are. \$\endgroup\$ May 14, 2017 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.