고속 행진법

1. 개요[편집]

고속 행진법 Fast Marching Method (FMM)
고안	James Sethian (1996); Tsitsiklis (1995) 독립 발견
푸는 문제	아이코날 |∇T| = 1/F, F > 0
전략	라벨 설정(label-setting) — 다익스트라형 단일 통과
자료구조	좁은 띠(narrow band) + 최소 힙
복잡도	O(N log N)

다익스트라를 격자에 풀어놓되, 간선 길이 대신 파면의 물리를 넣으면 된다.

고속 행진법(Fast Marching Method, FMM)은 전파속도 $F(\mathbf{x})>0$ 가 한 방향으로만 커지는(단조 전파) 문제에서 아이코날 방정식 $|\nabla T| = 1/F$ 의 도달시간 $T$ 를 격자점을 한 번씩만 확정하며 O(N log N)에 푸는 알고리즘이다. 제임스 세시안(James Sethian)이 1996년 정식화했고, 최적제어 쪽에서 치치클리스(Tsitsiklis)가 1995년 사실상 같은 구조를 독립적으로 얻어 둘을 함께 인용한다.

아이코날 방정식의 물리·점성해·이산화 유도는 아이코날 방정식 문서가 다룬다. 여기서는 그 위에 얹힌 알고리즘만 본다 — 왜 이것이 다익스트라 알고리즘의 연속판인지, 왜 힙이 필요한지, 어디서 다익스트라와 갈라지는지. 한 줄로 요약하면 FMM은 격자화 오차를 없앤 다익스트라다.¹

2. 다익스트라와의 관계[편집]

그래프 최단경로의 다익스트라 알고리즘을 떠올려 보자. 시작점에서 가까운 정점부터 하나씩 **확정(settle)**해 나가고, 확정된 정점의 거리는 두 번 다시 바뀌지 않는다. 이것이 가능한 이유는 간선 가중치가 음이 아니어서 더 먼 정점이 더 가까운 정점의 값을 깎을 수 없기 때문이다. 그래서 매번 미확정 중 최솟값을 꺼내 확정하면 된다 — 이런 부류를 라벨 설정(label-setting) 알고리즘이라 부른다.

FMM은 이 논리를 격자에 그대로 옮긴다. 격자점을 세 상태로 나눈다.

• 확정(Accepted/Known) — $T$ 값이 최종 확정된 점.
• 후보(Trial/Narrow Band) — 확정된 점에 인접해 잠정값을 가진 점. 이들이 좁은 띠(narrow band)를 이룬다.
• 미방문(Far) — 아직 손대지 않은 점.

매 반복은 다익스트라와 판박이다. 후보 중 $T$ 가 최소인 점을 꺼내 확정하고, 그 이웃을 갱신해 좁은 띠를 앞으로 민다. 확정된 최솟값보다 나중에 확정될 점들은 전부 그보다 값이 크므로, 확정값은 재확정되지 않는다.

딱 한 곳에서 갈라진다. 다익스트라의 갱신은 “이웃 값 + 간선 길이”의 최소를 취하는데, 격자에서 이를 그대로 쓰면 진행 방향이 격자축과 대각선(8방향 연결이면 45° 배수)으로 양자화되는 격자화 오차가 생긴다. FMM은 이 갱신을 상방향 이차방정식으로 바꾼다. 상류 이웃값 $T_1, T_2$ 로부터

$$(T-T_1)^2 + (T-T_2)^2 = (h/F)^2$$

의 큰 근을 취하는 이 갱신(판별식이 음수면 1방향 갱신으로 후퇴)이 두 축의 정보를 동시에 섞어, 연속적인 진행 방향을 복원한다. 유도와 인과성 조건은 아이코날 방정식에 있다. 요컨대 뼈대는 다익스트라, 알맹이는 이차방정식 갱신이다.

3. 왜 라벨 설정이 성립하는가[편집]

FMM이 단일 통과로 끝나는 근거는 갱신식의 **인과성(causality)**이다. 이차방정식 갱신에서 나온 $T$ 는 항상 자신을 만든 상류 이웃값 $T_1, T_2$ 보다 크다. 즉 어떤 점의 값은 오로지 자기보다 작은 값들에만 의존한다. 그러므로 현재 후보 중 최솟값을 확정하면, 그보다 큰 값들이 나중에 그것을 끌어내릴 방법이 없다 — 다익스트라의 음이 아닌 간선 조건과 정확히 같은 역할을 인과성이 한다.

이 성질은 동적 계획법의 벨만 최적성 원리와도 닿아 있다. $T(\mathbf{x})$ 를 파원까지의 최소 도달비용으로 보면, FMM은 값이 작은(=이미 최적이 확정된) 상태부터 바깥으로 최적값을 전파하는 전방 동적계획이다. 최적 제어의 값함수를 격자에서 푸는 해밀턴-야코비-벨만 방정식의 특수형이 바로 아이코날이라는 점에서, FMM·다익스트라·값 반복이 한 가족임이 드러난다.

4. 복잡도와 자료구조[편집]

비용은 세 부분으로 쪼개진다. 각 점은 정확히 한 번 확정되고(총 $N$ 회), 확정 때마다 상수 개의 이웃을 이차방정식으로 갱신하며(점당 $O(1)$), 갱신은 좁은 띠의 우선순위 큐에 값을 넣거나 낮춘다. 최소 힙을 쓰면 삽입·감소·추출이 각각 $O(\log N)$ 이므로 총

$$O(N \log N)$$

이다. 여기서 결정적인 사실은 이 비용이 속도장의 복잡도와 무관하다는 것 — 매질이 아무리 광선을 휘게 해도 확정 횟수는 정확히 $N$ 이다. 예측 가능한 최악 성능이 FMM의 큰 매력이다.

자료구조에서 실무적 미세조정이 갈린다.

• 이진 힙이 표준이지만, 값의 정밀도를 버려 정수 버킷에 넣는 **덜 정돈된 큐(untidy priority queue)**를 쓰면 힙 로그를 없애 사실상 $O(N)$ 에 근접시킬 수 있다(야리브·세시안). 격자화 오차 대신 버킷 폭만큼의 순서 오차를 감수하는 거래다.
• 후보가 값을 낮출 때 힙 안의 원소 위치를 찾아야 하므로, 격자점→힙인덱스 역참조 배열을 함께 관리한다. 이 한 줄을 빼먹으면 감소 연산이 $O(N)$ 으로 퇴화한다.

5. 다익스트라 계열에서의 위치[편집]

FMM은 “최솟값부터 확정”하는 라벨 설정이지만, 세상 모든 아이코날 솔버가 그런 건 아니다. 정렬을 포기하는 라벨 수정(label-correcting) 계열이 반대편에 있다.

성격	대표	순서	복잡도	갈아탈 때
라벨 설정	고속 행진법	최소 힙(엄격)	$O(N\log N)$	최악 성능 보장이 필요할 때
라벨 수정	고속 스위핑법	방향 스윕 반복	$O(N)$·상수 매질 의존	속도가 매끈할 때 캐시 이득
라벨 수정	고속 반복법(FIM)	활성 리스트 병렬	문제 의존	GPU에서 힙을 못 쓸 때

고속 스위핑법은 가우스-자이델식으로 격자를 방향 바꿔 훑는다. 힙이 없어 캐시 친화적이고 병렬화가 쉽지만, 스윕 횟수가 광선의 굴곡에 따라 늘어 최악 성능이 문제 의존적이다. 힙이 순차적이라 병렬화가 어려운 FMM의 약점을 정확히 뒤집은 것 — 둘의 비교표는 아이코날 방정식에 자세하다. 실무는 대개 둘 다 두고 문제에 맞춰 고른다.

이 스펙트럼은 그래프 알고리즘의 다익스트라 대 벨만-포드 구도와 정확히 대응한다. 정렬해 한 번에 끝내느냐(다익스트라·FMM), 정렬을 포기하고 수렴할 때까지 훑느냐(벨만-포드·스위핑)의 오래된 이분법이다.

6. 한계 — 단조 전파를 벗어나면[편집]

라벨 설정이 성립하려면 **속도가 양수이고 문제가 등방(isotropic)**이어야 한다. 이 가정이 깨지는 곳이 FMM의 경계다.

• 비등방(anisotropic): 비용이 진행 방향에 의존하면 “최솟값 우선”이 더 이상 최적 확정을 보장하지 않는다. 세시안·블라디미르스키의 정렬 상방향 방법(ordered upwind method)이 비등방 비율에 비례해 스텐실을 넓혀 라벨 설정을 되살리지만, 스텐실이 커지는 만큼 공짜가 아니다.
• 비정렬·둔각 격자: 삼각형이 둔각이면 갱신이 “더 큰 값”에 기대게 되어 인과성이 깨진다. 킴멜·세시안의 펼침(unfolding)이 표준 대응.
• 음의 방향 전파·되돌아오는 파: 값이 한 방향으로만 커진다는 전제가 무너지면 애초에 라벨 설정 자체를 못 쓴다. 되돌아오는 다중 도달파는 FMM의 사정거리 밖이다(아이코날 방정식의 점성해 절 참조).

7. 알고리즘이 쓰이는 곳[편집]

물리 응용의 상세는 아이코날 방정식에 있으니, 여기서는 왜 FMM이라는 알고리즘이 뽑히는지만 짚는다.

• 경로 계획과 로보틱스: 비용장 $1/F$ 위에서 $T$ 를 한 번 행진시키면 도메인 전체의 비용-투-고가 채워지고, $-\nabla T$ 를 따라 내려가면 최적 경로가 나온다. 격자 위 A*가 8방향 양자화로 진행 방향을 45° 배수로 꺾는 반면, FMM은 연속 방향을 낸다. 내비게이션 메시의 흐름장, 군중 시뮬레이션의 연속체 모형이 이 성질을 산다.
• 레벨셋 방법의 재초기화: $F\equiv 1$ 이면 $T$ 가 곧 거리라, 계면에서 FMM을 한 번 행진시키면 부호거리함수가 복원된다. 반복 PDE보다 계면을 덜 흔들어 질량 누출이 적다. 순수 유클리드 거리만 필요하면 거리 변환의 정확 알고리즘이 더 싸다 — FMM은 속도가 변할 때 값을 한다.
• 최소비용 세그멘테이션·형상 복원: 측지 활성 윤곽, 음영으로부터 형상 복원처럼 “가장 싼 도달”이 목적함수인 문제에서 단일 통과의 예측 가능한 비용이 강점이다.

8. 여담[편집]

• 다익스트라와의 유사성이 너무 강해서, FMM을 처음 구현한 사람들의 소감이 대체로 “이거 다익스트라 아니냐”인데 절반은 맞다. 나머지 절반, 이차방정식 갱신이 격자화 오차를 없애는 부분이 이 방법을 알고리즘 하나로 격상시킨 알맹이다.
• 이름의 “고속”은 그리디하게 한 번에 끝낸다는 뜻이지 상수가 작다는 뜻이 아니다. 실제로 매끈한 매질에서는 힙 없는 스위핑이 더 빠를 때가 많다 — 그리디 알고리즘이 늘 최속은 아니라는 교과서적 교훈이 여기서도 나온다.

9. 관련 문서[편집]

• 아이코날 방정식 · 레벨셋 방법 · 거리 변환
• 다익스트라 알고리즘 · 우선순위 큐 · 그리디 알고리즘 · 고속 스위핑법
• 동적 계획법 · 해밀턴-야코비-벨만 방정식 · 최적 제어
• 경로 계획 · 내비게이션 메시 · 군중 시뮬레이션 · 역문제

10. Footnotes[편집]

1. FMM과 다익스트라의 관계를 두고 “FMM은 다익스트라의 일반화”라고들 하지만, 방향을 뒤집어 “다익스트라는 $F\equiv$상수 격자에서 이차방정식을 1차 갱신으로 근사한 FMM”이라 말해도 틀리지 않는다. 어느 쪽이 부모인지는 그래프에서 왔느냐 PDE에서 왔느냐의 관점 차이일 뿐이다. ↩