tsp  巡回セールスマン問題（n個の市1回ずつ通ってもとの市
     に戻るための最短パスを求める問題）

int tsp(int *spath, int *xcity, int *ycity, int ncity);

spath  （出力）最短パスが入っている配列
xcity  （入力）n個の市のx座標
ycity  （入力）n個の市のy座標
ncity  （入力）市の数n

使い方ですが、まずデータファイルを用意しておく。市の数をデータ ファイルの1行目に書く。2行目からは1行ごとに各市の x、y 座標を書く。 たとえば、以下のように、
4
2 4
6 8
1 4
3 6
でデータファイルを書く。つぎに、用例プログラムは
tsp-test データファイル
で実行すれば、最短距離を出すパスが表示される。最短パスがいくつも ある場合は、その1例の表示となる。

#define MAX_CITY 100

int tsp(int *spath, int *xcity, int *ycity, int ncity)
{
    int slen = -1;
    int tpath[MAX_CITY];
    static int guess();
    static void evaluate();

    while (1) {
        if (guess(tpath, slen, xcity, ycity, ncity) == 1)
            break;
        evaluate(&slen, spath, tpath, xcity, ycity, ncity);
    }
    return slen;
}

static int guess(int *tpath, int slen, int *xcity, int *ycity, int ncity)
{
    int i, j, k;
    int	tmp[MAX_CITY];

    if (slen < 0) {
        for (i = 0; i < ncity; i++) tpath[i] = i;
        return 0;
    }

    for (i = ncity - 2; i >= 1; i--) {
        for (j = 0; j < ncity; j++) tmp[j] = j;
        for (j = 0; j <= i; j++) tmp[tpath[j]] = MAX_CITY;
        for (j = 0; j < ncity; j++)
            if (tmp[j] != MAX_CITY)
                if (tmp[j] > tpath[i]) {
                    tpath[i] = tmp[j];
                    goto NEXT;
                }
    }
    return 1;

NEXT:
    for (j = i+1; j < ncity; j++) {
        for (k = 0; k < ncity; k++) tmp[k] = k;
        for (k = 0; k < j; k++) tmp[tpath[k]] = MAX_CITY;
        for (k = 0; k < ncity; k++)
            if (tmp[k] != MAX_CITY) {
                tpath[j] = tmp[k];
                break;
            }
    }
    return 0;
}

static void evaluate(int *slen, int *spath, int *tpath,int *xcity, int *ycity, int ncity)
{
    int i;
    int dx, dy;
    int tlen;

    dx = xcity[tpath[0]] - xcity[tpath[ncity-1]];
    dy = ycity[tpath[0]] - ycity[tpath[ncity-1]];
    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;
    tlen = dx + dy;
    for (i = 1; i < ncity; i++) {
        dx = xcity[tpath[i]] - xcity[tpath[i-1]];
        dy = ycity[tpath[i]] - ycity[tpath[i-1]];
        if (dx < 0) dx = -dx;
        if (dy < 0) dy = -dy;
        tlen += dx + dy;
    }

    if (*slen < 0 || tlen < *slen) {
        for (i = 0; i < ncity; i++) spath[i] = tpath[i];
        *slen = tlen;
    }
}

何百市を超えると、世界の全てのコンピュータを動員して、宇宙誕生の瞬 間からの何百億年を計算させても終わらない計算時間である。コンピュー タはなんと無力なものであろう。その創造主の人間についても同じことが いえるかも知れない。

巡回セールスマン問題はいわゆるNP完全問題の1つで、多項式時間の解法 は存在しないといわれている。本当に存在するかしまいか、証明できれば、 あなたはチューリング賞（コンピュータ科学分野でのノーベル賞）をもら えるはずである。