# AI 꾸러미 — 외판원 순회 (배달 길 최적화) — Traveling salesman problem (TSP)
> 여러 집을 한 번씩 도는 배달 길을 가까운 곳부터 고르는 욕심 길로 만들고, 엇갈린 두 길을 풀어 잇는 2-opt 로 점점 짧게 다듬는다.  
> 견본: https://ai-techstudio.web.app/#t/i269

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 외판원 순회 (배달 길 최적화) — Traveling salesman problem (TSP)

#### 1. 목표
동네 배달 길을 외판원 순회로 풀어 줘 — 욕심 길이 먼저 그려지고, 2-opt 가 한 번씩 엇갈린 두 길(빨강)을 끊고 새 길(초록)로 이어 짧아지는 모습과 길이(km · %)가 보이게. 분위기는 밤 동네 지도.

#### 2. 핵심 기술 용어
- **Traveling salesman problem (TSP)** — 모든 곳을 한 번씩 돌고 돌아오는 가장 짧은 길
- **Nearest neighbor heuristic** — 지금 자리에서 가장 가까운 곳부터 (욕심 길)
- **2-opt local search** — 두 길을 끊고 반대로 이어 엇갈림 풀기

#### 3. 환경
- 플랫폼: HTML Canvas 2D (TypeScript), requestAnimationFrame 루프, 라이브러리 없이
- 화면: 2D · 브라우저 — PC 와 폰(390px 폭) 모두, devicePixelRatio 맞춰 또렷하게, 60fps 목표

#### 4. 조건
- 바꾸는 과정을 미리 다 계산해 기록(moves: i · k · 바꾸기 전 순서)하고, 화면은 그 기록을 한 단계씩 재생
- 바꿀 때 끊는 두 길(빨강) → 새로 잇는 두 길(초록) 순서로 보이기
- 집들은 서로 최소 거리(0.11)를 두고 뿌리기 — 겹친 점이 없게
- 욕심 길과 최종 길의 길이 · 줄어든 % 를 보이고, 욕심 길을 점선으로 겹쳐 비교

#### 5. 완성 기준 (이게 보이면 성공)
- 욕심 길이 집을 하나씩 이으며 그려지고, 길이 서로 엇갈린 곳이 보인다
- 2-opt 단계마다 엇갈림 하나가 풀리고 길이 숫자가 줄어든다
- 마지막 길에는 엇갈린 선이 없고, 점선 욕심 길보다 몇 % 짧다
- 배달할 곳 수를 40 까지 늘려도 바로 풀린다

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- 모든 순서를 다 재면 n! 가지라 16곳만 돼도 너무 많다 — 그래서 빨리 「꽤 좋은」 길을 찾는다.
- 욕심 길: 0번 집에서 시작해 아직 안 간 곳 중 가장 가까운 곳으로 가기를 되풀이.
- 2-opt: 길 a→b 와 c→d 를 끊고 a→c, b→d 로 잇는다 (그 사이 순서는 뒤집힘). 길이 변화 = D(a,c) + D(b,d) − D(a,b) − D(c,d).
- 한 번에 가장 많이 줄어드는 쌍을 골라 바꾸고, 더 줄어드는 쌍이 없을 때까지(견본 최대 60번) 되풀이하면 길이 엇갈리지 않는다.

## 핵심 코드 — 욕심 길 + 2-opt (가장 많이 줄어드는 쌍부터)
(발췌: demos/demosMapB.ts i269 gen() 을 정리)
```ts
const D = (a: number, b: number) => Math.hypot(pts[a][0] - pts[b][0], pts[a][1] - pts[b][1]);
const N = pts.length;
// 1) 욕심 길: 가장 가까운 안 간 곳으로
const used = new Uint8Array(N);
const greedy = [0];
used[0] = 1;
for (let s = 1; s < N; s++) {
  const c = greedy[greedy.length - 1];
  let b = -1;
  for (let j = 0; j < N; j++) if (!used[j] && (b < 0 || D(c, j) < D(c, b))) b = j;
  greedy.push(b); used[b] = 1;
}
// 2) 2-opt: a→b, c→d 를 a→c, b→d 로 (사이 구간 뒤집기)
const o = greedy.slice();
const moves: { i: number; k: number; before: number[] }[] = [];
for (let it = 0; it < 60; it++) {
  let best = -1e-9, bi = -1, bk = -1;
  for (let i = 1; i < N - 1; i++) for (let k = i + 1; k < N; k++) {
    const a = o[i - 1], b = o[i], c = o[k], d = o[(k + 1) % N];
    const delta = D(a, c) + D(b, d) - D(a, b) - D(c, d);
    if (delta < best) { best = delta; bi = i; bk = k; }
  }
  if (bi < 0) break;                                  // 더 줄일 쌍이 없다
  moves.push({ i: bi, k: bk, before: o.slice() });    // 화면에서 한 단계씩 다시 보여 줄 기록
  const seg = o.slice(bi, bk + 1).reverse();
  o.splice(bi, seg.length, ...seg);
}
const tourLen = (ord: number[]) => ord.reduce((L, v, i) => L + D(v, ord[(i + 1) % ord.length]), 0);
```

## 흔한 실수 · 확인 목록
- [ ] **모든 순서를 다 재려 하면 점 12개만 돼도 수억 가지라 멈춘다** — 욕심 길로 시작해 2-opt 같은 지역 개선으로 다듬는다.
- [ ] **두 길을 바꿀 때 사이 구간을 안 뒤집으면 순회가 둘로 끊긴다** — i ~ k 구간을 통째로 뒤집어야 하나의 고리가 유지된다.
- [ ] **부동소수점 때문에 0 에 가까운 변화로 끝없이 바꾼다** — 변화가 −1e-9 보다 작을 때만 바꾸고, 되풀이 횟수에 상한을 둔다.

## 완성 기준 체크리스트
- [ ] 욕심 길이 집을 하나씩 이으며 그려지고, 길이 서로 엇갈린 곳이 보인다
- [ ] 2-opt 단계마다 엇갈림 하나가 풀리고 길이 숫자가 줄어든다
- [ ] 마지막 길에는 엇갈린 선이 없고, 점선 욕심 길보다 몇 % 짧다
- [ ] 배달할 곳 수를 40 까지 늘려도 바로 풀린다

## 이 기술 정보
- id: `i269` · 분류: 지도 · 길찾기 › 길찾기 · 이동 · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 2-opt 한 번 = 쌍 n²/2 (40곳 = 780쌍), 60번까지라 문제를 바꿀 때 한 번 돌리면 된다. 견본은 바꾼 순서를 모두 적어 두고 한 단계씩 보여 준다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i269
- 쓰면 좋을 때: 배달 · 순회 순서를 정해야 할 때 / 「욕심이 늘 최선은 아니다」를 보여 줄 때 / 점이 수십 개 정도인 경로 최적화
- 쓰지 말 때: 두 점 사이 한 길만 필요할 때 — 대신 A*(i264) / 정확한 최적해가 꼭 필요한 작은 문제 — 동적 계획법(점 15개 안팎까지)으로

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### i269 견본 항목 — `src/demos/demosMapB.ts:2276`
```ts
  i269: {
    kind: '2d',
    caption: '가까운 곳부터 가는 욕심 길 → 엇갈린 두 길을 풀어 잇는 2-opt 로 점점 짧게 (빨강 = 끊는 길 · 초록 = 새로 잇는 길)',
    make() {
      let n = 16;
      let seed = 3;
      let speed = 1;
      let ghost = true;
      let pts: V2[] = [];
      let greedy: number[] = [];
      let moves: { i: number; k: number; before: number[] }[] = [];
      let finalT: number[] = [];
      let phaseT = 0;
      const AW = 1.6;
      const layer = new Layer();
      const D = (a: number, b: number): number => Math.hypot(pts[a]![0] - pts[b]![0], pts[a]![1] - pts[b]![1]);
      const tourLen = (o: number[]): number => {
        let L = 0;
        for (let i = 0; i < o.length; i++) L += D(o[i]!, o[(i + 1) % o.length]!);
        return L;
      };
      const gen = (): void => {
        const r = rng(seed);
        pts = [];
        for (let k = 0; k < 3000 && pts.length < n; k++) {
          const p: V2 = [0.06 + r() * (AW - 0.12), 0.07 + r() * 0.86];
          if (pts.every((q) => Math.hypot(q[0] - p[0], q[1] - p[1]) > 0.11)) pts.push(p);
        }
        const N = pts.length;
        const used = new Uint8Array(N);
        greedy = [0];
        used[0] = 1;
        for (let s = 1; s < N; s++) {
          const c = greedy[greedy.length - 1]!;
          let b = -1;
          for (let j = 0; j < N; j++) if (!used[j] && (b < 0 || D(c, j) < D(c, b))) b = j;
          greedy.push(b);
          used[b] = 1;
        }
        const o = greedy.slice();
        moves = [];
        for (let it = 0; it < 60; it++) {
          let best = -1e-9;
          let bi = -1;
          let bk = -1;
          for (let i = 1; i < N - 1; i++)
            for (let k = i + 1; k < N; k++) {
              const a = o[i - 1]!;
              const b = o[i]!;
              const c = o[k]!;
              const d = o[(k + 1) % N]!;
              const delta = D(a, c) + D(b, d) - D(a, b) - D(c, d);
              if (delta < best) {
                best = delta;
                bi = i;
                bk = k;
              }
            }
          if (bi < 0) break;
          moves.push({ i: bi, k: bk, before: o.slice() });
          const seg = o.slice(bi, bk + 1).reverse();
          o.splice(bi, seg.length, ...seg);
        }
        finalT = o;
        phaseT = 0;
      };
      gen();
      const HOUSE = ['#ff8fa3', '#8ecae6', '#ffd166', '#b8f2a1', '#cdb4ff'];
      return {
        draw(g, w, h, _t, dt) {
          reset(g);
          const u = scaleOf(w, h);
          const dpr = dprOf(g);
          phaseT += Math.min(dt, 0.1) * speed;
          const N = pts.length;
          const tBuild = N * 0.11;
          const tMove = 0.62;
          const tOpt = tBuild + 0.4 + moves.length * tMove;
          const tEnd = tOpt + 3.2;
          if (phaseT > tEnd) {
            seed++;
            gen();
          }
          const headH = 17 * u;
          const k = Math.min((w - 12 * u) / AW, h - headH - 8 * u);
          const ox = (w - AW * k) / 2;
          const oy = headH + 2 * u;
          const S = (i: number): V2 => [ox + pts[i]![0] * k, oy + pts[i]![1] * k];
          const L = layer.get(`${seed}|${n}|${w}|${h}|${dpr}`, w, h, dpr, (lg) => {
            bgGrad(lg, w, h, '#18233c', '#0d1424');
            rr(lg, ox - 4 * u, oy - 4 * u, AW * k + 8 * u, k + 8 * u, 7 * u);
            lg.fillStyle = '#1f2c48';
            lg.fill();
            lg.save();
            lg.clip();
            // 동네 블록 · 공원 · 강
            const r = rng(seed + 5);
            const bs = 0.1 * k;
            for (let y = oy - 4 * u; y < oy + k; y += bs)
              for (let x = ox - 4 * u; x < ox + AW * k; x += bs) {
                const park = r() < 0.08;
                rr(lg, x + bs * 0.12, y + bs * 0.12, bs * 0.76, bs * 0.76, bs * 0.12);
                lg.fillStyle = park ? '#24503f' : '#26355a';
                lg.fill();
                if (park) {
                  lg.fillStyle = '#2f6b50';
                  lg.beginPath();
                  lg.arc(x + bs * 0.4, y + bs * 0.45, bs * 0.16, 0, TAU);
                  lg.arc(x + bs * 0.62, y + bs * 0.6, bs * 0.12, 0, TAU);
                  lg.fill();
                }
              }
            lg.strokeStyle = 'rgba(70,140,220,0.55)';
            lg.lineWidth = bs * 0.5;
            lg.lineCap = 'round';
            lg.beginPath();
            lg.moveTo(ox + AW * k * 0.62, oy - 10);
            lg.bezierCurveTo(ox + AW * k * 0.5, oy + k * 0.35, ox + AW * k * 0.78, oy + k * 0.6, ox + AW * k * 0.66, oy + k + 10);
            lg.stroke();
            lg.restore();
          });
          g.drawImage(L, 0, 0, w, h);
          // 지금 순서 · 길
          let order: number[];
          let edges = 0;
          let mv: { i: number; k: number; before: number[] } | null = null;
          let mk2 = 0;
          if (phaseT < tBuild) {
            order = greedy;
            edges = Math.floor(phaseT / 0.11);
          } else if (phaseT < tOpt) {
            const m = Math.floor((phaseT - tBuild - 0.4) / tMove);
            if (m < 0) order = greedy;
            else {
              mv = moves[Math.min(m, moves.length - 1)]!;
              order = mv.before;
              mk2 = (phaseT - tBuild - 0.4 - m * tMove) / tMove;
            }
            edges = N;
          } else {
            order = finalT;
            edges = N;
          }
          const lw = Math.max(1.6, 2.2 * u);
          if (ghost && phaseT >= tOpt) {
            g.setLineDash([3 * u, 3 * u]);
            g.strokeStyle = 'rgba(255,170,90,0.45)';
            g.lineWidth = 1.2 * u;
            g.beginPath();
            greedy.forEach((i, q) => {
              const p = S(i);
              if (q) g.lineTo(p[0], p[1]);
              else g.moveTo(p[0], p[1]);
            });
            g.closePath();
            g.stroke();
            g.setLineDash([]);
          }
          const skip = new Set<string>();
          if (mv && mk2 < 1) {
            const a = order[mv.i - 1]!;
            const b = order[mv.i]!;
            const c = order[mv.k]!;
            const d = order[(mv.k + 1) % N]!;
            skip.add(a + '-' + b);
            skip.add(c + '-' + d);
          }
          g.lineCap = 'round';
          g.lineJoin = 'round';
          g.beginPath();
          for (let q = 0; q < Math.min(edges, N); q++) {
            const a = order[q]!;
            const b = q + 1 < N ? order[q + 1]! : order[0]!;
            if (q + 1 >= N && phaseT < tBuild) break;
            if (skip.has(a + '-' + b)) continue;
            const pa = S(a);
            const pb = S(b);
            g.moveTo(pa[0], pa[1]);
            g.lineTo(pb[0], pb[1]);
          }
          g.strokeStyle = 'rgba(80,200,255,0.25)';
          g.lineWidth = lw * 3;
          g.stroke();
          g.strokeStyle = '#6ad1ff';
          g.lineWidth = lw;
          g.stroke();
          if (phaseT < tBuild && edges < N) {
            const a = S(order[edges]!);
            const b = S(order[Math.min(edges + 1, N - 1)]!);
            const f = (phaseT % 0.11) / 0.11;
            g.strokeStyle = '#fff';
            g.lineWidth = lw;
            g.beginPath();
            g.moveTo(a[0], a[1]);
            g.lineTo(lerp(a[0], b[0], f), lerp(a[1], b[1], f));
            g.stroke();
          }
          if (mv && mk2 < 1) {
            const a = S(order[mv.i - 1]!);
            const b = S(order[mv.i]!);
            const c = S(order[mv.k]!);
            const d = S(order[(mv.k + 1) % N]!);
            const blink = 0.55 + 0.45 * Math.sin(phaseT * 30);
            const old = 1 - smooth(0.45, 0.8, mk2);
            g.strokeStyle = `rgba(255,70,90,${old * blink})`;
            g.lineWidth = lw * 1.3;
            g.beginPath();
            g.moveTo(a[0], a[1]);
            g.lineTo(b[0], b[1]);
            g.moveTo(c[0], c[1]);
            g.lineTo(d[0], d[1]);
            g.stroke();
            const nk = smooth(0.35, 0.85, mk2);
            g.strokeStyle = '#5dff9a';
            g.lineWidth = lw * 1.3;
            g.beginPath();
            g.moveTo(a[0], a[1]);
            g.lineTo(lerp(a[0], c[0], nk), lerp(a[1], c[1], nk));
            g.moveTo(b[0], b[1]);
            g.lineTo(lerp(b[0], d[0], nk), lerp(b[1], d[1], nk));
            g.stroke();
          }
          // 집 · 창고
          for (let i = 0; i < N; i++) {
            const [x, y] = S(i);
            const s = 7 * u;
            if (i === 0) {
              g.fillStyle = 'rgba(0,0,0,0.4)';
              g.fillRect(x - s * 1.1 + 2 * u, y - s * 0.4 + 2 * u, s * 2.2, s * 1.2);
              g.fillStyle = '#ffd166';
              g.fillRect(x - s * 1.1, y - s * 0.4, s * 2.2, s * 1.2);
              g.fillStyle = '#e09f3e';
              g.beginPath();
              g.moveTo(x - s * 1.3, y - s * 0.35);
              g.lineTo(x, y - s * 1.1);
              g.lineTo(x + s * 1.3, y - s * 0.35);
              g.fill();
              g.fillStyle = '#7a4b16';
              g.fillRect(x - s * 0.4, y + s * 0.1, s * 0.8, s * 0.7);
              continue;
            }
            g.fillStyle = 'rgba(0,0,0,0.4)';
            g.fillRect(x - s * 0.5 + 1.5 * u, y - s * 0.2 + 1.5 * u, s, s * 0.8);
            g.fillStyle = '#f4ead8';
            g.fillRect(x - s * 0.5, y - s * 0.2, s, s * 0.8);
            g.fillStyle = HOUSE[i % HOUSE.length]!;
            g.beginPath();
            g.moveTo(x - s * 0.7, y - s * 0.15);
            g.lineTo(x, y - s * 0.8);
            g.lineTo(x + s * 0.7, y - s * 0.15);
            g.fill();
            g.fillStyle = '#6b4a2a';
            g.fillRect(x - s * 0.15, y + s * 0.2, s * 0.3, s * 0.4);
          }
          // 트럭
          if (phaseT >= tOpt) {
            const poly = [...finalT.map(S), S(finalT[0]!)];
            const tk = ((phaseT - tOpt) / 3.2) % 1;
            const [p, ang] = alongPoly(poly, ease(tk) * polyLen(poly));
            g.save();
            g.translate(p[0], p[1]);
            g.rotate(ang);
            const s = 6 * u;
            g.fillStyle = 'rgba(0,0,0,0.4)';
            g.fillRect(-s + 1.5 * u, -s * 0.5 + 1.5 * u, s * 2, s);
            g.fillStyle = '#ff6b6b';
            g.fillRect(-s, -s * 0.55, s * 1.3, s * 1.1);
            g.fillStyle = '#ffe3e3';
            g.fillRect(s * 0.35, -s * 0.45, s * 0.65, s * 0.9);
            g.fillStyle = '#334';
            g.fillRect(s * 0.7, -s * 0.38, s * 0.22, s * 0.76);
            g.restore();
          }
          const curLen = phaseT < tBuild ? -1 : tourLen(mv ? (mk2 > 0.8 ? moves[moves.indexOf(mv) + 1]?.before ?? finalT : order) : order);
          const gl = tourLen(greedy);
          txt(g, phaseT < tBuild ? '욕심 길 만들기' : phaseT < tOpt ? '2-opt 고치기' : '다 고쳤어요', 8 * u, headH / 2 + 1 * u, 10.5 * u, phaseT < tBuild ? '#ffb86b' : '#5dff9a', 'left', 900);
          if (curLen > 0) {
            const pct = Math.round((1 - curLen / gl) * 100);
            pill(g, `길이 ${(gl * 10).toFixed(1)} → ${(curLen * 10).toFixed(1)} km${pct > 0 ? ` (−${pct}%)` : ''}`, w - 6 * u, headH / 2 + 1 * u, 7.5 * u, 'rgba(255,255,255,0.12)', '#e8ecff', 'right');
          } else pill(g, `배달할 곳 ${N - 1}군데`, w - 6 * u, headH / 2 + 1 * u, 7.5 * u, 'rgba(255,255,255,0.12)', '#e8ecff', 'right');
        },
        controls: [
          { type: 'range', label: '배달할 곳 수', min: 8, max: 40, step: 1, value: 16, on: (v) => ((n = v), gen()) },
          { type: 'range', label: '속도', min: 0.3, max: 3, step: 0.1, value: 1, on: (v) => (speed = v) },
          { type: 'toggle', label: '욕심 길 겹쳐 보기 (점선)', value: true, on: (v) => (ghost = v) },
          { type: 'button', label: '새 문제', on: () => (seed++, gen()) },
        ] as Control[],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [A* 길찾기 (열린 · 닫힌 칸 보기)](https://ai-techstudio.web.app/ai/t/i264.md) `i264`
- 다음에 해 볼 기술: [그래프 지도 (노선도 · 지하철)](https://ai-techstudio.web.app/ai/t/i270.md) `i270`
- 참고 문서: [Wikipedia — Travelling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) · [Wikipedia — 2-opt](https://en.wikipedia.org/wiki/2-opt)