Approach Guided Local Search(GLS) 。 TCO2016 MM R3 で CatalinT さんが使ったものと本質的に同じもの。


Score

kosakkunさんの適当なSAGLS
1494.01053692588624485.4605733810348
2530.1168033455548517.7671599235256
3367.93392449788024360.1746149965883
4493.59914978630474486.95184401291823
5364.88013978229515364.41532260772044
6304.6700126557216301.3079655440071
7482.3144426341467469.5112459237517
8579.3091643733519572.0601824834589
9352.68717930411583345.82962544607824
10558.819510787507553.5887500736407




source code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class EuclideanTravellingSalesmanProblem {
private static final long START = System.nanoTime();
private static final long END = (long) (START + 9.8 * 1e9);
private int N;
private double[][] distance;

private int[] nodeToCity;
private double score;

private int[] bestNodeToCity;
private double bestScore;

public int[] getOrder(double[] x, double[] y) {
init(x, y);
GLS();
return nodeToCity;
}

private void init(double[] x, double[] y) {
this.N = x.length;

nodeToCity = new int[N];
bestNodeToCity = new int[N];
for (int i = 0; i < nodeToCity.length; i++) {
nodeToCity[i] = i;
}

distance = new double[N][N];
for (int i = 0; i < distance.length; i++) {
for (int j = 0; j < i; j++) {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
distance[i][j] = Math.sqrt(dx * dx + dy * dy);
distance[j][i] = distance[i][j];
}
}

score = calculateScore();
bestScore = score;

}

private void GLS() {
double[][] penalty = new double[N][N];
int[] maxUtilNodes = new int[N];
boolean[] isTarget = new boolean[N];
Arrays.fill(isTarget, true);

for (int iteration = 0;; iteration++) {
if ((iteration & ((1 << 10) - 1)) == 0) {
if (System.nanoTime() >= END) {
score = bestScore;
System.arraycopy(bestNodeToCity, 0, nodeToCity, 0, N);
break;
}
}

for (int i = 0, node = 0; i < N; i++, node = (node + 1) % N) {
if (!isTarget[nodeToCity[node]]) {
continue;
}

int B = node;
int A = B - 1;
if (A < 0) {
A = N - 1;
}

boolean update = false;
for (int node2 = 0; node2 < N; node2++) {
if (node2 == node) {
continue;
}
int C = node2;
int D = node2 + 1;
if (D == N) {
D = 0;
}

if (C == A) {
continue;
}
if (D == B) {
continue;
}

double A_BC_D = distance[nodeToCity[A]][nodeToCity[B]] + distance[nodeToCity[C]][nodeToCity[D]];
double A_CB_D = distance[nodeToCity[A]][nodeToCity[C]] + distance[nodeToCity[B]][nodeToCity[D]];
double deltaScore = A_CB_D - A_BC_D;

double pA_BC_D = penalty[nodeToCity[A]][nodeToCity[B]] + penalty[nodeToCity[C]][nodeToCity[D]];
double pA_CB_D = penalty[nodeToCity[A]][nodeToCity[C]] + penalty[nodeToCity[B]][nodeToCity[D]];
double deltaPenalty = (0.3 * bestScore / N) * (pA_CB_D - pA_BC_D);

if (deltaScore + deltaPenalty < 0) {
update = true;
score += deltaScore;

if (B <= C) {
for (int l = B, r = C; l < r; l++, r--) {
int swap = nodeToCity[l];
nodeToCity[l] = nodeToCity[r];
nodeToCity[r] = swap;
}
} else {
for (int l = C + 1, r = B - 1; l < r; l++, r--) {
int swap = nodeToCity[r];
nodeToCity[r] = nodeToCity[l];
nodeToCity[l] = swap;
}
}

if (score < bestScore) {
bestScore = score;
System.arraycopy(nodeToCity, 0, bestNodeToCity, 0, N);
}

break;
}

}

if (update) {
i = -1;
} else {
isTarget[nodeToCity[node]] = false;
}
}

double maxUtil = -1e9;
int size = 0;
for (int node = 0; node < N; node++) {
double util = distance[nodeToCity[node]][nodeToCity[(node + 1) % N]] / (penalty[nodeToCity[node]][nodeToCity[(node + 1) % N]] + 1.0);
if (util > maxUtil) {
maxUtil = util;
size = 0;
maxUtilNodes[size++] = node;
} else if (Math.abs(util - maxUtil) < 1e-5) {
maxUtilNodes[size++] = node;
}
}
for (int i = 0; i < size; i++) {
int node = maxUtilNodes[i];
int city1 = nodeToCity[node];
int city2 = nodeToCity[(node + 1) % N];
penalty[city1][city2]++;
penalty[city2][city1]++;
isTarget[city1] = true;
isTarget[city2] = true;
}

}
}

private double calculateScore() {
double score = 0.0;
for (int i = 0; i < N; i++) {
score += distance[nodeToCity[i]][nodeToCity[(i + 1) % N]];
}
return score;
}

public static void main(String[] args) {
EuclideanTravellingSalesmanProblem o = new EuclideanTravellingSalesmanProblem();

try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {

int N = Integer.parseInt(reader.readLine().trim());
double[] x = new double[N];
double[] y = new double[N];
for (int i = 0; i < N; i++) {
String[] split = reader.readLine().trim().split(" ");
x[i] = Double.parseDouble(split[0]);
y[i] = Double.parseDouble(split[1]);
}

int[] ret = o.getOrder(x, y);

StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++)
sb.append(ret[i] + "\n");

System.out.println(sb.toString());
System.out.flush();

} catch (IOException e) {
e.printStackTrace();
}
}
}