Greedy construction combined with 2-opt and Or-opt

// Candidate: combines the greedy edge construction (03) with the 2-opt + Or-opt local
// search (02): shortest-edges-first tour, then 2-opt and Or-opt alternated to a local
// optimum. Deterministic.
export function solve(instance) {
  const points = instance.points;
  const n = points.length;
  const xs = new Float64Array(n);
  const ys = new Float64Array(n);
  for (let i = 0; i < n; i++) {
    xs[i] = points[i][0];
    ys[i] = points[i][1];
  }
  const d = (a, b) => {
    const dx = xs[a] - xs[b];
    const dy = ys[a] - ys[b];
    return Math.sqrt(dx * dx + dy * dy);
  };

  let tour = greedyEdgeTour(n, d);
  for (let round = 0; round < 40; round++) {
    const before = tourLength(tour, d);
    twoOpt(tour, d);
    tour = orOpt(tour, d);
    if (tourLength(tour, d) > before - 1e-9) break;
  }
  return tour;
}

function tourLength(tour, d) {
  let total = 0;
  for (let i = 0; i < tour.length; i++) total += d(tour[i], tour[(i + 1) % tour.length]);
  return total;
}

function greedyEdgeTour(n, d) {
  if (n < 3) return Array.from({ length: n }, (_, i) => i);
  const m = (n * (n - 1)) / 2;
  const eu = new Int32Array(m);
  const ev = new Int32Array(m);
  const len = new Float64Array(m);
  let t = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      eu[t] = i;
      ev[t] = j;
      len[t] = d(i, j);
      t++;
    }
  }
  const order = new Array(m);
  for (let i = 0; i < m; i++) order[i] = i;
  order.sort((a, b) => len[a] - len[b] || a - b);
  const parent = new Int32Array(n);
  for (let i = 0; i < n; i++) parent[i] = i;
  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  const degree = new Uint8Array(n);
  const adjacentA = new Int32Array(n).fill(-1);
  const adjacentB = new Int32Array(n).fill(-1);
  const link = (u, v) => {
    if (adjacentA[u] === -1) adjacentA[u] = v;
    else adjacentB[u] = v;
    if (adjacentA[v] === -1) adjacentA[v] = u;
    else adjacentB[v] = u;
    degree[u]++;
    degree[v]++;
  };
  let added = 0;
  for (let k = 0; k < m && added < n - 1; k++) {
    const e = order[k];
    const u = eu[e];
    const v = ev[e];
    if (degree[u] >= 2 || degree[v] >= 2) continue;
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) continue;
    parent[ru] = rv;
    link(u, v);
    added++;
  }
  const ends = [];
  for (let i = 0; i < n; i++) if (degree[i] === 1) ends.push(i);
  if (ends.length === 2) link(ends[0], ends[1]);
  const tour = new Array(n);
  let previous = -1;
  let current = 0;
  for (let k = 0; k < n; k++) {
    tour[k] = current;
    const next = adjacentA[current] !== previous ? adjacentA[current] : adjacentB[current];
    previous = current;
    current = next;
  }
  return tour;
}

function twoOpt(tour, d) {
  const n = tour.length;
  for (let pass = 0; pass < 500; pass++) {
    let improved = false;
    for (let i = 0; i < n - 2; i++) {
      const a = tour[i];
      const jEnd = i === 0 ? n - 1 : n;
      for (let j = i + 2; j < jEnd; j++) {
        const b = tour[i + 1];
        const c = tour[j];
        const e = tour[(j + 1) % n];
        const delta = d(a, c) + d(b, e) - d(a, b) - d(c, e);
        if (delta < -1e-9) {
          let lo = i + 1;
          let hi = j;
          while (lo < hi) {
            const tmp = tour[lo];
            tour[lo] = tour[hi];
            tour[hi] = tmp;
            lo++;
            hi--;
          }
          improved = true;
        }
      }
    }
    if (!improved) break;
  }
}

function orOpt(tour, d) {
  const n = tour.length;
  if (n < 8) return tour;
  for (let pass = 0; pass < 100; pass++) {
    let improved = false;
    for (let len = 1; len <= 3; len++) {
      for (let i = 0; i + len <= n; i++) {
        const prev = tour[(i - 1 + n) % n];
        const first = tour[i];
        const last = tour[i + len - 1];
        const next = tour[(i + len) % n];
        const removeGain = d(prev, first) + d(last, next) - d(prev, next);
        if (removeGain <= 1e-9) continue;
        let best = 1e-9;
        let bestK = -1;
        let bestReversed = false;
        for (let k = 0; k < n; k++) {
          if ((((k - (i - 1)) % n) + n) % n <= len) continue;
          const u = tour[k];
          const v = tour[(k + 1) % n];
          const base = d(u, v);
          const gainForward = removeGain - (d(u, first) + d(last, v) - base);
          if (gainForward > best) {
            best = gainForward;
            bestK = k;
            bestReversed = false;
          }
          const gainReversed = removeGain - (d(u, last) + d(first, v) - base);
          if (gainReversed > best) {
            best = gainReversed;
            bestK = k;
            bestReversed = true;
          }
        }
        if (bestK >= 0) {
          const segment = tour.slice(i, i + len);
          if (bestReversed) segment.reverse();
          const anchor = tour[bestK];
          const rest = tour.slice(0, i).concat(tour.slice(i + len));
          const at = rest.indexOf(anchor);
          tour = rest.slice(0, at + 1).concat(segment, rest.slice(at + 1));
          improved = true;
        }
      }
    }
    if (!improved) break;
  }
  return tour;
}