Nearest neighbor with 2-opt refinement

// Candidate: nearest-neighbor construction followed by first-improvement 2-opt.
// Deterministic (no time-dependent decisions, no randomness). O(n^2) per 2-opt pass.
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);
  };

  // Nearest-neighbor tour from vertex 0 (same start as the baseline).
  const visited = new Uint8Array(n);
  const tour = new Array(n);
  tour[0] = 0;
  visited[0] = 1;
  let current = 0;
  for (let k = 1; k < n; k++) {
    let best = -1;
    let bestDistance = Infinity;
    for (let j = 0; j < n; j++) {
      if (visited[j]) continue;
      const dx = xs[current] - xs[j];
      const dy = ys[current] - ys[j];
      const distance = dx * dx + dy * dy;
      if (distance < bestDistance) {
        bestDistance = distance;
        best = j;
      }
    }
    visited[best] = 1;
    tour[k] = best;
    current = best;
  }

  // 2-opt: remove edges (a,b) and (c,e), add (a,c) and (b,e) by reversing b..c.
  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;
  }
  return tour;
}