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완전 문제의 하나로, 다항식 시간의 해법 (은)는 존재하지 않는다고 말해지고 있다. 정말로 존재할까 이바지하지 않든지인가, 증명할 수 있으면, 당신은 튜링상(컴퓨터 과학 분야에서의 노벨상) 등 는 두이다.