Skip to content

Instantly share code, notes, and snippets.

@benck
Created April 14, 2013 04:16

Revisions

  1. benck created this gist Apr 14, 2013.
    104 changes: 104 additions & 0 deletions TSPparallel.c
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,104 @@
    #include <omp.h>
    #include <stdlib.h>
    #include <stdio.h>

    #define MAX_N 26
    #define X 0
    #define Y 1

    int N;
    int map[MAX_N][2];
    // int position[MAX_N];
    int ans[MAX_N] = {0};
    int min_distance = 0;


    inline void print_solution(int position[])
    {
    int i;
    int sum = 0;
    for (i = 1; i < N; i++){
    int dx = map[position[i]][X] - map[position[i-1]][X];
    int dy = map[position[i]][Y] - map[position[i-1]][Y];
    sum += (dx * dx + dy * dy);
    }
    for (i = 0; i < N; i++){
    printf("%d %d, ", map[position[i]][X], map[position[i]][Y]);
    }
    printf("sum: %d\n", sum);
    if(min_distance == 0){
    min_distance = sum;
    }else if(sum < min_distance){
    min_distance = sum;
    }
    }


    inline int ok(int position[], int next, int test)
    {
    int i;

    for (i = 0; i < next; i++)
    //if (position[i] == test || (abs(test - position[i]) == next - i))
    if (position[i] == test)
    return 0;

    return 1;
    }

    void queen(int position[], int next, int row, int current_distance)
    {


    int test;

    if (next >= N) {
    //ans[row]++;
    //print_solution(position);
    #pragma omp critical
    {
    if(min_distance == 0){
    min_distance = current_distance;
    }else if(current_distance < min_distance){
    min_distance = current_distance;
    }
    }
    return;
    }

    //#pragma omp parallel for
    for (test = 0; test < N; test++)
    if (ok(position, next, test)) {
    position[next] = test;

    int dx = map[position[next]][X] - map[position[next-1]][X];
    int dy = map[position[next]][Y] - map[position[next-1]][Y];

    int added_distance = current_distance + (dx * dx + dy * dy);
    if(min_distance > 0 && added_distance > min_distance)
    continue;

    queen(position, next + 1, row, added_distance);
    }
    }


    int main(int argc, char *argv[])
    {
    scanf("%d", &N);
    int i;

    for(i = 0; i < N; i++){
    scanf("%d %d", &map[i][X], &map[i][Y]);
    }


    int position[MAX_N] = {0};
    #pragma omp parallel for private(position)
    for(i = 0; i < N; i++){
    position[0] = i;
    queen(position, 1, i, 0);
    }
    printf("%d\n", min_distance);
    return 0;
    }