TSP启发式算法的低C性能

Question

最近我一直在上旅行推销员问题的课。对于这个问题，我一直在研究最近的启发式方法，并且看到算法过于简单，我决定看看在不同语言中实现解决方案的速度。我使用不同的lua扩展实现了解决方案的几个版本，其中最重要的是luajit。我在C语言中也做过同样的算法。

令我惊讶的是，使用C数据结构的luajit解决方案实际上大大超过了纯C实现(速度快5-6倍)C是用gcc -o3编译的，问题的大小是这样的，完成时间大约只有几秒钟。

我不太精通这种语言，所以我想知道我是否在C代码中做了一些正确的事情：

#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));
}

该函数实现了以下算法:从城市0开始，找到最近的城市，去那里，找到最近的未访问的城市，去那里，重复直到没有城市，再去城市0。

Answer 1

首先要做的是提取距离计算并替换对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;
}

接下来，让我们停止在不需要的时候照搬城市。

可以选择使用一个哨兵值(INFINITY)，这样我们就不需要为最近的城市挑选任何候选人。

我所做的另一个几乎毫无意义的改变是从最后一个城市开始的。

我建议您也投资于稍微多一点的空间，它们使事物更加可读性，特别是在运算符周围。

职能的改变：

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));
}