tsp.c

/*    tsp.c

    Heuristics for solving TSP

    by:Steven Skiena
    begun: August 2, 2006
*/


/*
Copyright 2003 by Steven S. Skiena; all rights reserved. 

Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.

This program appears in my book:

"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.

See our website www.programming-challenges.com for additional information.

This book can be ordered from Amazon.com at

http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/

*/

#include <math.h>
#include <stdio.h>
#include <string.h>

#include "annealing.h"
#include "bool.h"
#include "random.h"

extern int solution_count;

/**********************************************************************/

void read_tsp(tsp_instance *t) {
    int i, j;    /* counters */

    scanf("%d\n", &(t->n));

    for (i = 1; i <= (t->n); i++) {
        scanf("%d %d %d\n", &j, &(t->p[i].x), &(t->p[i].y));
    }
}

void print_tsp(tsp_instance *t) {
    int i;    /* counter */

    for (i = 1; i <= (t->n); i++) {
        printf("%d %d %d\n", i, (t->p[i].x), (t->p[i].y));
    }
}

int sq(int x) {
    return(x * x);
}

double distance(tsp_solution *s, int x, int y, tsp_instance *t) {
    int i, j;

    i = x;
    j = y;

    if (i == ((t->n) + 1)) {
        i = 1;
    }

    if (j == ((t->n) + 1)) {
        j = 1;
    }

    if (i == 0) {
        i = (t->n);
    }

    if (j == 0) {
        j = (t->n);
    }

    return (sqrt((double) (sq(t->p[(s->p[i])].x - t->p[(s->p[j])].x) +
             sq(t->p[(s->p[i])].y - t->p[(s->p[j])].y))));
}

/**********************************************************************/

double solution_cost(tsp_solution *s, tsp_instance *t) {
    int i;           /* counter */
    double cost;     /* cost of solution */
    double distance();

    cost = distance(s, t->n, 1, t);
    for (i = 1; i < (t->n); i++) {
        cost = cost + distance(s, i, i + 1, t);
    }

    return(cost);
}

void initialize_solution(int n, tsp_solution *s) {
    int i;    /* counter */

    s->n = n;
    for (i = 1; i <= n; i++) {
        s->p[i] = i;
    }
}

void copy_solution(tsp_solution *s, tsp_solution *t) {
    int i;    /* counter */
    t->n = s->n;
    for (i = 1; i <= (s->n); i++) {
        t->p[i] = s->p[i];
    }
}
    

void print_solution(tsp_solution *s) {
    int i;    /* counter */

    for (i = 1; i <= (s->n); i++) {
            printf(" %d", s->p[i]);
    }
    printf("\n------------------------------------------------------\n");
}

void read_solution(tsp_solution *s) {
    int i;    /* counter */

    scanf("%d\n", &(s->n));

    for (i = 1; i <= (s->n); i++) {
        scanf("%d", &(s->p[i]));
    }
}

void random_solution(tsp_solution *s) {
    random_permutation(&(s->p[1]), (s->n) - 1);
}

double transition(tsp_solution *s, tsp_instance *t, int i, int j) {
    double was, willbe;    /* before and after costs */
    double distance();
    bool neighbors;        /* i,j neighboring tour positions? */

    neighbors = FALSE; 

    if (i == j) {
        return(0.0);
    }

    if (i > j) {
        return(transition(s, t, j, i));
    }

    if (i == (j - 1)) {
        neighbors = TRUE;
    }

    if ((i == 1) && (j == (s->n))) {
        swap(&i, &j);
        neighbors = TRUE;
    }

    if (neighbors) {
        was = distance(s, i-1, i, t) + distance(s, j, j+1, t);
    } else {
        was = distance(s, i-1, i, t) + distance(s, i, i+1, t)
           + distance(s, j-1, j, t) + distance(s, j, j+1, t);
    }

    swap(&(s->p[i]), &(s->p[j]));

    if (neighbors) {
        willbe = distance(s, i-1, i, t) + distance(s, j, j+1, t);
    } else {
        willbe = distance(s, i-1, i, t) + distance(s, i, i+1, t)
        + distance(s, j-1, j, t) + distance(s, j, j+1, t);
    }

    return(willbe - was);
}

/**********************************************************************/

int main(void) {
    tsp_instance t;    /* tsp points */
    tsp_solution s;    /* tsp solution */
    int i;             /* counter*/
    double solution_cost();

    read_tsp(&t);

    read_solution(&s);
    printf("OPTIMAL SOLUTION COST = %7.1f\n",solution_cost(&s, &t));
    print_solution(&s);


    initialize_solution(t.n, &s);
    printf("solution_cost = %7.1f\n",solution_cost(&s,&t));
    print_solution(&s);

    solution_count=0;
    repeated_annealing(&t, 3, &s);
    printf("repeated annealing %d iterations, cost = %7.1f\n",
            solution_count,solution_cost(&s, &t));
    print_solution(&s);

    return 0;
}