빠른 행진 방법

빠른 행진 방법(빠른行进方法, 영어: fast marching method)^[1]은 제임스 세티안이 만든 방법으로, 다음의 아이코날 방정식의 경계값 문제를 해결하는 수치적 방법이다:

|\nabla u(x)|=1/f(x){\text{ for }}x\in \Omega

u(x)=0{\text{ for }}x\in \partial \Omega

특히, 이런 문제는 닫힌 표면의 진화를 점 $x$ 에서 전파 표면으로 가는 법 방향의 속도 $f$ 와 시간 $u$ 에 관한 함수로 설명한다. 속도 함수는 결정되어 있고, 파면이 점 $x$ 을 통과하는 시간은 방정식을 풀어서 얻을 수 있다. 대신에, $u(x)$ 는 점 $x$ 에서 시작해서 $\partial \Omega$ 에 도달하는 최소 시간으로 생각할 수 있다. 빠른 행진 방법은 "아는 정보"에서 시작해서 해법을 만들어 나가는 문제(즉, 경계값 문제)의 최적 제어 해석의 이점을 이용한다.

알고리즘은 데이크스트라 알고리즘과 유사하고 정보가 시작 영역에서 바깥으로 뻗어나간다는 점을 이용한다. 이 문제는 레벨 셋 방법의 특수한 경우이다. 더 일반적인 알고리즘이 있지만 일반적으로 더 느리다.

평면이 아닌(삼각화된) 영역으로의 확장은 다음을 표면 $S$ 와 $x\in S$ 에 대해서 해결하는 것으로, 론 킴멜과 제임스 세티안이 고안해냈다:

|\nabla _{S}u(x)|=1/f(x),

속도 함수로써의 미로와 최단 경로
무작위 소스 점에서의 거리 맵의 멀티 스탠실

알고리즘 편집

처음에는, 영역이 메쉬로 이산화되었다고 가정한다. 이 메쉬의 점을 꼭짓점으로 부를 것이다. 각각의 꼭짓점 $x_{i}$ 은 대응하는 값인 $U_{i}=U(x_{i})\approx u(x_{i})$ 을 가진다.

이 알고리즘은 데이크스트라 알고리즘과 거의 비슷하지만 꼭짓점의 값을 계산하는 방법은 다르다. 데이크스트라 알고리즘에서 꼭짓점의 값은 인접한 하나의 꼭짓점만 의존해서 계산하지만, $\mathbb {R} ^{n}$ 에서 PDE를 풀 때는 $1$ 에서 $n$ 개의 인접한 꼭짓점을 사용한다.

꼭짓점은 각각 멂(far) (방문하지 않음), 고려 중(considered) (방문했으며 시험적인 값을 부여함), 그리고 완료 됨(accepted) (방문했으며 영구적인 값을 부여함)의 라벨이 붙는다.

모든 꼭짓점 $x_{i}$ 에 $U_{i}=+\infty$ 의 값을 부여하고 멂 라벨을 붙이고, $x_{i}\in \partial \Omega$ 인 모든 꼭짓점에 대해서 $U_{i}=0$ 로 설정하고 $x_{i}$ 의 라벨을 완료 됨으로 설정한다.
모든 먼 꼭짓점 $x_{i}$ 에 대해서, ${\tilde {U}}$ 의 새 값을 계산하기 위해 아이코날 업데이트 공식을 사용한다. ${\tilde {U}}<U_{i}$ 이면, $U_{i}={\tilde {U}}$ 으로 $x_{i}$ 의 라벨을 고려 중으로 설정한다.
${\tilde {x}}$ 가 고려 중인 꼭짓점 중 가장 작은 $U$ 의 값을 가지는 꼭짓점이라면 ${\tilde {x}}$ 에는 완료 됨의 라벨을 붙인다.
${\tilde {x}}$ 의 모든 완료되지 않은 인접한 꼭짓점 $x_{i}$ 에 대해서, 시험적 값 ${\tilde {U}}$ 을 계산한다.
${\tilde {U}}<U_{i}$ 이라면 $U_{i}={\tilde {U}}$ 로 설정한다. If $x_{i}$ 의 라벨이 멂이였다면, 라벨을 고려 중으로 갱신한다.
만약 고려 중인 꼭짓점이 있다면, 3단계로 되돌아간다. 그렇지 않으면 종료한다.