제1부 수학적 기초

1.23 이산 수학: 그래프 이론·조합 최적화·할당 문제(헝가리안 알고리즘)·외판원 문제(TSP)

1.23.1 이 장에서 배우는 것 / 선수 지식 / 특히 중요한 독자

이 장은 로봇의 이산적 결정, 곧 어느 로봇이 어느 과업을 맡고 어떤 순서로 방문하는가를 다루는 이산 수학과 조합 최적화를 정리한다. 그래프는 이런 문제의 공통 언어이고, 할당 문제는 이분 그래프의 최소 비용 완전 매칭이며 다항 시간에 정확히 풀린다. 외판원 문제(traveling salesman problem, TSP)는 방문 순서를 정하는 문제로 정확한 해법이 지수 시간이며 휴리스틱과 근사 알고리즘이 사용된다. 다룰 질문은 다섯 가지다. 그래프와 신장 트리는 어떤 표현·연산을 갖는가, 할당 문제는 어떤 쌍대 구조를 가지며 헝가리안 알고리즘은 어떻게 최적성을 보장하는가, 탐욕 할당은 최적에서 얼마나 벗어나는가, TSP의 정확해·휴리스틱·근사는 얼마나 차이 나고 계산 시간은 어떻게 늘어나는가, 라이브러리(SciPy·NetworkX·OR-Tools)는 같은 입력에서 어떤 결과를 내는가.

배우는 것:

• 그래프 — 표현, 연결, 신장 트리, 최소 신장 트리(MST).
• 할당 문제 — 선형 계획 형식, 쌍대(퍼텐셜), 헝가리안 알고리즘, 탐욕과의 비교.
• 외판원 문제 — 헬드-카프 정확해, 최근접 이웃·2-opt, MST 이중 순회와 Christofides의 근사 보장.
• 계산 복잡도 — 다항 시간(할당)과 지수 시간(TSP 정확해)의 실측 차이.
• 라이브러리 — SciPy linear_sum_assignment, NetworkX, OR-Tools 경로 탐색.

선수 지식: 1.13(선형 계획·쌍대성), 기초 확률(1.19). 그래프 탐색(다익스트라·A*)은 11.3, 다중 로봇 작업 할당(경매·CBBA)은 24.2, 커버리지 순서는 11.22·24.12이 다룬다.

특히 중요한 독자: 다중 로봇 작업 할당과 방문 순서를 구현하는 엔지니어, 조합 최적화 라이브러리를 선택하는 연구자, 계획 알고리즘의 계산 비용을 평가하는 소프트웨어 개발자.

출처 방침. 서지는 Crossref 응답으로 확인했다(목록은 이 장 끝). 직접 읽은 자료: ① SciPy linear_sum_assignment의 문서(수정 Jonker-Volgenant 알고리즘, 참고 문헌), ② NetworkX christofides의 문서(3/2 근사, 완전 가중 무방향 그래프 요구, 인용 문헌). 직접 실행한 것: SciPy 1.18.1·NetworkX 3.7·OR-Tools 9.15.6755(Python 3.12, NumPy 2.5.4). 읽지 못한 것: 인용한 논문·교과서의 본문(정리 번호는 (확인 필요)), NetworkX·OR-Tools의 소스와 GitHub 저장소 정보(조회 시 GitHub API 한도가 초과되어 PyPI 메타데이터만 확인). 이 장의 수치는 순수 파이썬 구현으로 계산했다.

1.23.2 개념 — 짝짓기와 순서 정하기

창고의 로봇 $n$대에 과업 $n$개를 하나씩 맡길 때 각 짝의 비용(이동 거리)이 주어지면 총 비용이 가장 작은 짝짓기를 찾는 것이 할당 문제이다. 로봇 한 대가 점 $n$개를 모두 방문하고 돌아올 때 가장 짧은 순서를 찾는 것이 TSP이다. 두 문제는 모양이 비슷하지만 계산 난이도가 다르다. 할당은 $n^3$에 비례하는 시간 안에 정확히 풀리고, TSP는 정확해에 필요한 시간이 도시 수에 대해 지수로 늘어난다.

탐욕 전략(가장 싼 짝을 먼저 확정)은 구현이 단순하지만 최적이 아니다. 아래 도해는 같은 위치에서 탐욕 할당과 최적 할당의 총 거리를 비교한다.

1.23.3 원리

1.23.3.1 그래프와 신장 트리

결론: 그래프는 정점 집합과 간선 집합이며 로봇공학의 이산 구조(지도·과업·로봇 사이의 관계)를 담는다. 최소 신장 트리는 모든 정점을 잇는 가장 가벼운 트리이며 TSP의 근사에도 사용된다.

그래프 $G=(V,E)$에 간선 가중치 $w:E\to\mathbb R$을 더하면 가중 그래프이다. 구현은 인접 리스트(희소)나 인접 행렬(조밀)을 사용한다. 연결 그래프의 신장 트리는 정점 $n$개와 간선 $n-1$개의 부분 그래프이며, 가중치 합이 최소인 것이 최소 신장 트리(MST)이다. Prim 알고리즘은 한 정점에서 시작해 트리와 나머지 정점 사이의 가장 싼 간선을 반복 추가하며 조밀 그래프에서 $O(n^2)$이다(이 장의 prim_tree). MST의 정당성은 절단 성질에 의존한다 (확인 필요: 정리 번호). 최단 경로 탐색(Dijkstra 1959)과 휴리스틱 탐색은 11.3가 다룬다.

1.23.3.2 할당 문제와 헝가리안 알고리즘

결론: 할당 문제의 선형 계획 완화는 정수 해를 갖고 쌍대 변수(퍼텐셜)가 최적성의 인증이 되며, 헝가리안 알고리즘은 이 퍼텐셜을 유지하면서 증가 경로로 짝을 늘려 $O(n^3)$에 최적해를 낸다.

비용 $c_{ij}$와 순열 행렬 $X=[x_{ij}]$에 대해

$$\min_X\sum_{i,j}c_{ij}x_{ij}\quad\text{s.t.}\quad\sum_jx_{ij}=1,\ \sum_ix_{ij}=1,\ x_{ij}\ge0$$

의 실현 가능 영역의 꼭짓점이 순열 행렬이므로 선형 계획 완화가 정수 해를 갖는다(Birkhoff–von Neumann 정리로 알려져 있으며 출처는 (확인 필요)). 쌍대 문제는

$$\max_{u,v}\ \sum_iu_i+\sum_jv_j\quad\text{s.t.}\quad u_i+v_j\le c_{ij}$$

이고, 최적에서 짝지어진 $(i,j)$는 $c_{ij}-u_i-v_j=0$(상보 여유성)이다. 헝가리안 알고리즘(Kuhn 1955, Munkres 1957)은 $c_{ij}-u_i-v_j\ge0$을 유지하면서 환산 비용이 0인 간선만으로 짝을 늘리고, 막히면 퍼텐셜을 조정한다. 이 장의 구현은 한 행씩 최단 증가 경로를 찾는 퍼텐셜 방식이다. 가장 나쁜 경우의 비용은 $O(n^3)$이고, 직사각 행렬과 더 빠른 구현은 Jonker & Volgenant(1987)와 Crouse(2016)가 다룬다.

1.23.3.3 외판원 문제

결론: TSP의 정확해는 헬드-카프 동적 계획으로 $O(n^22^n)$이어서 $n$이 수십 이상이면 사용할 수 없고, 로봇 응용에서는 최근접 이웃·2-opt 같은 휴리스틱이나 근사 알고리즘을 사용한다.

TSP는 NP-난해로 알려져 있다 (확인 필요: 출처). 정확해의 동적 계획(Held & Karp 1962; Bellman 1962)은 상태 $(S,j)$($S$는 방문한 도시 집합, $j$는 마지막 도시)에서 $dp[S][j]=\min_{k\in S\setminus\{j\}}\bigl(dp[S\setminus\{j\}][k]+d_{kj}\bigr)$이며 상태 수가 $(n-1)2^{n-1}$이다. 휴리스틱은 다음과 같다.

Christofides의 보장은 NetworkX의 문서가 3/2 근사라고 밝힌 것을 읽었다(원 보고서의 본문은 읽지 않았다). 삼각 부등식을 만족하지 않는 비용에서는 이 보장이 성립하지 않는다.

1.23.3.4 로봇공학에서의 쓰임과 비용 행렬

할당 비용은 유클리드 거리 외에 실제 경로 길이(11.3)나 소요 시간, 배터리 소모일 수 있다. 이 경우 비용 행렬의 각 칸이 경로 탐색 한 번의 결과이다. 로봇이 과업을 여러 개 맡는 다중 할당(경매·CBBA)은 24.2이 다루며 단일 과업 할당은 이 장의 헝가리안 알고리즘이 정확해를 낸다. TSP는 점검·커버리지·픽업 순서에 나타나며(11.22·24.12), 정수 계획으로의 정식화는 1.14가 다룬다.

1.23.3.5 라이브러리

1.23.4 알고리즘

헝가리안(퍼텐셜), 헬드-카프, 2-opt, MST 이중 순회

헝가리안(C):  u, v ← 0 ;  행 i = 1..n에 대해:
    최단 증가 경로: 열 j의 환산 비용 minv[j] = c[i0][j] − u[i0] − v[j] 갱신,
    최솟값 δ에 대해 방문한 열은 (u += δ, v −= δ), 아니면 minv −= δ
    빈 열에 닿으면 경로를 따라 짝을 바꿈 ;  총 비용 = Σ c[i][짝(i)]
헬드-카프(D):  dp[{j}][j] ← d[0][j] ;  S 증가 순서로
    dp[S ∪ {k}][k] ← min( dp[S][j] + d[j][k] ) ;  답 = min_j dp[전체][j] + d[j][0]
2-opt(t):     i < j에 대해 d(a,c)+d(b,d) < d(a,b)+d(c,d)이면 구간 (i+1..j) 뒤집기, 개선이 없을 때까지
MST 이중 순회: Prim으로 MST ;  0에서 선순회한 순서로 방문

구현은 1.23.5의 코드에 있다.

1.23.5 풀이 예제 — 할당·TSP의 최적성·휴리스틱 간극·계산 시간과 라이브러리 확인

헝가리안 알고리즘을 브루트포스와 쌍대 인증으로 검증하고, 무작위 로봇·과업에서 탐욕 할당과 최적 할당의 총 거리를 비교하며, 무작위 12개 도시에서 휴리스틱을 헬드-카프의 정확해와 비교하고, 계산 시간의 증가를 측정한 뒤 SciPy·NetworkX·OR-Tools와 대조한다. 결론부터 적으면 다음과 같다. ① 헝가리안 알고리즘의 최적 비용은 브루트포스와 일치하고 쌍대 인증(환산 비용의 최솟값 $-1.8\times10^{-14}$, 쌍대 목적과 비용의 차이 $5.7\times10^{-14}$)이 성립한다. ② 탐욕 할당의 총 거리는 최적보다 평균 10.0%($n=10$)~18.7%($n=40$) 길고 최대 45.7%이다. ③ 12개 도시에서 최근접 이웃은 평균 10.5%, 2-opt를 더하면 0.9%, MST 이중 순회는 16.9% 최적을 넘는다. ④ 헬드-카프의 시간은 도시 하나가 늘 때 2배 이상 늘고(표), 무작위 입력에서 헝가리안의 시간은 $n^3$보다 완만하게 늘었다. ⑤ SciPy와 최적 비용이 $0.0$으로 일치하고 OR-Tools는 12개 도시 30개 사례에서 모두 최적이다.

구현. hungarian·greedy_assign·held_karp·nearest_neighbor·two_opt·prim_tree·double_tree·tour_len

import math

def hungarian(C):
    """최소 비용 완전 할당 O(n^3): 퍼텐셜·증가 경로"""
    n, INF = len(C), float('inf')
    u, v = [0.0] * (n + 1), [0.0] * (n + 1)
    p, way = [0] * (n + 1), [0] * (n + 1)
    for i in range(1, n + 1):
        p[0], j0 = i, 0
        minv, used = [INF] * (n + 1), [False] * (n + 1)
        while True:
            used[j0] = True
            i0, delta, j1 = p[j0], INF, 0
            for j in range(1, n + 1):
                if not used[j]:
                    cur = C[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j], way[j] = cur, j0
                    if minv[j] < delta:
                        delta, j1 = minv[j], j
            for j in range(n + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while j0:
            p[j0] = p[way[j0]]
            j0 = way[j0]
    asg = [0] * n
    for j in range(1, n + 1):
        asg[p[j] - 1] = j - 1
    cost = sum(C[i][asg[i]] for i in range(n))
    return asg, cost, u[1:], v[1:]

def greedy_assign(C):
    """가장 싼 (행, 열) 쌍을 반복해서 고른다"""
    n = len(C)
    pairs = sorted((C[i][j], i, j) for i in range(n)
                   for j in range(n))
    ri, cj, asg = set(), set(), [0] * n
    for c, i, j in pairs:
        if i not in ri and j not in cj:
            asg[i] = j
            ri.add(i)
            cj.add(j)
    return asg, sum(C[i][asg[i]] for i in range(n))

def tour_len(D, t):
    n = len(t)
    return sum(D[t[i]][t[(i + 1) % n]] for i in range(n))

def held_karp(D):
    """정확한 TSP: dp[S][j] = S를 거쳐 j에서 끝나는 최단"""
    n, INF = len(D), float('inf')
    m, N = n - 1, 1 << (n - 1)
    dp = [[INF] * m for _ in range(N)]
    par = [[-1] * m for _ in range(N)]
    for j in range(m):
        dp[1 << j][j] = D[0][j + 1]
    for S in range(1, N):
        for j in range(m):
            if not (S >> j) & 1 or dp[S][j] == INF:
                continue
            for k in range(m):
                if (S >> k) & 1:
                    continue
                T = S | (1 << k)
                c = dp[S][j] + D[j + 1][k + 1]
                if c < dp[T][k]:
                    dp[T][k], par[T][k] = c, j
    S = N - 1
    best, j = min((dp[S][i] + D[i + 1][0], i)
                  for i in range(m))
    tour = []
    while j >= 0:
        tour.append(j + 1)
        S, j = S ^ (1 << j), par[S][j]
    return [0] + tour[::-1], best

def nearest_neighbor(D, s=0):
    t, left = [s], set(range(len(D))) - {s}
    while left:
        j = min(left, key=lambda k: D[t[-1]][k])
        t.append(j)
        left.remove(j)
    return t

def two_opt(D, t):
    """역순 교환으로 개선이 없을 때까지"""
    t, n, better = list(t), len(t), True
    while better:
        better = False
        for i in range(n - 1):
            for j in range(i + 2, n):
                a, b = t[i], t[i + 1]
                c, d = t[j], t[(j + 1) % n]
                old = D[a][b] + D[c][d]
                new = D[a][c] + D[b][d]
                if a != d and new < old - 1e-12:
                    t[i + 1:j + 1] = t[i + 1:j + 1][::-1]
                    better = True
    return t

def prim_tree(D):
    n, INF = len(D), float('inf')
    d, par, used, edges = [INF] * n, [-1] * n, [False] * n, []
    d[0] = 0.0
    for _ in range(n):
        free = [i for i in range(n) if not used[i]]
        u = min(free, key=lambda i: d[i])
        used[u] = True
        if par[u] >= 0:
            edges.append((par[u], u))
        for w in range(n):
            if not used[w] and D[u][w] < d[w]:
                d[w], par[w] = D[u][w], u
    return edges

def double_tree(D):
    """MST 선순회: 삼각 부등식이면 최적의 2배 이하"""
    ch = {i: [] for i in range(len(D))}
    for a, b in prim_tree(D):
        ch[a].append(b)
    out, stack = [], [0]
    while stack:
        u = stack.pop()
        out.append(u)
        stack.extend(reversed(ch[u]))
    return out

① 헝가리안의 검증.

② 헝가리안의 계산 시간.

최악의 경우 $O(n^3)$이지만 무작위 비용에서 증가 경로 탐색이 일찍 끝나 측정 기울기가 3보다 작다. 이 기울기는 네 번 실행에서 2.6~2.9 사이였고(시간 측정의 잡음), 입력 분포에 의존하는 값이다.

③ 탐욕 할당 대 최적 할당.

탐욕 할당은 거의 모든 시행에서 최적과 다르며 로봇·과업이 늘수록 평균 간극이 커진다. 이 값은 균일 분포의 유클리드 비용에서의 관찰이다.

④ TSP의 휴리스틱과 정확해.

2-opt는 최근접 이웃의 간극 10.5%를 0.9%로 줄이고 66개 사례에서 최적과 같다. MST 이중 순회는 이론적 상한(2배)에 한참 못 미치는 최대 1.37배이나 평균 16.9%로 최근접 이웃보다 길다.

⑤ 정확해의 계산 시간.

상태 수가 약 2배씩 늘 때 시간도 2배 이상 늘며($n=14$에서 상태 106,496개) 이 증가는 $n$이 수십이 되면 정확해를 불가능하게 한다.

⑥ 라이브러리 호출 결과(실행 2026-11-03). 스크립트는 robotics/fig-src/1.23-libcheck.py, 출력은 robotics/fig-src/data/1.23-libcheck-output.txt에 있다.

Christofides는 MST 이중 순회보다 짧고(1.07 대 1.18) 최대 1.17로 3/2 상한 안이다. OR-Tools의 유도 지역 탐색은 12개 도시에서 모든 사례가 최적이었으나(정수 비용으로 변환), 이는 작은 문제의 결과이며 큰 문제의 성능을 보이지 않는다. SciPy는 $n=640$에서 순수 파이썬보다 약 40배 빠르다.

⑦ 라이브러리 메타데이터(PyPI, 조회 2026-11-03).

한계. 수치는 합성 입력(시드 고정)이다. TSP 비교는 12개 도시의 유클리드 거리에 한정되며 큰 문제와 비대칭·시간 창 문제는 다루지 않았다. 계산 시간은 한 환경의 측정이며 실행마다 달라진다. 탐욕 할당은 한 가지 규칙(가장 싼 쌍 반복 선택)만 비교했다. Christofides는 구현하지 않고 NetworkX의 결과만 보았다. 직사각 행렬·제약 있는 할당(다중 과업·용량)은 다루지 않았다.

견해: 이 책은 단일 과업 할당에는 헝가리안 알고리즘(또는 SciPy의 linear_sum_assignment)을 기본으로 사용하고, 방문 순서는 규모에 따라 정확해(수십 개 미만의 도시), 2-opt·LKH 계열 지역 탐색(수백 개 이상), OR-Tools 같은 라이브러리의 메타휴리스틱 중에서 선택하는 것을 기본으로 둔다고 본다. 근거는 위 예제에서 헝가리안이 다항 시간에 최적을 내는 데 비해 탐욕이 평균 10~19% 길고, TSP 정확해의 시간이 도시 하나당 2배 이상 늘며 2-opt만으로도 12개 도시에서 평균 0.9%까지 줄었다는 점이다. 이 근거는 작은 합성 문제이다.

1.23.6 설계 트레이드오프 — 할당과 방문 순서의 해법

공개 문헌에서 확인되는 선택지는 세 가지다.

• ① 정확해(헝가리안·헬드-카프·분기 한정). 최적 보장. 계산 시간이 크기에 민감하다(TSP).
• ② 휴리스틱(탐욕·최근접 이웃·2-opt·LKH). 빠르다. 최적 보장이 없다.
• ③ 근사 알고리즘(MST 이중 순회·Christofides). 비 상한의 보장이 있다. 실측은 보장보다 훨씬 좋거나(MST) 휴리스틱보다 나쁠 수 있다.

견해: 비용 행렬을 만드는 비용(각 칸의 경로 탐색)이 할당 알고리즘의 비용보다 클 수 있으므로 문제의 병목을 먼저 측정하는 것이 알고리즘 선택보다 중요하다고 본다. 근거는 이 장에서 $n=640$의 헝가리안이 순수 파이썬에서 1.5초, SciPy에서 0.04초였던 반면 비용 행렬 $640^2$칸 각각이 경로 탐색이면 이보다 훨씬 오래 걸릴 수 있다는 점이다(이 장은 경로 탐색 비용을 측정하지 않았다 (추정)).

1.23.7 응용 축 비교

이 표는 이 책의 정리이며 장별 요구는 다르다.

1.23.8 관련 규격·프로토콜

조합 최적화 알고리즘의 표기에 국제 표준은 없다. 결과 비교는 입력·시드·시간 제한을 적은 실행 기록이 기준이다.

1.23.9 관련 규제·인증 요구와의 연결

직접 적용되는 규제는 없다. 작업 할당·경로 순서의 오류(예: 휴리스틱이 낸 비최적 순서)는 작업 시간·충돌 위험에 영향을 줄 수 있으며, 안전 관련 소프트웨어에서는 계획기의 출력이 안전 제약을 만족하는지의 검증이 필요하다. 소프트웨어 안전과 품질 표준은 26.20이 다룬다.

1.23.10 한계·유의점·미해결

• 정리의 출처. NP-난해성·절단 성질·Birkhoff–von Neumann 정리·Christofides 보고서의 정리 번호는 확인하지 않았다 (확인 필요).
• 라이브러리. NetworkX·OR-Tools의 소스와 저장소 정보는 읽지 못했다(GitHub API 한도). OR-Tools의 설정 외 내부 알고리즘은 확인하지 않았다.
• 규모. TSP 비교는 12개 도시이며 수백 개 이상의 거동은 측정하지 않았다.
• 비용 행렬. 경로 탐색에서 비용 행렬을 만드는 비용은 측정하지 않았다.
• 확장. 다중 과업·용량·시간 창 제약이 있는 할당·경로(1.14의 정수 계획, 24.2)는 다루지 않았다.

1.23.11 체크포인트·연구 질문

체크포인트:

1. 그래프의 표현(인접 리스트·행렬)과 신장 트리·MST의 정의를 말할 수 있는가.
2. 할당 문제의 선형 계획·쌍대 형식과 상보 여유성을 적고, 퍼텐셜이 최적성의 인증임을 설명할 수 있는가.
3. 헝가리안 알고리즘의 한 단계(증가 경로와 퍼텐셜 조정)를 설명할 수 있는가.
4. 탐욕 할당이 최적에서 벗어나는 이유를 예제의 도해로 설명할 수 있는가.
5. 헬드-카프의 상태와 점화식을 적고 시간이 $2^n$으로 늘어나는 이유를 설명할 수 있는가.
6. 최근접 이웃·2-opt·MST 이중 순회·Christofides의 보장과 실측 간극을 구별할 수 있는가.
7. 라이브러리의 출력을 같은 입력의 정확해와 대조해 검증하는 방법을 말할 수 있는가.

연구 질문(47.12에 수록한다):

• 다중 로봇 작업 할당에서 비용 행렬의 추정 오차(경로 길이의 불확실성)는 헝가리안 할당의 최적성에 얼마나 영향을 주는가.
• 큰 TSP(수백~수천 개)에서 2-opt·LKH·OR-Tools 메타휴리스틱의 간극과 계산 시간은 로봇 점검 순서 문제에서 어떻게 비교되는가.
• 재계획이 필요한 환경에서 증분적 할당(변화한 행·열만 갱신)은 처음부터 다시 푸는 것에 비해 얼마나 빠른가.

1차 출처

• H. W. Kuhn, 「The Hungarian method for the assignment problem」, Naval Research Logistics Quarterly 2(1–2), 83–97, 1955(doi:10.1002/nav.3800020109).
• J. Munkres, 「Algorithms for the Assignment and Transportation Problems」, Journal of the Society for Industrial and Applied Mathematics 5(1), 32–38, 1957(doi:10.1137/0105003).
• R. Jonker, A. Volgenant, 「A shortest augmenting path algorithm for dense and sparse linear assignment problems」, Computing 38(4), 325–340, 1987(doi:10.1007/bf02278710).
• D. F. Crouse, 「On implementing 2D rectangular assignment algorithms」, IEEE Transactions on Aerospace and Electronic Systems 52(4), 1679–1696, 2016(doi:10.1109/taes.2016.140952).
• M. Held, R. M. Karp, 「A Dynamic Programming Approach to Sequencing Problems」, Journal of the Society for Industrial and Applied Mathematics 10(1), 196–210, 1962(doi:10.1137/0110015).
• R. Bellman, 「Dynamic Programming Treatment of the Travelling Salesman Problem」, Journal of the ACM 9(1), 61–63, 1962(doi:10.1145/321105.321111).
• G. A. Croes, 「A Method for Solving Traveling-Salesman Problems」, Operations Research 6(6), 791–812, 1958(doi:10.1287/opre.6.6.791).
• S. Lin, B. W. Kernighan, 「An Effective Heuristic Algorithm for the Traveling-Salesman Problem」, Operations Research 21(2), 498–516, 1973(doi:10.1287/opre.21.2.498).
• K. Helsgaun, 「An effective implementation of the Lin–Kernighan traveling salesman heuristic」, European Journal of Operational Research 126(1), 106–130, 2000(doi:10.1016/s0377-2217(99)00284-2).
• D. L. Applegate, R. E. Bixby, V. Chvátal, W. J. Cook, 『The Traveling Salesman Problem: A Computational Study』, Princeton University Press(Crossref 등록 2011, doi:10.1515/9781400841103) — 서지만 확인 (확인 필요: 장 번호).
• E. W. Dijkstra, 「A note on two problems in connexion with graphs」, Numerische Mathematik 1(1), 269–271, 1959(doi:10.1007/bf01386390) — 서지만 확인.
• N. Christofides, 「Worst-case analysis of a new heuristic for the travelling salesman problem」, Carnegie-Mellon University Management Sciences Research Group, Report RR-388, 1976 — NetworkX 문서가 인용한 서지, 직접 확인하지 않음 (확인 필요).
• PyPI 메타데이터(조회 2026-11-03)와 설치본 문서: SciPy 1.18.1(linear_sum_assignment), NetworkX 3.7(christofides), OR-Tools 9.15.6755(실행).

다음 장. 1.24는 계산 기하와 공간 자료구조로, 볼록 껍질·보로노이 도형·메시·k-d 트리·옥트리를 다룬다. 이 장의 그래프·정점 집합을 평면·공간의 점으로 옮겨, 근접 질의와 충돌 검사에 사용되는 자료구조의 구조와 비용을 정리한다.