TSPparallel.c

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